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, so3^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.