Fermat's Little Theorem Calculator

Fermat's little theorem calculator will teach you all there is about this famous result in elementary number theory. Read on to find out:

• What Fermat's little theorem is about and why it's called "little";
• How to perform primality test using this theorem;
• How to use Fermat's little theorem to find the multiplicative inverse modulo; and
• When was Fermat's little theorem proved — and was it Fermat's achievement?

We'll also see examples of Fermat's little theorem applied to concrete numbers. Enjoy!

Fermat's little theorem is one of the fundamental results of number theory. It says that if p is a prime number and a is an integer, then a^p – a is divisible by p. In modulo notation:

a^p ≡ a (mod p)

In particular, if a is not divisible by p, then:

a^p-1 ≡ 1 (mod p)

Once we know what Fermat's little theorem is, let's see how it works in practice. We'll go together through some examples of Fermat's little theorem applied to concrete numbers.

Example 1

Let's consider p = 7 and a = 15. a is not divisible by p, so the theorem says that

15^7-1 = 15⁶ ≡ 1 (mod 7)

Indeed, we have

15⁶ – 1 = 11390624 = 7 × 1627232

Example 2

Be careful to check the assumptions! If p = 7 and a = 14, then 14⁶ is not equal to 1 modulo 7:

14⁶ – 1 ≡ 6 (mod 7)

This is because 14 and 7 are not coprime — 14 is divisible by 7. So, we should use the version of Fermat's little theorem for non-coprime numbers — the one that states a^p ≡ a (mod p):

14⁷ ≡ 14 (mod 7)

Indeed:

14⁷ – 14 = 7 × 15059070

Omni's calculator for Fermat's little theorem is really simple to use:

1. Our tool accepts two inputs: the integers a and p.

2. Remember that p must be a prime number. You can use Omni's prime number calculator to verify if the number you want to enter is prime. If it is not, our Fermat's little theorem calculator will display a warning and refuse to cooperate further.

3. Our calculator will also check if your numbers are coprime to decide which version of Fermat's last theorem is appropriate.

4. In either case, the statement of Fermat's little theorem applied to your input will appear.

To find the multiplicative inverse of a modulo p using Fermat's little theorem:

1. Write the claim of Fermat's little theorem as a^p-1 ≡ 1 (mod p).
2. Recall the assumptions: p must be prime and a must not be a multiple of p.
3. Verify that your numbers satisfy these assumptions.
4. Rewrite the claim a × a^p-2 ≡ 1 (mod p).
5. That is, the multiplicative inverse of a modulo p is equal to a^p-2.

To check if p is a prime number using Fermat's little theorem:

1. Pick a random integer a ∈ {2, ... p-2} not divisible by p.
2. Compute a^p-1 (mod p).
3. If the result is not 1, then p is definitely not prime.
4. If the result is equal to 1, then we choose a different a and repeat the procedure from Step 2.
5. If the test cannot decide after many repetitions, then p is probably prime.

The answer is 8. This is because Fermat’s little theorem tells us that 19¹¹ ≡ 19 (mod 11). We can further calculate that 19 = 1 × 11 + 8, which means that 19 (mod 11) ≡ 8, as claimed.

When using Fermat’s little theorem, always remember to verify the assumptions! We could use this theorem here since 11 is a prime number.

Fermat formulated his "little" theorem in October 1640 in a letter to his friend Frénicle de Bessy. However, he did not provide a proof, saying that he would gladly have attached it "if I did not fear its being too long". The first proof was published by Euler in 1736, but it turned out that Leibniz had found the same proof sometime before 1683 but kept it in an unpublished manuscript.