Congruences allow us to solve remainders of large numbers and integer problems efficiently.
Example ① (Remainder of a Large Number)
Find the remainder when 20242024 is divided by 9.
2024 = 2+0+2+4 = 8 → 2024≡8≡−1(mod 9)
20242024≡(−1)2024=1(mod 9)
Answer: The remainder is 1
Find the remainder when 20242024 is divided by 9.
2024 = 2+0+2+4 = 8 → 2024≡8≡−1(mod 9)
20242024≡(−1)2024=1(mod 9)
Answer: The remainder is 1
Example ② (Proof of Divisibility)
Show that n³−n is a multiple of 6 when n is an integer.
n³−n = n(n−1)(n+1)（product of three consecutive integers）
Three consecutive integers contain one multiple of 2 and one multiple of 3 → a multiple of 2×3=6 ■
Show that n³−n is a multiple of 6 when n is an integer.
n³−n = n(n−1)(n+1)（product of three consecutive integers）
Three consecutive integers contain one multiple of 2 and one multiple of 3 → a multiple of 2×3=6 ■
Example ③ (A Congruence Equation)
Solve 3x ≡ 2 (mod 7).
Since 3×5=15≡1(mod 7), the inverse of 3 is 5. Multiply both sides by 5:
x ≡ 5×2 = 10 ≡ 3 (mod 7)
Answer:x ≡ 3 (mod 7)
Solve 3x ≡ 2 (mod 7).
Since 3×5=15≡1(mod 7), the inverse of 3 is 5. Multiply both sides by 5:
x ≡ 5×2 = 10 ≡ 3 (mod 7)
Answer:x ≡ 3 (mod 7)
Key Points
- Test for multiples of 9: the sum of the digits is a multiple of 9
- Test for multiples of 3: the sum of the digits is a multiple of 3
- n(n−1)(n+1) is the product of three consecutive integers → a multiple of 6
- Congruence equations use inverses (solutions of ax≡1(mod m))
Practice Problems
- Find the remainder when 7100 is divided by 10 (the units digit).
- Show that when n is an integer, the remainder when n² is divided by 4 is only 0 or 1.
- Solve 2x ≡ 1 (mod 5).
Answers and Explanations
- 7¹≡7、7²≡9、7³≡3、7⁴≡1(mod 10)（period 4）. 100=4×25 → 7100≡1(mod 10) → remainder1（the units digit is 1）
- Let n≡0,1,2,3(mod 4). Then n²≡0,1,0,1(mod 4) → the remainder is only 0 or 1 ■
- Since 2×3=6≡1(mod 5), the inverse is 3. x≡3×1=3(mod 5) → x≡3(mod 5)