Congruences · Definition

Euler's theorem

elementary number theorycongruences

Before you start you need to know

Many modular power computations simplify once the exponent is reduced modulo \(\varphi(n)\). Euler's theorem is the tool that justifies this reduction when the modulus is not prime.

Definition

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\]

If \(\gcd(a,n)=1\), multiplying each element \(r_1,\dots,r_{\varphi(n)}\) of a reduced residue system by \(a\) gives another reduced residue system, so \(a^{\varphi(n)}\,r_1\cdots r_{\varphi(n)}\equiv r_1\cdots r_{\varphi(n)} \pmod{n}\). Since this product is coprime to \(n\), it can be cancelled, giving \(a^{\varphi(n)}\equiv 1 \pmod{n}\). When \(n\) is prime, \(\varphi(n)=n-1\) and the result reduces to Fermat's little theorem.

For example, to compute \(7^{222} \bmod 10\): since \(\gcd(7,10)=1\) and \(\varphi(10)=4\), we have \(7^{4}\equiv 1 \pmod{10}\). Since \(222=4\cdot 55+2\), we get \(7^{222}\equiv 7^{2}=49\equiv 9 \pmod{10}\).

A typical mistake is applying the theorem without checking that \(\gcd(a,n)=1\), for example using \(2^{\varphi(8)}\equiv 1 \pmod 8\) when \(2^4=16\equiv 0\pmod 8\). Another common error is using \(n-1\) instead of \(\varphi(n)\) as the exponent for composite moduli.

Think about it

Why does Euler's theorem require \(\gcd(a,n)=1\)?

Because \(a\) must be invertible modulo \(n\) so the product of residues can be cancelled; without coprimality cancellation fails.

Exercises 10

  1. State Euler's theorem with its hypotheses.
  2. Compute \(\varphi(12)\).
  3. Find the remainder of \(3^{100}\) modulo \(7\) using Euler's theorem.
  4. Which is the value of \(\varphi(9)\)?
  5. By Euler's theorem, which exponent of \(5\) modulo \(8\) gives remainder 1?
  6. Compute \(11^{203} \bmod 12\).
  7. Use Euler's theorem to find \(2^{1000} \bmod 9\).
  8. Find the last digit of \(3^{2026}\) in base 10.
  9. Compute \(5^{2025}\bmod 16\).
  10. Prove that \(a^{13}\equiv a\pmod{30}\) for all \(a\) coprime to 30, and check with \(a=7\).

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 7
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 2