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

Problem Solving with Fermat's and Euler's Theorems

Solve advanced problems involving large powers, inverses, and congruences using both theorems strategically.

Problem Solving with Fermat's and Euler's Theorems

What You'll Learn

You'll learn to strategically choose between Fermat's Little Theorem and Euler's Theorem to solve complex problems involving large powers, modular inverses, and congruences efficiently.

The Strategic Approach

Now that you understand both theorems individually, the key is knowing when to use each:

  • Fermat's Little Theorem works when your modulus is prime (p): a^(p-1) ≡ 1 (mod p)
  • Euler's Theorem works for any modulus n (when gcd(a,n) = 1): a^φ(n) ≡ 1 (mod n)

Think of Fermat's theorem as your specialized tool and Euler's theorem as your universal toolkit. When you can use the specialized tool (prime modulus), it's often simpler. Otherwise, reach for Euler's.

Strategic Problem-Solving Steps

1. Computing Large Powers

To find 3^1000000 mod 11:

  • Recognize 11 is prime → use Fermat's
  • 3^10 ≡ 1 (mod 11)
  • Write 1000000 = 10 × 100000, so 3^1000000 ≡ 1^100000 ≡ 1 (mod 11)

2. Finding Inverses

To find the inverse of 7 modulo 15:

  • 15 is composite → use Euler's
  • φ(15) = φ(3·5) = 2·4 = 8
  • The inverse is 7^(8-1) = 7^7 mod 15

3. Mixed Moduli Problems

To solve 5^n ≡ 1 (mod 12) for the smallest n:

  • φ(12) = 4, and gcd(5,12) = 1
  • By Euler's theorem, n divides 4
  • Test: 5^1 ≡ 5, 5^2 ≡ 1 (mod 12) ✓
  • Answer: n = 2

Key Takeaway: Master problem-solving by identifying whether your modulus is prime (use Fermat's for simplicity) or composite (use Euler's with φ(n)), then reduce exponents systematically using the appropriate theorem to make seemingly impossible calculations tractable.