Divisibility and primes

Remainders, divisibility rules, unknown digits, prime numbers and counting multiples. 8 problems with step-by-step solutions.

Solve each problem in your notebook first, then open the solution.

Problem 1 Remainders

a) When \(p\) is divided by 5 the remainder is 3. Find the remainder when \(p^2\) and \(2p + 1\) are divided by 5.

b) \(n \in \mathbb{N}\) and \(\dfrac{4n + 23}{n + 2}\) is a natural number. Find all possible \(n\).

Show solution

a) \(p = 5k + 3\): \(p^2 = 25k^2 + 30k + 9\) leaves the same remainder as 9, i.e. 4. \(2p + 1 = 10k + 7\): remainder 2.

b) \(\frac{4n + 23}{n + 2} = 4 + \frac{15}{n + 2}\). \(n + 2\) divides 15 and \(n + 2 \ge 3\): \(n + 2 \in \{3, 5, 15\}\), so \(n \in \{1, 3, 13\}\).

Problem 2 Digit differences

a) \(\overline{abc}\) and \(\overline{cba}\) are three-digit numbers. Show that \(\overline{abc} - \overline{cba}\) is divisible by 99.

b) Show that \(\overline{abc} - \overline{bca}\) is divisible by 9.

Show solution

a) \((100a + 10b + c) - (100c + 10b + a) = 99a - 99c = 99(a - c)\).

b) \((100a + 10b + c) - (100b + 10c + a) = 99a - 90b - 9c = 9(11a - 10b - c)\).

Problem 3 Prime or not

Is the number prime? a) 391 b) 397 c) 667 d) 2003

e) Is \(13 + 26 + 39\) prime? f) Is \(7999999\) prime?

Show solution

Test the primes up to \(\sqrt{n}\).

a) \(391 = 17\cdot 23\): not prime.
b) \(\sqrt{397} < 20\); not divisible by 2, 3, 5, 7, 11, 13, 17, 19: prime.
c) \(667 = 23\cdot 29\): not prime.
d) \(\sqrt{2003} < 45\); not divisible by any prime up to 43: prime.
e) \(13(1 + 2 + 3) = 78\): not prime.
f) \(7999999 = 8\cdot 10^6 - 1 = 200^3 - 1 = (200 - 1)(200^2 + 200 + 1) = 199\cdot 40201\): not prime.

Problem 4 Divisibility rules

a) Is 784512 divisible by 3? by 4? by 8? by 9?

b) Find the remainder when 9472351 is divided by 3, by 4, by 5 and by 9.

c) Is 5917394 divisible by 11?

Show solution

a) Digit sum \(7 + 8 + 4 + 5 + 1 + 2 = 27\): divisible by 3 and 9. Last two digits 12: divisible by 4. Last three 512 \(= 8\cdot 64\): divisible by 8.

b) Digit sum 31: remainder 1 by 3, remainder 4 by 9. Last two digits 51: remainder 3 by 4. Last digit 1: remainder 1 by 5.

c) Alternating sum from the right: \(4 - 9 + 3 - 7 + 1 - 9 + 5 = -12\), not divisible by 11. So no (the remainder is 10).

Problem 5 Unknown digits

a) Find all digits \(m\) such that \(53m28\) is divisible by 3.

b) Find all digits \(m\) such that \(4716m\) is divisible by 4.

c) The four-digit number \(\overline{57mn}\) is divisible by 5 and by 8. Find all such numbers.

d) The five-digit number \(\overline{629ab}\) is divisible by 5 and 9. Find all such numbers.

Show solution

a) \(5 + 3 + m + 2 + 8 = 18 + m\): \(m \in \{0, 3, 6, 9\}\).

b) \(\overline{6m}\) divisible by 4: \(m \in \{0, 4, 8\}\).

c) Divisible by 5 and 8 means divisible by 40, so \(n = 0\) and \(\overline{57m}\) must be divisible by 4: \(m \in \{2, 6\}\). Numbers: 5720 and 5760.

d) \(b \in \{0, 5\}\). Digit sum \(17 + a + b\) divisible by 9: \(b = 0 \Rightarrow a = 1\); \(b = 5 \Rightarrow a = 5\). Numbers: 62910 and 62955.

Problem 6 Combined rules

a) Find all pairs \((a, b)\) such that \(\overline{7a3b}\) is divisible by 15.

b) \(\overline{5m31n}\) is divisible by 6. Find the greatest such number.

c) Find the possible values of \(k\) if \(\overline{1k52}\) is divisible by 33.

Show solution

a) 15 = 3·5. \(b \in \{0, 5\}\), and \(10 + a + b\) divisible by 3. \(b = 0\): \(a \in \{2, 5, 8\}\); \(b = 5\): \(a \in \{0, 3, 6, 9\}\).

b) Even and digit sum \(9 + m + n\) divisible by 3. Take \(m = 9\): \(18 + n\) divisible by 3 and \(n\) even: \(n \in \{0, 6\}\). Greatest: 59316.

c) 33 = 3·11. By 3: \(8 + k\) divisible by 3, so \(k \in \{1, 4, 7\}\). By 11: \(2 - 5 + k - 1 = k - 4\) divisible by 11, so \(k = 4\). Answer \(k = 4\) (\(1452 = 33\cdot 44\)).

Problem 7 Counting multiples

a) How many numbers in \(\{1, 2, \dots, 500\}\) are divisible by 6 or 8?

b) How many numbers in \(\{1, 2, \dots, 100\}\) are divisible by neither 2 nor 5?

Show solution

a) \(\lfloor 500/6\rfloor + \lfloor 500/8\rfloor - \lfloor 500/24\rfloor = 83 + 62 - 20 = 125\).

b) Divisible by 2 or 5: \(50 + 20 - 10 = 60\). Neither: \(100 - 60 = 40\).

Problem 8 Remainder of sums and products

a) Find the remainder when \(2347\cdot 589 + 1234\) is divided by 9.

b) Find the remainder when \(518\cdot 731 - 263\) is divided by 4.

Show solution

a) Remainders mod 9: \(2347 \to 7\), \(589 \to 4\), \(1234 \to 1\). \(7\cdot 4 + 1 = 29 \to 2\). Remainder 2.

b) Mod 4: \(518 \to 2\), \(731 \to 3\), \(263 \to 3\). \(6 - 3 = 3\). Remainder 3.