Congruences are a powerful tool for working with remainders in division.
Definition of Congruence
When integers a and b leave the same remainder upon division by m, we write a ≡ b (mod m)。
a ≡ b (mod m) ⟺ m | (a−b) ⟺ a and b leave equal remainders when divided by m
Basic Properties of Congruences
When a≡b and c≡d (mod m):
・a+c ≡ b+d (mod m) （addition）
・a−c ≡ b−d (mod m) （subtraction）
・ac ≡ bd (mod m) （multiplication）
・an ≡ bn (mod m) （exponentiation）
Example ① (Calculating a Congruence)
Using 17 ≡ 2 (mod 5) and 23 ≡ 3 (mod 5), find the remainder when 17×23 is divided by 5.
17×23 ≡ 2×3 = 6 ≡ 1 (mod 5)
Answer: The remainder is 1
Using 17 ≡ 2 (mod 5) and 23 ≡ 3 (mod 5), find the remainder when 17×23 is divided by 5.
17×23 ≡ 2×3 = 6 ≡ 1 (mod 5)
Answer: The remainder is 1
Example ② (Remainders of Powers)
Find the remainder when 3100 is divided by 7.
3¹≡3、3²≡2、3³≡6、3⁴≡4、3⁵≡5、3⁶≡1 (mod 7)（period 6）
100 = 6×16+4 → 3100≡3⁴≡4 (mod 7)
Answer: The remainder is 4
Find the remainder when 3100 is divided by 7.
3¹≡3、3²≡2、3³≡6、3⁴≡4、3⁵≡5、3⁶≡1 (mod 7)（period 6）
100 = 6×16+4 → 3100≡3⁴≡4 (mod 7)
Answer: The remainder is 4
Key Points
- Congruences allow addition, subtraction, multiplication, and exponentiation
- Division is possible only by numbers relatively prime to mod m
- Look for periodicity when finding remainders of powers
Practice Problems
- Using congruences, find the remainder when 210 is divided by 3.
- Find the remainder when 520 is divided by 7 (first find the period of powers of 5).
- Using congruences, find the remainder when 13×17×19 is divided by 5.
Answers and Explanations
- 2≡−1(mod 3) → 210≡(−1)10=1(mod 3) → remainder1
- 5¹≡5、5²≡4、5³≡6、5⁴≡2、5⁵≡3、5⁶≡1(mod 7)（period 6）. 20=6×3+2 → 520≡5²≡4(mod 7) → remainder4
- 13≡3、17≡2、19≡4(mod 5) → 3×2×4=24≡4(mod 5) → remainder4