Computing Large Powers Using Fermat's Little Theorem
You'll learn how to use Fermat's Little Theorem as a shortcut to calculate massive powers in modular arithmetic without actually computing astronomical numbers.
The Core Idea
When you need to compute something like 7^1000000 mod 11, calculating 7 to the millionth power directly is impossible—the number would have hundreds of thousands of digits! Fermat's Little Theorem gives us a clever workaround.
Recall that Fermat's Little Theorem states: if p is prime and a is not divisible by p, then:
a^(p-1) ≡ 1 (mod p)
This means raising a to the power (p-1) "loops back" to 1 modulo p. We can use this cyclical behavior to shrink huge exponents.
How It Works
To compute a^n mod p:
- Divide the exponent: Write n = q(p-1) + r where 0 ≤ r < p-1
- Apply the theorem: a^n = a^(q(p-1) + r) = (a^(p-1))^q · a^r ≡ 1^q · a^r ≡ a^r (mod p)
- Compute the small power: Calculate a^r mod p, which is manageable since r < p-1
Example: Find 7^1000000 mod 11
- Here p = 11, so p-1 = 10
- Divide: 1000000 = 100000(10) + 0
- Therefore: 7^1000000 ≡ 7^0 ≡ 1 (mod 11)
Another example: Find 3^50 mod 7
- Here p = 7, so p-1 = 6
- Divide: 50 = 8(6) + 2
- Therefore: 3^50 ≡ 3^2 ≡ 9 ≡ 2 (mod 7)
Think of it like a clock: just as 25 hours from now is the same as 1 hour from now (since hours cycle every 24), powers cycle every (p-1) steps in modulo p arithmetic.
Key Takeaway: Fermat's Little Theorem lets you reduce any exponent modulo (p-1) when computing powers modulo a prime p, transforming impossible calculations into trivial ones.