Exercise · ZW-EULER-S-THEOREM-001 · ★☆☆ Basic
State Euler's theorem with its hypotheses.
Choose one option.
Show answer
- B. If \(\gcd(a,n)=1\), then \(a^{\varphi(n)}\equiv 1 \pmod n\)
Explanation
The correct option gives the exact statement with the coprimality hypothesis and exponent \(\varphi(n)\). The one using \(a^n\equiv a\) corresponds to Fermat's little theorem, not this result.
Review the concept: Euler's theorem
Euler's theorem states that if \(a\) and \(n\) are coprime, then \(a^{\varphi(n)} \equiv 1 \pmod{n}\), generalizing Fermat's little theorem to composite moduli.
\[a^{\varphi(n)} \equiv 1 \pmod{n}, \quad \gcd(a,n)=1\]
More practice problems: euler's theorem
- ZW-EULER-S-THEOREM-002 Compute φ(12).
- ZW-EULER-S-THEOREM-003 Find the remainder of 3^100 modulo 7 using Euler's theorem.
- ZW-EULER-S-THEOREM-004 Which is the value of φ(9)?
- ZW-EULER-S-THEOREM-005 By Euler's theorem, which exponent of 5 modulo 8 gives remainder 1?
- ZW-EULER-S-THEOREM-006 Compute 11^203 bmod 12.
- ZW-EULER-S-THEOREM-007 Use Euler's theorem to find 2^1000 bmod 9.
- ZW-EULER-S-THEOREM-008 Find the last digit of 3^2026 in base 10.
- ZW-EULER-S-THEOREM-009 Compute 5^2025bmod 16.