Fermat's Theorem Applications

Number Theory · Axiom Academy

EXAMPLE Fermat's Theorem Applications Computing large powers modulo primes using Fermat's Little Theorem Excellent work! You've completed this example using Fermat's Little Theorem. Here's what we learned: Fermat's Little Theorem: If p is prime and gcd( a , p ) = 1, then a p -1 ≡ 1 (mod p ). This is an incredibly powerful tool for simplifying large exponentials. Division Algorithm: We can always write any exponent n as n = q ( p -1) + r where 0 ≤ r p -1. This lets us reduce the problem to computing a r mod p . Modular Reduction: When computing powers, we can reduce intermediate results modulo p at any step. This keeps numbers manageable. Practical Application: Without FLT, computing 3 100 directly would be extremely difficult. FLT reduces this to just computing 3 4 = 81, which easily reduces to 4 (mod 7). This technique is fundamental in cryptography and number theory. Practice with different bases and primes to build confidence!

This is the written version of the interactive lesson above. See the full Number Theory course.