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

Computing Large Powers Using Fermat's Little Theorem

Use Fermat's Little Theorem to reduce exponents and efficiently compute a^n mod p for large n.

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:

  1. Divide the exponent: Write n = q(p-1) + r where 0 ≤ r < p-1
  2. Apply the theorem: a^n = a^(q(p-1) + r) = (a^(p-1))^q · a^r ≡ 1^q · a^r ≡ a^r (mod p)
  3. 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.