Course contentsShow
← Mathematics
Lesson 2748 of 3,12154. Number TheoryFree lesson

Statement of Euler's Theorem

Euler's generalization: if gcd(a,n) = 1, then a^φ(n) ≡ 1 (mod n), extending Fermat's Little Theorem to composite moduli.

Statement of Euler's Theorem

You'll learn: How Euler generalized Fermat's Little Theorem to work with any modulus, not just primes.

The Big Idea

Fermat's Little Theorem told us that if p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p). But what if our modulus isn't prime? What if we're working modulo 12, or 15, or 100?

Euler discovered a beautiful generalization: if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function counting integers relatively prime to n.

Understanding the Theorem

The power of Euler's Theorem is that it works for any modulus n, whether prime or composite, as long as a and n are relatively prime.

  • When n is prime: φ(n) = n - 1, so Euler's Theorem reduces exactly to Fermat's Little Theorem
  • When n is composite: φ(n) gives us the right exponent to make a^φ(n) ≡ 1 (mod n)

Example: Take n = 10. We know φ(10) = 4 (the numbers 1, 3, 7, 9 are relatively prime to 10). Euler's Theorem says that for any a with gcd(a, 10) = 1:

  • 3^4 = 81 ≡ 1 (mod 10) ✓
  • 7^4 = 2401 ≡ 1 (mod 10) ✓
  • 9^4 = 6561 ≡ 1 (mod 10) ✓

Why It Matters

Euler's Theorem is foundational for modern cryptography (especially RSA), computing large powers modulo composite numbers, and solving congruences where the modulus isn't prime. It unifies our understanding of modular exponentiation.

Key Takeaway: Euler's Theorem states that if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n), extending Fermat's result from prime moduli to any modulus where a is relatively prime to n.