What is the remainder when (13100 + 17100) is divided by 25?
20232024
What is the remainder when (13100 + 17100) is divided by 25?
- A.
0
- B.
2
- C.
4
- D.
11
Attempted by 31 students.
Show answer & explanation
Correct answer: B
Key idea: use Euler's theorem with modulus 25.
Compute φ(25) = 25 × (1 − 1/5) = 20.
Since gcd(13,25) = 1 and gcd(17,25) = 1, Euler's theorem gives a^20 ≡ 1 (mod 25) for a = 13 and a = 17.
Because 100 = 20 × 5, we have 13^100 = (13^20)^5 ≡ 1^5 ≡ 1 (mod 25) and 17^100 ≡ 1 (mod 25).
Therefore 13^100 + 17^100 ≡ 1 + 1 ≡ 2 (mod 25). The remainder upon division by 25 is 2.