Fermat's Little Theorem

Number Theory · Axiom Academy

LESSON Fermat's Little Theorem One of the foundational results in number theory and modular arithmetic Fermat's Little Theorem states: If p is a prime number and a is an integer such that gcd(a, p) = 1 (meaning a is not divisible by p ), then: This can also be written in an alternative form that holds for all integers a : Let's explore this theorem with concrete examples. Consider p = 7 (a prime) and a = 2 . According to Fermat's Little Theorem, we should have: The powers of 2 modulo 7 cycle through values, but crucially, the (p-1)th power always equals 1 modulo p. Fermat's Little Theorem has numerous practical applications in mathematics and computer science: 1. Computing Modular Inverses: From the theorem, we know that a p-1 ≡ 1 (mod p), which means: So a p-2 is the modular multiplicative inverse of a modulo p . To compute large powers like a 1000 mod p, we can reduce the exponent:

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