Free Fermat's Little Theorem Calculator

Understanding Fermat's Little Theorem

Fermat's Little Theorem is a cornerstone of elementary number theory, establishing a profound link between prime numbers and modular arithmetic. This theorem states that if $p$ is a prime and $a$ is any integer, then $a^{p} - a$ is always divisible by $p$. In the language of modular arithmetic, we write:

$$a^{p} \equiv a \pmod{p}$$

When $a$ is not a multiple of $p$ (i.e., $\gcd(a,p)=1$), the theorem can be simplified to:

$$a^{p-1} \equiv 1 \pmod{p}$$

This result is the foundation for many applications: primality testing, public‑key cryptography (like RSA), and computing modular inverses. While the Prime Number Theorem describes the asymptotic distribution of primes, Fermat's Little Theorem provides a concrete relationship that powers many modern algorithms. The modular arithmetic calculator based on Fermat's Little Theorem allows you to verify these congruences quickly.

Working with Examples

Let’s examine two concrete cases to see how the theorem behaves under different conditions.

Case 1: $a$ and $p$ coprime. Take $p=7$ and $a=15$. Since 15 is not divisible by 7, the second version applies:

$$15^{6} \equiv 1 \pmod{7}$$

Calculating: $15^{6} = 11,390,625$; subtract 1 yields $11,390,624$, which equals $7 \times 1,627,232$, confirming divisibility.

Case 2: $a$ divisible by $p$. Now consider $p=7$ and $a=14$. Here 14 is a multiple of 7, so we must use the original form:

$$14^{7} \equiv 14 \pmod{7}$$

Indeed, $14^{7} - 14 = 105,413,504$ is exactly $7 \times 15,059,070$, satisfying the congruence.

These examples illustrate the importance of checking the coprime condition before applying the shortened exponent form.

How to Use the Fermat's Little Theorem Calculator

The online Fermat's Little Theorem calculator — a dedicated mod calculator — simplifies the process of applying the theorem. To use it:

1. Enter the two integers $a$ and $p$.
2. The tool first verifies that $p$ is indeed prime (you can also pre‑check with a prime number checker).
3. It then checks whether $a$ and $p$ are coprime.
4. Based on these checks, it displays the appropriate version of the theorem and shows the resulting congruence.

This mod calculator is especially useful for quickly verifying modular relationships and for educational purposes.

Finding the Multiplicative Inverse Modulo $p$

One important application of Fermat's Little Theorem is computing the multiplicative inverse of an integer modulo a prime. From $a^{p-1} \equiv 1 \pmod{p}$, we can rewrite this as $a \cdot a^{p-2} \equiv 1 \pmod{p}$. Therefore, the inverse of $a$ modulo $p$ is $a^{p-2}$. The calculator can compute this exponentiation modulo $p$ efficiently, providing the modular inverse without complex calculations.

Using the Theorem for Primality Testing

Fermat's Little Theorem also offers a probabilistic primality test. To test whether a number $p$ is prime:

• Choose a random integer $a$ between 2 and $p-2$ such that $\gcd(a,p)=1$.
• Compute $a^{p-1} \bmod p$.
• If the result is not 1, then $p$ is definitely composite.
• If the result is 1, the test is inconclusive; try a different $a$.
• After several successful passes, $p$ is considered "probably prime."

While this test does not guarantee primality (some composites, called Carmichael numbers, may always pass), it provides a quick check. Combined with other tests, it forms the basis of many modern primality checks.

A Historical Perspective

Fermat first stated his "little" theorem in 1640 in a letter to Frénicle de Bessy, but he did not provide a proof. The first published proof came from Euler in 1736, though Leibniz had earlier discovered it privately. The theorem earned the nickname "little" to distinguish it from Fermat's Last Theorem, which concerns the equation $x^{n} + y^{n} = z^{n}$ and was finally proved by Andrew Wiles in 1995. Despite its humble name, Fermat's Little Theorem remains an essential tool in number theory and modern cryptography.

Conclusion

The Fermat's Little Theorem Calculator offers a convenient way to explore congruences and apply the theorem in various contexts, from finding modular inverses to testing primality. By understanding the statement and its conditions, you can leverage this powerful result in both theoretical and practical settings.