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.
Recall that denotes the Euler function (i.e. the number of integers that are less than and relatively prime to ). There are two important theorems for us now:
- Euler theorem: Let such that . Then mod .
- Fermat’s little theorem: Let be a prime, and suppose that does not divide . Then mod . Note that this is just a special case of the Euler theorem.
- Computing the Euler function: If , then
Let be any number that we want to check whether it is prime or not. If we are able to find any such that and at the same time mod , then 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 , so called witness, that proves that 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 is necessarily prime? NO and NO!
There exist infinitely many numbers such that for every with it holds that mod and is composite. They are called Carmichael numbers and the smallest of them is . Some other Carmichael numbers are or .
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.
We know that , so by the last point of the Theory part we get that
Compute mod .
Since , we can use Fermat’s little theorem to get that mod . Therefore, mod .
Use Fermat primarility test to proof that is a composite number.
First of all, we need to find some natural number such that . Well, there are only two such numbers modulo , namely and . Obviously, , which proves nothing, i.e., is not a witness. What about ? Well, mod , so is not a prime number and is a witness proving it.
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.
Compute (using Fermat’s little theorem) mod .
Write a computer program in your favourite programming language to check that satisfies the definition of a Carmichael number.
Prove that is not a prime number using Fermat test. Find all witnesses modulo .