Fermat's Little Theorem Calculator

Fermat's Little Theorem states that if p is a prime number and a is an integer not divisible by p, then a^(p-1) ≡ 1 (mod p). Equivalently, a^p ≡ a (mod p) for any integer a. This is a fundamental result in number theory with applications in cryptography and primality testing.

The theorem holds only when p is prime. If p is composite (not prime), the congruence a^(p-1) ≡ 1 (mod p) may still hold for some values of a, but not all. Numbers that pass the Fermat test for all bases coprime to n are called Carmichael numbers — they are composite but fool the basic Fermat primality test.

If p is prime and gcd(a,p) = 1, then the modular inverse of a modulo p is a^(p-2) mod p. This follows from a^(p-1) ≡ 1 (mod p), which means a × a^(p-2) ≡ 1 (mod p). So a^(p-2) is the multiplicative inverse of a modulo p.

The modular inverse of a modulo m is an integer x such that a × x ≡ 1 (mod m). It exists only when gcd(a,m) = 1. For example, the modular inverse of 3 mod 7 is 5, because 3 × 5 = 15 ≡ 1 (mod 7).

RSA encryption uses modular exponentiation and relies on the difficulty of factoring large numbers. Fermat's Little Theorem (and its generalization, Euler's theorem) ensures that decryption works correctly: encrypting with exponent e and decrypting with exponent d = e^(-1) mod (p-1)(q-1) recovers the original message because m^(ed) ≡ m (mod n).

This calculator uses Fermat's Little Theorem as a heuristic primality test. If a^(p-1) mod p ≠ 1 for some base a coprime to p, then p is definitely composite. However, passing the test for one base does not guarantee primality — Carmichael numbers can fool the test. For definitive primality, use the Miller-Rabin test.

Fermat's Little Theorem applies specifically when the modulus p is prime: a^(p-1) ≡ 1 (mod p). Euler's Theorem is the generalization: a^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function (count of integers from 1 to n coprime to n). When n is prime, φ(n) = n-1, so Euler's Theorem reduces to Fermat's.

Applications include: (1) Fast modular exponentiation in cryptography, (2) Primality testing (Fermat test), (3) Computing modular inverses efficiently, (4) Simplifying number theory problems, (5) RSA key generation and encryption/decryption operations.

Use modular exponentiation (repeated squaring). Instead of computing a^b directly and then taking mod m (which creates enormous numbers), repeatedly square and multiply while taking mod m at each step. For example, 3^13 mod 7: 3^1 = 3, 3^2 = 2, 3^4 = 4, 3^8 = 2, then 3^13 = 3^8 × 3^4 × 3^1 = 2 × 4 × 3 = 24 mod 7 = 3.

Carmichael numbers are composite numbers n that satisfy a^(n-1) ≡ 1 (mod n) for all integers a coprime to n. They are 'absolute Fermat pseudoprimes' that fool the Fermat primality test. The smallest Carmichael number is 561 = 3 × 11 × 17. There are infinitely many, and they become more common as numbers get larger.

The Fermat's Little Theorem Calculator uses standard mathematical formulas validated against authoritative references. The specific formula is displayed in the calculator interface with a detailed explanation of each variable.

Each calculator includes a step-by-step worked example showing exactly how the formula is applied. You can follow these steps with pen and paper to verify any result.

The Fermat's Little Theorem Calculator accepts numeric inputs including integers and decimals. Invalid inputs (letters, special characters) are rejected with clear error messages.