Armed with an understanding a theorem of Fermat and a calculator or software that can handle large numbers, any interested individual can carry out exercises in primality testing – checking whether or not a number is prime. No advanced study in number theory is required. In this post, we explain how this is done. This post is built on two previous posts on detecting composite numbers and the fast powering algorithm.
___________________________________________________________________________
Fermat’s Little Theorem
This is called the little theorem so that it is not confused with the other theorem of Fermat whose proof took three and a half centuries. The little theorem of Fermat describes a property that is possessed by all prime numbers. It says: if is a prime number, then a certain property is true for the number . Turning this around, if that property is not true for a number , that number must not be prime (i.e. it must be composite). This approach is a great way to prove the compositeness of a number. It is also a great way to gather evidence to support the primality of a number.
Two number are relatively prime to each other if they do not have any common factor that is greater than 1. For example, 28 is relatively prime to 15 even though neither one of them is prime. Similarly 17 and 35 have no factors in common. So they are relatively prime to each other.
The notation means that and differ by a multiple of , i.e. for some integer . The notation is read is congruent to modulo . The statement of Fermat’s theorem uses the notation . This would mean that for some integer . This means that divisible by .
Here’s the statement of Fermat’s little theorem.

Fermat’s Little Theorem
If is a prime number, then for all numbers that are relatively prime to .
___________________________________________________________________________
Fermat’s Test
The theorem says that if is a prime number, and and so on. The flip side is that if we can find a number such that , then we have convincing proof that is not a prime number.
When we need to determine whether or not a number is prime, we pick a value and calculate . If the calculated result is not 1, then we have a convincing proof that the number is not prime. If , then the number is said to be a probable prime to base . When is a probable prime to base , we also say that passes the Fermata test. Fermat’s little theorem can then be restated as:

Fermat’s Little Theorem
If is a prime number, then passes Fermata test for all possible choices of .
Example 1
This previous post discusses the following 204digit number.
34526903293921580314641092817369674040684481568423
96721012992064214519445919256941544565276067662360
10874972724155570842527652727868776362959519620872
73561220060103650687168112461098659687818073890148
6527
It can be verified that where is not 1 and is the following 203digit number.
33345811005959530251539697392827903173946066773819
70645616725285996925661000056829272733579262095715
97827398131150054514508640724258354848985651127636
92970799269335402819507605691622173717318335512037
458
The number in this example fails the Fermat2 test and is thus a composite number. The calculation of is carried out by using the fast powering algorithm.
Example 2
Consider 982447387. Is it prime?
Calculate for several values of . let’s start with 2. We find that . So we say that the number is a probable prime to base 2. It is very likely that is a prime. Let’s try a few more values of . We have the following results.
Now is a probable prime to the bases 2, 3, 5, and 7. It turns out that there are actually composite numbers that are probable primes to bases 2, 3, 5 and 7. But they are extremely rare. So the number is a probable prime (meaning that the chance that it is not a prime is very negligible). For good measure, we generate 5 random values of . They are:

323064262
866079494
599071122
773037193
247321577
Calculating for all 5 values show that the number passes the Fermata test for all 5 values of . At this point we are willing to conclude that is a prime. The conclusion is based on a probability argument and is not based on a mathematical proof.
Since the number is a 9digit number, we can actually conclude that it is a prime by looking it up in lists of primes that are published online. So this is a toy example that is meant for illustration only.
___________________________________________________________________________
Remarks
Example 1 shows that failing the Fermata test just for one value of is enough to conclude that the number in question is not prime. In general, to test the primality of a number , carry out the Fermata test for several values of (preferably randomly chosen). If fails the Fermata test for one of the values of , then is composite. On the other hand, if passes the Fermata test for all the chosen values of , then is a probable prime.
The Fermat test is the “entry level” primality test. It is easy to use. It often works correctly. But it can produce incorrect results on rare occasions. For a more in depth discussion of the Fermat’s primality test, we refer you to an article in another blog.
___________________________________________________________________________