Fermat's Little Theorem Calculator
Enter a base a and a candidate prime p to compute a^(p−1) mod p. If the result is 1, p passes Fermat's test for this witness; the calculator also confirms whether p is truly prime and derives the modular inverse a⁻¹ (mod p) = a^(p−2) mod p when p is prime.
Result is 1 — theorem confirmed: p is prime and gcd(a, p) = 1
Fermat's theorem: if p is prime and gcd(a, p) = 1:
Substitute values:
Result — theorem holds:
- 1
Exponent e = p − 1
e = 13 − 1 = 12 - 2
gcd(a, p)
gcd(7, 13) = 1 - 3
aᵉ mod p
7^12 mod 13 = 1
How does this calculator work?
Fermat's little theorem: for prime p and gcd(a, p) = 1, a^(p−1) ≡ 1 (mod p). Compute with binary exponentiation using BigInt. If result ≠ 1, p is definitely composite. If result = 1, p passes the Fermat test — but Carmichael numbers can fool it, so the calculator adds a deterministic Miller–Rabin check. When p is prime, a^(p−2) mod p gives the modular inverse of a.
Formula
How this is calculated
Fermat's little theorem states that if p is a prime and a is any integer not divisible by p, then a^(p−1) is congruent to 1 modulo p. Equivalently, a^p ≡ a (mod p) for any integer a. The theorem is one of the fundamental results of modular arithmetic and underlies the RSA cryptosystem, Miller–Rabin primality testing, and fast computation of modular inverses.
This calculator uses binary exponentiation (exponentiation by squaring) with JavaScript BigInt to compute a^(p−1) mod p exactly, without overflow, for any p up to 10^15. Primality is checked with a deterministic variant of the Miller–Rabin test using the witness set {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}, which gives correct results for all integers below approximately 3.3 × 10^24 — far larger than the input limit.
When p is prime and gcd(a, p) = 1, the modular inverse of a mod p is given by a^(p−2) mod p — a direct consequence of the theorem, since a × a^(p−2) ≡ a^(p−1) ≡ 1 (mod p). One critical caveat: a^(p−1) ≡ 1 (mod p) for a composite p does NOT prove primality. Composite numbers that pass Fermat's test are called Fermat pseudoprimes; those that pass for every base coprime to them are Carmichael numbers (e.g., 561, 1105, 1729). The deterministic Miller–Rabin check used here correctly identifies all Carmichael numbers as composite.
Frequently asked questions
It means p is definitively not prime — the base a is a Fermat witness proving compositeness. Any single witness that produces a result other than 1 is sufficient proof that p is composite.
Yes. Composite numbers called Fermat pseudoprimes pass the test for particular bases. Carmichael numbers — such as 561, 1105 and 1729 — pass for every base coprime to them. The Miller–Rabin primality check used here is immune to this weakness.
Fermat's theorem gives a^(p−1) ≡ 1 (mod p), which can be rewritten as a × a^(p−2) ≡ 1 (mod p). That is exactly the definition of a multiplicative inverse modulo p. This trick only works when p is prime; for composite moduli, use the extended Euclidean algorithm instead.
Also known as
TG we-Calculate Editorial Team. (2026). Fermat's Little Theorem Calculator [Online calculator]. TG we-Calculate. https://we-calculate.com/calculator/fermats-little-theorem-calculator
TG we-Calculate Editorial Team. "Fermat's Little Theorem Calculator." TG we-Calculate. 2026. https://we-calculate.com/calculator/fermats-little-theorem-calculator.
TG we-Calculate Editorial Team, "Fermat's Little Theorem Calculator," TG we-Calculate, 2026. [Online]. Available: https://we-calculate.com/calculator/fermats-little-theorem-calculator
@misc{wecalculate_fermats_little_theorem_calculator, title = {Fermat's Little Theorem Calculator}, author = {{TG we-Calculate Editorial Team}}, howpublished = {\url{https://we-calculate.com/calculator/fermats-little-theorem-calculator}}, year = {2026}, note = {TG we-Calculate} }
Did this calculator help you?