Verify Fermat's little theorem, compute a^(p-1) mod p, perform modular exponentiation, check primality, view computation steps, and explore theorem properties with presets.
**Fermat's Little Theorem Calculator** lets you explore one of the cornerstones of number theory and modern cryptography. The theorem states that if p is a prime number and a is any integer not divisible by p, then a^(p−1) ≡ 1 (mod p). This elegant result, first stated by Pierre de Fermat in 1640, underpins primality testing algorithms and the RSA cryptosystem.
Enter a base value a and a modulus p, and this calculator instantly computes a^(p−1) mod p using fast modular exponentiation (binary method). If the result is 1 and p is indeed prime, the theorem is verified. If the result is not 1, then p is definitely composite — giving you a quick (though not foolproof) primality test.
The tool also computes arbitrary modular exponentiations a^e mod m for any exponent e and modulus m you choose, not just the p−1 case. A step-by-step breakdown shows the binary expansion of the exponent and the squaring-and-multiplying process at each bit, making it an excellent learning resource for understanding how computers perform modular arithmetic efficiently.
Preset buttons load classic examples including small primes, Carmichael numbers (pseudoprimes that fool the Fermat test), and large values used in cryptographic contexts. A properties reference table lists key corollaries and related theorems, while the computation steps table shows every intermediate result. Whether you are a student learning abstract algebra, preparing for a competition, or studying cryptographic protocols, this calculator makes Fermat's little theorem concrete and interactive.
Modular exponentiation with large numbers is impractical by hand — computing 2^100 mod 101 requires either a clever shortcut or a computer. This calculator verifies Fermat's little theorem step by step, showing the intermediate squaring operations so you can follow the binary exponentiation method. It also tests whether a number passes the Fermat primality test and flags Carmichael numbers that fool the basic test. Cryptography students use it to understand the RSA underpinnings, while competitive programmers use it to check modular inverse computations.
If p is prime and gcd(a, p) = 1, then a^(p−1) ≡ 1 (mod p). Equivalently, a^p ≡ a (mod p) for all a.
Result: 2
Let a = 2, p = 7. Then 2^6 mod 7 = 64 mod 7 = 1 ✓. Since the result is 1 and 7 is prime, Fermat's theorem holds.
Fermat's little theorem states that if p is prime and a is not divisible by p, then a^(p−1) ≡ 1 (mod p). The proof relies on the fact that multiplying the set {1, 2, …, p−1} by a (mod p) simply permutes the set, so the products are equal — leading to a^(p−1) ≡ 1 after cancellation. This elegant argument generalises to Euler's theorem using the totient function.
The Fermat test works by checking whether a^(n−1) ≡ 1 (mod n) for random bases a. If it fails, n is definitely composite. However, Carmichael numbers (561, 1105, 1729, …) pass the test for every coprime base, making the basic Fermat test probabilistic rather than deterministic. The Miller–Rabin test refines this by also checking square roots of 1, eliminating most Carmichael-number false positives.
RSA encryption chooses e and d such that ed ≡ 1 (mod φ(n)), ensuring that (m^e)^d ≡ m (mod n) by Euler's theorem. Fermat's little theorem is the special case that makes textbook RSA examples tractable: choosing small primes p and q lets students verify the entire encrypt–decrypt cycle by hand. Modular exponentiation via repeated squaring — the algorithm this calculator demonstrates — is the same routine used in production RSA implementations.
If p is prime and a is not divisible by p, then a^(p−1) ≡ 1 (mod p). It connects prime numbers to modular arithmetic.
If a^(p−1) mod p ≠ 1, then p is definitely composite. However, the converse is not always true — some composites (Carmichael numbers) pass the test.
A composite number n where a^(n−1) ≡ 1 (mod n) for all a coprime to n. Examples: 561, 1105, 1729. They fool the basic Fermat test.
Computing a^e mod m efficiently using the binary method: square and multiply based on the bits of e, reducing mod m at each step. Use this as a practical reminder before finalizing the result.
RSA relies on Euler's theorem (a generalization of Fermat's) to ensure that encryption and decryption are inverses of each other. Keep this note short and outcome-focused for reuse.
If p divides a, then a^(p−1) mod p = 0, not 1. The theorem only applies when gcd(a, p) = 1.
Euler's theorem says a^φ(n) ≡ 1 (mod n) for any n when gcd(a, n) = 1, where φ is Euler's totient function. Fermat's theorem is the special case where n is prime and φ(p) = p−1.