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

Applications of Euler's Theorem to Modular Arithmetic

Use Euler's Theorem to reduce large exponents and find modular inverses when the modulus is composite.

Applications of Euler's Theorem to Modular Arithmetic

What you'll learn: How to use Euler's Theorem to simplify exponents and find modular inverses when working with composite moduli.

The Core Idea

Euler's Theorem tells us that if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function. This powerful result lets us reduce enormous exponents and find inverses without the Extended Euclidean Algorithm when dealing with composite moduli.

Think of φ(n) as a "reset point"—every φ(n) steps in the exponent brings you back to 1 (mod n), just like how the hour hand on a clock resets every 12 hours.

Reducing Large Exponents

When computing something like 7^1234 (mod 10), direct calculation is impractical. Instead:

  1. Find φ(10) = φ(2·5) = φ(2)·φ(5) = 1·4 = 4
  2. Check that gcd(7, 10) = 1 ✓
  3. Reduce the exponent: 1234 = 4·308 + 2, so 7^1234 ≡ 7^2 ≡ 49 ≡ 9 (mod 10)

We only need to compute 7^2 instead of 7^1234!

Finding Modular Inverses

To find the inverse of a modulo n (where gcd(a, n) = 1):

The inverse is a^(φ(n)-1) (mod n) because: a · a^(φ(n)-1) ≡ a^φ(n) ≡ 1 (mod n)

Example: Find the inverse of 3 modulo 10.

  • φ(10) = 4
  • The inverse is 3^(4-1) = 3^3 = 27 ≡ 7 (mod 10)
  • Check: 3·7 = 21 ≡ 1 (mod 10) ✓

This method works beautifully when φ(n) is easy to compute, especially for composite moduli!

Key Takeaway: Euler's Theorem transforms intimidating modular arithmetic problems into manageable calculations by exploiting the cyclic pattern of powers modulo n.