Fermat’s Little Theorem Calculator (check aᵖ⁻¹ ≡ 1 mod p, Fermat test)

Understanding the Fermat's little theorem calculator — concept and principle

This calculator checks Fermat's little theorem for a base a and a modulus p: it computes a^(p−1) mod p and a^p mod p exactly, tests whether p is prime, explains what the result shows, and gives the modular inverse of a when p is prime. Use it for number theory courses, cryptography basics and primality testing.

How it is calculated

Fermat's little theorem: if p is prime and p does not divide a, then a^(p−1) ≡ 1 (mod p); for every a, a^p ≡ a (mod p)

Powers are computed exactly by repeated squaring.

p is tested with a deterministic Miller–Rabin test.

For prime p, the inverse of a is a^(p−2) mod p.

The principle

Multiply each of 1, 2, …, p − 1 by a and reduce mod p: when p is prime and does not divide a, you get the same numbers in a different order. Multiplying all of them together on both sides gives a^(p−1) × (p − 1)! ≡ (p − 1)!, and cancelling (p − 1)! leaves a^(p−1) ≡ 1. The theorem works only one way: a result other than 1 proves p is composite, but a result of 1 does not prove p is prime, because pseudoprimes such as 341 = 11 × 31 (base 2) and Carmichael numbers such as 561 pass too.

Worked example

Default inputs: a = 3, p = 101.

1. a mod p = 3.
2. 3¹⁰⁰ mod 101 = 1, computed by repeated squaring.
3. 3¹⁰¹ mod 101 = 3, matching a^p ≡ a.
4. Is p prime? yes — p is prime, so the theorem holds as expected.
5. Inverse of 3 mod 101 = 3⁹⁹ mod 101 = 34; check: 3 × 34 = 102 ≡ 1.

How to read the result

A value of 1 with a prime p is the theorem in action. A value other than 1 is a certificate that p is composite, with a as a Fermat witness. A value of 1 with a composite p flags a Fermat pseudoprime. Modular inverses like 34 are used in RSA and other public-key methods.

Common mistakes

• Treating a^(p−1) ≡ 1 as proof that p is prime.
• Forgetting the condition that p must not divide a.
• Computing a^(p−1) in full before reducing, which overflows for large p.
• Confusing a^(p−1) ≡ 1 with a^p ≡ a.

Frequently asked questions

What does Fermat's little theorem say?

For a prime p not dividing a, a^(p−1) leaves remainder 1 when divided by p.

Can it prove a number is prime?

No. It can prove a number is composite, but some composite numbers also pass.

How do I find a modular inverse with it?

For prime p, the inverse of a is a^(p−2) mod p.

Sources: E. W. Weisstein, "Fermat's Little Theorem", Wolfram MathWorld