Divisibility and Euclidean division
We say n divides a (written n | a) if a = n × k for some integer k. Example: 5 | 35 because 35 = 5 × 7.
Euclidean division: for any integer a and any whole number n ≥ 1, there is exactly one pair q, r with
a = n × q + r, and 0 ≤ r < n.
q is the quotient, r the remainder. For negative a, the remainder is still between 0 and n − 1: −7 = 5 × (−2) + 3, so the remainder is 3, not −2.
Useful facts: if n | a and n | b, then n divides a + b, a − b and any a × x + b × y.
Congruence modulo n
a ≡ b (mod n) means a and b leave the same remainder when divided by n. Equivalently, n | (a − b).
- 17 ≡ 2 (mod 5) since 17 − 2 = 15 = 5 × 3.
- Every integer is congruent to exactly one of 0, 1, …, n − 1: its remainder.
- a ≡ 0 (mod n) means n divides a.
Think of a clock with n numbers: congruent numbers stop at the same place.
Operations with congruences
If a ≡ b and c ≡ d (mod n), then:
- a + c ≡ b + d and a − c ≡ b − d
- a × c ≡ b × d
- ak ≡ bk for any whole number k
Remainders of powers repeat in a cycle. Find the cycle, then use the exponent’s remainder.
Example: 3k mod 7 gives 3, 2, 6, 4, 5, 1, then repeats every 6. So 3100: 100 = 6 × 16 + 4, so 3100 ≡ 34 ≡ 4 (mod 7).
Careful: you cannot always divide. 2 × 3 ≡ 2 × 8 (mod 10) but 3 ≢ 8 (mod 10). You may cancel a factor only if it shares no common factor with n.
Divisibility rules explained by congruences
- By 2, 5, 10: 10 ≡ 0 (mod 2, 5, 10), so only the last digit matters.
- By 4 (and 25): 100 ≡ 0, so only the last two digits matter.
- By 3 and 9: 10 ≡ 1, so every power of 10 ≡ 1. A number ≡ the sum of its digits.
- By 11: 10 ≡ −1, so a number ≡ alternating sum of digits from the right (+ − + …).
Example: 7 392: digit sum 21 is divisible by 3, so 7 392 is too. Alternating sum 2 − 9 + 3 − 7 = −11, so it is divisible by 11.
Solving simple integer equations
Congruences show quickly when an equation has no integer solution. Example: x² = 4y + 3. Squares mod 4 are only 0 or 1 (0² = 0, 1² = 1, 2² = 4 ≡ 0, 3² = 9 ≡ 1), but the right side is ≡ 3 (mod 4). So no integers work.
Linear congruence 3x ≡ 4 (mod 7): try x = 0…6: 3 × 6 = 18 ≡ 4, so x ≡ 6 (mod 7), i.e. x = 7k + 6.
Key formulas and definitions
- a = n × q + r, 0 ≤ r < n
- a ≡ b (mod n) ⇔ n | (a − b)
- a ≡ b, c ≡ d ⇒ a ± c ≡ b ± d, ac ≡ bd
- a ≡ b ⇒ aᵏ ≡ bᵏ (mod n)
- 10 ≡ 1 (mod 9) and 10 ≡ −1 (mod 11)
Worked examples
1. Write the Euclidean division of 100 by 7.
7 × 14 = 98 and 100 − 98 = 2. So 100 = 7 × 14 + 2: q = 14, r = 2.
2. Find the remainder when −23 is divided by 6.
6 × (−4) = −24, and −23 − (−24) = 1. So −23 = 6 × (−4) + 1, remainder 1 (between 0 and 5).
3. Is 1 234 ≡ 4 (mod 9)?
Digit sum = 1 + 2 + 3 + 4 = 10 ≡ 1 (mod 9). So 1 234 ≡ 1, not 4. The statement is false.
4. Find the remainder of 47 × 58 when divided by 5.
47 ≡ 2 and 58 ≡ 3 (mod 5). 2 × 3 = 6 ≡ 1. Remainder 1. (Check: 47 × 58 = 2 726 = 5 × 545 + 1.)
5. Find the remainder when 2¹⁰⁰ is divided by 7.
2¹ ≡ 2, 2² ≡ 4, 2³ = 8 ≡ 1 (mod 7). Cycle length 3. 100 = 3 × 33 + 1, so 2¹⁰⁰ = (2³)³³ × 2 ≡ 1 × 2 = 2.
6. Show that n³ − n is divisible by 3 for every integer n.
n ≡ 0, 1 or 2 (mod 3). n³ − n = (n − 1)n(n + 1). Check: 0 → 0; 1 → 0; 2 → 8 − 2 = 6 ≡ 0. In every case it is ≡ 0, so 3 divides it.
Common mistakes
- Giving a negative remainder: the remainder must be between 0 and n − 1 (−7 mod 5 is 3, not −2).
- Dividing both sides of a congruence by a number that shares a factor with n.
- Working out a huge power fully instead of reducing at every step and using the cycle.
- Using the exponent’s remainder without first finding the cycle length (for 2ᵏ mod 7 the cycle is 3, not 7).