Fermat's Little Theorem Solver

Understanding Fermat's Little Theorem

Fermat's Little Theorem stands as a pillar in elementary number theory. It states that for any prime number p and any integer a, the value of a^p - a is always divisible by p. Expressed in modular arithmetic notation, this is:

a^p ≡ a (mod p)

A particularly useful corollary applies when a is not a multiple of p (i.e., a and p are coprime):

a^(p-1) ≡ 1 (mod p)

Practical Applications and Examples

Seeing the theorem in action clarifies its use. Let's examine a couple of concrete examples.

Example 1: Coprime Condition

Consider p = 7 and a = 15. Since 15 is not divisible by 7, the theorem assures us that 15^(7-1) ≡ 1 (mod 7). A quick calculation confirms that 15^6 - 1 = 11,390,624, which is indeed a multiple of 7.

Example 2: General Form

It's crucial to verify the theorem's preconditions. For p = 7 and a = 14, the numbers are not coprime. Therefore, the a^(p-1) ≡ 1 form does not apply. Instead, we use the general form a^p ≡ a (mod p). We find that 14^7 - 14 is divisible by 7, confirming the theorem's primary statement.

Why is it Called the "Little" Theorem?

The "little" designation distinguishes this theorem from Fermat's more famous Last Theorem. The Last Theorem, a legendary problem stating that no three positive integers satisfy x^n + y^n = z^n for n>2, remained unproven for centuries until Andrew Wiles' proof in 1995. In contrast, the Little Theorem, while profound, has a more straightforward application and proof, hence its modest nickname.

Finding a Modular Multiplicative Inverse

You can leverage Fermat's Little Theorem to compute the multiplicative inverse of an integer a modulo a prime p. Provided p is prime and a is not a multiple of p, the theorem states a^(p-1) ≡ 1 (mod p). This can be rewritten as:

a × a^(p-2) ≡ 1 (mod p)

Consequently, the multiplicative inverse of a modulo p is precisely a^(p-2). This provides a direct computational method using modular exponentiation.

Primality Testing with Fermat's Theorem

This theorem also offers a probabilistic test for primality. To check if a number p might be prime:

1. Choose a random integer a between 2 and p-2.
2. Compute a^(p-1) mod p.
3. If the result is anything other than 1, p is definitively composite.
4. If the result is 1, it suggests p could be prime, and the test should be repeated with different a values.
5. After many repetitions without a definitive composite result, p is considered a probable prime.

Frequently Asked Questions