Fermat primarility test

There is always a question whether a given integer is a prime number or not. Such question is easy to answer in case of some small integer – you can do it by hand or Google it, right? But what about an integer with, hmm, let’s say, a million of digits? Would you try to check all possible prime divisors? Well, that is actually one way to deal with such problem. However, it is extremely ineffective.

Therefore, we sometimes need to rely on some sort of probability and be satisfied with answers like “There is a 98.3 % chance that this number is prime”. It may look weird, but in practise it is the best way to handle this problem. This post deals with one of the most basic primarility test there is, namely the Fermat test.

Sources:

Theory:

Recall that \varphi(n) denotes the Euler function (i.e. the number of  integers that are less than n and relatively prime to n). There are two important theorems for us now:

  • Euler theorem: Let a,n\in\mathbb{N} such that gcd(a,n)=1. Then a^{\varphi(n)}\equiv 1 mod n.
  • Fermat’s little theorem: Let p be a prime, a\in\mathbb{N} and suppose that p does not divide a. Then a^{p-1}\equiv 1 mod p. Note that this is just a special case of the Euler theorem.
  • Computing the Euler function: If n=p_1^{k_1}\cdot...\cdot p_r^{k_r}, then

        \[\varphi(n)=p_1^{k_1-1}\cdot(p_1-1)\cdot...\cdot p_r^{k_r-1}\cdot(p_r-1).\]

The Test:

Let n\in\mathbb{N} be any number that we want to check whether it is prime or not. If we are able to find any a\in\mathbb{N} such that gcd(a,n)=1 and at the same time a^{n-1}\not\equiv 1 mod n, then n is not prime by Fermat’s little theorem – if it was, then the congruence would have to be satisfied.

So, the idea is to find one number a, so called witness, that proves that n is composite. Okay, great, seems logic. The natural question is whether for every composite number there is a witness. In other words, if we find no witness, is it true that n is necessarily prime? NO and NO!

There exist infinitely many numbers n such that for every a with gcd(a,n)=1 it holds that a^{n-1}\equiv 1 mod n and n is composite. They are called Carmichael numbers and the smallest of them is 561=3\cdot 11\cdot\17. Some other Carmichael numbers are 1105, 1729 or 2465.

Conclusion:

The idea behind the Fermat test is very simple. So simple, that it just doesn’t work. For infinitely many integers we are not able to decide whether they are prime or composite using only this test.

Fortunately, this test can be slightly modified in order to make it work for all integers. This way we get Rabin-Miller test, which we deal with in this post.

Examples:

EXAMPLE 1:

Compute \varphi(48).

Solution:

We know that 48=2^4\cdot 3, so by the last point of the Theory part we get that

    \[\varphi(48)=2^3\cdot(2-1)\cdot 3^0\cdot(3-1)=8\cdot 2=16.\]

Example 2:

Compute 2^{30} mod 5.

Solution:

Since gcd(2,5)=1, we can use Fermat’s little theorem to get that 2^4\equiv 1 mod 5. Therefore, 2^{30}=2^{28}\cdot 2^2=(2^{4})^7\cdot 4\equiv 1^7\cdot 4=4 mod 5.

Example 3:

Use Fermat primarility test to proof that n=4 is a composite number.

SOlution:

First of all, we need to find some natural number a such that gcd(a,4)=1. Well, there are only two such numbers modulo 4, namely a_1=1 and a_2=3. Obviously, a_1^{4-1}=1, which proves nothing, i.e., 1 is not a witness. What about 3? Well, 3^{4-1}=3^{3}=27\equiv 3\not\equiv 1 mod 4, so 4 is not a prime number and 3 is a witness proving it.

Problems:

Problem 0:

Watch this 7-minutes long video by Numberphile on Fermat’s little theorem, Fermat’s witnesses and Carmichael numbers to check whether you fully understand this topic.

Problem 1:

Compute \varphi(128).

Problem 2:

Compute (using Fermat’s little theorem) 11^{70} mod 3.

Problem 3:

Write a computer program in your favourite programming language to check that 561 satisfies the definition of a Carmichael number.

Problem 4:

Prove that 12 is not a prime number using Fermat test. Find all witnesses modulo 12.

Leave a Reply

Your email address will not be published. Required fields are marked *