Numerical answer
What is the remainder when 2³⁰¹ is divided by 9?
Show answer and solution
Answer: 2
9 is not prime, but 2 is coprime to 9, so Euler's theorem applies: 2^φ(9) ≡ 1 (mod 9), where φ(9) = 9(1 − 1/3) = 6.
301 = 6 × 50 + 1, so 2³⁰¹ ≡ 2¹ (mod 9) = 2.
Remainder = 2.
Tip: For a composite modulus m, use Euler's theorem with φ(m) in place of (p − 1); here φ(9) = 6 since 9 = 3² gives φ(3²) = 3² − 3 = 6.
301 = 6 × 50 + 1, so 2³⁰¹ ≡ 2¹ (mod 9) = 2.
Remainder = 2.
Tip: For a composite modulus m, use Euler's theorem with φ(m) in place of (p − 1); here φ(9) = 6 since 9 = 3² gives φ(3²) = 3² − 3 = 6.
Saved on this device. Sign in or create a free account to keep it on every device.