Fermat's Little Theorem Calculator

About the Fermat's Little Theorem Calculator

**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 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.

When This Page Helps

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.

How to Use the Inputs

1. Enter a base value a and a prime modulus p.
2. Optionally enter a custom exponent (defaults to p−1).
3. Click a preset button to load a classic example.
4. Review output cards for the result, primality verdict, and GCD.
5. Examine the computation steps table for the binary exponentiation process.
6. Check the properties reference for related theorems and corollaries.

Example Calculation

Tips & Best Practices

• Check that all inputs use the same scale and assumptions before trusting the result.
• Compare the answer with the worked example or a rough estimate to catch entry mistakes.

How the Theorem Works

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.

Primality Testing and Carmichael Numbers

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.

Applications in Cryptography

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.

Frequently Asked Questions

• What is Fermat's little theorem?

  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.

• How is it used for primality testing?

  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.

• What is a Carmichael number?

  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.

• What is modular exponentiation?

  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.

• How does this relate to RSA?

  RSA relies on Euler's theorem (a generalization of Fermat's) to ensure that encryption and decryption are inverses of each other.

• What if a and p are not coprime?

  If p divides a, then a^(p−1) mod p = 0, not 1. The theorem only applies when gcd(a, p) = 1.

• What is Euler's generalization?

  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.