Exercise on congruences
Exercise 1. Determine the remainder of the division by 9 of the number
574321142
and the remainder of the division by 3 of the number
89741527
Solution. The sum of the digits of 57432 is 21 so the number is divisible by 3 and we can write:
57432 ≡ 3 mod 9 → 574321142 ≡ 31142 mod 9
but 31142 ≡ 0 mod 9, so
574321142 ≡ 0 mod 9
the remainder is 0.
The sum of the digits of 89741 is 29 so the number, we can write
89741 ≡ 2 mod 3 → 89741527 ≡ 2527 mod 3
23 ≡ 2 mod 3 → 2527 ≡ 2525 mod 3
so 2527 ≡ 2 mod 3 → 89741527 ≡ 2 mod 3
Exercise 2. Find last two digits of 30246 and 7506.
Solution. The last two digits of a number are obtained as remainder of the division by 100, thus we work mod 100. It is easy to notice that
302 = 2 mod 100
then
30246 = 246 mod 100
now
246 = ( 220 ⋅ 23)2 = ((210)2 ⋅ 8)2 = (242 ⋅ 8)2
Now notice that 242 = 576 and 576 ≡ 76 mod 100, and then also that 76 ⋅ 8 = 608 is congruent to 8 mod 100 so we have
246 ≡ (76 ⋅ 8)2 ≡ 82 ≡ 64 mod 100
2) 7506 ≡ (72)253 ≡ (49)2 ⋅ 126 + 1
72 = 2401 ≡ 1 mod 100, so
(49)2⋅ 126 + 1 ≡ 1126 ⋅ 49 ≡ 49
The last two digits are thus 49.
Exercise 3. Verify that 2n17 + 2n15 + 3n3 + 3n is divisible by 5 for every n ∈ ℕ
Solution. n17 = n3⋅5 + 2 and by Fermat's little theorem we have
n5 ≡ n mod 5
n17 ≡ n3 ⋅ n2 ≡ n5 ≡ n.
Analogously n15 = n5 ⋅ 3 ≡ n3. With these two facts we can write
2n17 + 2n15 + 3n3 + 3n ≡ 2n + 2n3 + 3n3 + 3n ≡ 5n + 5n3 ≡ 0 (mod 5)