3
1
1
1
4
6
1
5
3
1
1
1
4
6
1
5
The Fermat's Little Theorem Calculator demonstrates and applies one of the foundational results in number theory. Fermat's Little Theorem states: if $$p$$ is a prime number and $$a$$ is any integer not divisible by $$p$$, then $$a^{p-1} \equiv 1 \pmod{p}$$. Equivalently, for any integer $$a$$: $$a^p \equiv a \pmod{p}$$.
Pierre de Fermat stated this result in a letter to Frénicle de Bessy in 1640, but characteristically provided no proof. The first published proof came from Euler in 1736, who later generalized it to composite moduli via what we now call Euler's theorem. The theorem has an elegant proof using group theory: the non-zero residues modulo $$p$$ form a group of order $$p - 1$$ under multiplication, and by Lagrange's theorem, the order of every element divides the group order.
This calculator applies the theorem in its most practical form: efficient modular exponentiation. To compute $$a^k \bmod p$$ where $$k$$ may be enormous, first reduce the exponent: since $$a^{p-1} \equiv 1 \pmod{p}$$, we have $$a^k \equiv a^{k \bmod (p-1)} \pmod{p}$$. This reduces a potentially huge exponent to a value less than $$p - 1$$.
A key corollary gives modular inverses. Setting $$k = p - 2$$: $$a \cdot a^{p-2} = a^{p-1} \equiv 1 \pmod{p}$$, so $$a^{-1} \equiv a^{p-2} \pmod{p}$$. This provides a straightforward method for computing modular inverses without the extended Euclidean algorithm.
Fermat's Little Theorem also underlies primality testing. The Fermat primality test checks whether $$a^{n-1} \equiv 1 \pmod{n}$$ for random bases $$a$$. If this congruence fails, $$n$$ is definitely composite. If it holds for many bases, $$n$$ is probably prime — though Carmichael numbers (pseudoprimes to all coprime bases) are the rare exceptions that fool this test, motivating more sophisticated tests like Miller-Rabin.
In RSA cryptography, the relationship between Fermat's theorem and Euler's theorem ensures that decryption recovers the original message. The public and private exponents $$e$$ and $$d$$ satisfy $$ed \equiv 1 \pmod{\lambda(n)}$$, where $$\lambda$$ is the Carmichael function — a refinement of Euler's totient that captures the exact exponent needed.
The calculator verifies Fermat's Little Theorem and uses it for efficient modular exponentiation.
Step 1: Verify primality. Check that $$p$$ is prime by trial division with small primes up to 47.
Step 2: Reduce the base. Compute $$a' = a \bmod p$$. If $$a' = 0$$, then $$p \mid a$$ and the theorem does not apply (but $$a^k \equiv 0$$ for all $$k \geq 1$$).
Step 3: Verify the theorem. Compute $$a^{p-1} \bmod p$$. By Fermat's theorem, this should equal 1 when $$p$$ is prime and $$\gcd(a, p) = 1$$.
Step 4: Reduce the exponent. $$k' = k \bmod (p-1)$$. Since $$a^{p-1} \equiv 1$$, powers of $$a$$ repeat with period dividing $$p-1$$:
$$a^k \equiv a^{k \bmod (p-1)} \pmod{p}$$
Step 5: Compute $$a^{k'} \bmod p$$.
Step 6: Compute modular inverse. $$a^{-1} \equiv a^{p-2} \pmod{p}$$.
Is p Prime? — Fermat's Little Theorem applies only when the modulus is prime. If $$p$$ is composite, the congruence $$a^{p-1} \equiv 1$$ may still hold for some bases (pseudoprimes) but is not guaranteed.
a mod p is the reduced base. If this is 0, then $$p$$ divides $$a$$ and the theorem's hypothesis $$\gcd(a,p) = 1$$ is not met.
a^(p−1) mod p should be 1 when the theorem applies. This is the core verification of the theorem.
k mod (p−1) is the reduced exponent. Fermat's theorem allows us to replace any exponent $$k$$ with its residue modulo $$p-1$$.
a^k mod p is the final modular exponentiation result using the reduced exponent.
Modular inverse $$a^{p-2} \bmod p$$ satisfies $$a \cdot a^{-1} \equiv 1 \pmod{p}$$.
Inputs
Results
3^6 = 729 ≡ 1 (mod 7) ✓. For k=100: 100 mod 6 = 4, so 3^100 ≡ 3^4 = 81 ≡ 4 (mod 7). Inverse: 3^5 = 243 ≡ 5 (mod 7), and 3×5 = 15 ≡ 1 (mod 7) ✓.
Inputs
Results
By Fermat, 2^12 ≡ 1 (mod 13). So 2^1000 ≡ 2^(1000 mod 12) = 2^4 = 16 ≡ 3 (mod 13). Without the theorem, computing 2^1000 directly would be impractical.
Fermat's Little Theorem does not hold for composite moduli in general. However, Euler's generalization states $$a^{\varphi(n)} \equiv 1 \pmod{n}$$ for any $$n$$ when $$\gcd(a,n) = 1$$, where $$\varphi$$ is Euler's totient function. For prime $$p$$, $$\varphi(p) = p-1$$, recovering Fermat's theorem as a special case.
Carmichael numbers are composite numbers $$n$$ where $$a^{n-1} \equiv 1 \pmod{n}$$ for all $$a$$ coprime to $$n$$. The smallest is 561 = 3 × 11 × 17. These pseudoprimes fool the basic Fermat primality test, which is why more robust tests like Miller-Rabin are preferred in practice.
RSA uses $$n = pq$$ where $$p, q$$ are large primes. The encryption exponent $$e$$ and decryption exponent $$d$$ satisfy $$ed \equiv 1 \pmod{\varphi(n)}$$. When you encrypt $$m^e$$ and decrypt $$(m^e)^d = m^{ed}$$, Euler's theorem (the generalization of Fermat's) guarantees $$m^{ed} \equiv m \pmod{n}$$.
The exponent reduction $$k \bmod (p-1)$$ always works correctly. The limitation is in the final computation $$a^{k'} \bmod p$$ where $$k' < p-1$$. For small primes ($$p < 100$$), intermediate results stay within JavaScript's exact integer range. For large primes, repeated squaring would be needed, which requires a loop not available in this expression-based engine.
A primitive root modulo $$p$$ is an integer $$g$$ whose powers generate all non-zero residues: $$\{g^1, g^2, \ldots, g^{p-1}\} = \{1, 2, \ldots, p-1\} \pmod{p}$$. The order of $$g$$ is exactly $$p-1$$. Every prime has at least one primitive root. The number of primitive roots modulo $$p$$ is $$\varphi(p-1)$$.
By Fermat's Little Theorem, $$a \cdot a^{p-2} = a^{p-1} \equiv 1 \pmod{p}$$, so $$a^{-1} \equiv a^{p-2} \pmod{p}$$. This is an alternative to the extended Euclidean algorithm. For example, $$3^{-1} \bmod 7 = 3^5 \bmod 7 = 243 \bmod 7 = 5$$, and indeed $$3 \times 5 = 15 \equiv 1 \pmod{7}$$.
Roboculator Team
The Roboculator Team explains calculations, planning tools, and practical formulas in clear language for real-life situations.
How helpful was this calculator?
Be the first to rate!
