Fermat Little Theorem
Fermat's little theorem: if p is prime and gcd(a,p)=1, then a^(p-1)≡1 (mod p); it underpins primality testing and modular inverses.
Purpose
To provide fast modular-exponentiation simplification and the theoretical basis for primality testing.
Mechanism
a^(p-1)≡1 (mod p) implies a^(-1)≡a^(p-2) (mod p) (modular inverse). Fermat primality test: pick a random a and check a^(n-1)≡1 (mod n); failure proves n composite. However, Carmichael numbers pass all Fermat tests.
Use cases
- Primality testing
- Modular inverse computation
- Cryptographic foundations
Related tools
Prime Checker
Prime Checker — pure client-side tool. Privacy-first, no server round-trip. TOOL
Modular Exponentiation
Modular Exponentiation — pure client-side tool. Privacy-first, no server round-trip. TOOL
Lucas Primality Test
Lucas Primality Test — pure client-side tool. Privacy-first, no server round-trip. Warning: current implementation uses plain trial division (equivalent to prime-checker), not the real Lucas primality test with Lucas sequences. TOOL