The statement
Fermat's little theorem says that for a prime modulus, any number not divisible by that prime, raised to the prime minus one, gives one under the modulus. Equivalently, the number raised to the prime gives back the number itself.
Two consequences
- Inverses. Since the number raised to the prime minus one is one, the number raised to the prime minus two is its modular inverse. This is the cleanest way to divide under a prime modulus.
- A primality hint. If raising some base to the candidate minus one does not give one, the candidate is definitely not prime. The reverse is not guaranteed, which is why stronger tests exist.
A caution
Some composite numbers pass the power test for many bases, so the theorem alone cannot confirm primality. It is a fast filter and a tool for inverses, not a proof of primeness by itself.
Key idea
Fermat's little theorem states that under a prime modulus a coprime base raised to the prime minus one is one, which yields modular inverses and a quick but not conclusive primality filter.