Numerical answer
What is the remainder when 17²⁰⁵ is divided by 9?
Show answer and solution
Answer: 8
Since gcd(17, 9) = 1, Euler's theorem applies with φ(9) = 6, so 17⁶ ≡ 1 (mod 9).
17 ≡ −1 (mod 9), so 17²⁰⁵ ≡ (−1)²⁰⁵ = −1 ≡ 8 (mod 9).
Check: 205 = 6 × 34 + 1, so 17²⁰⁵ ≡ 17¹ ≡ −1 ≡ 8 (mod 9), consistent.
Tip: Whenever the base is congruent to −1 (or a small number) modulo the divisor, use that directly instead of computing φ(n).
17 ≡ −1 (mod 9), so 17²⁰⁵ ≡ (−1)²⁰⁵ = −1 ≡ 8 (mod 9).
Check: 205 = 6 × 34 + 1, so 17²⁰⁵ ≡ 17¹ ≡ −1 ≡ 8 (mod 9), consistent.
Tip: Whenever the base is congruent to −1 (or a small number) modulo the divisor, use that directly instead of computing φ(n).
Saved on this device. Sign in or create a free account to keep it on every device.