Fermat primality test and Fermat pseudoprime What is the difference between Fermat primality test and Fermat pseudoprime?Can anyone explain me how we use them ?
 A: It is known that if $n$ is prime, then $a^{n-1} \equiv 1 \mod n$ for all $2 \le a \le n-1$. Reading this backwards, we get: if we can find some $a$ between $2$ and $n-1$ such that $a^{n-1} \not\equiv 1 \mod n$, then surely $n$ is not prime. If not, then $n$ is prime.
Therefore, you take the number $n$ to be tested and take $a=2$. If $2^{n-1} \not\equiv 1 \mod n$, then surely $n$ is not prime, and you stop. What happens if $2^{n-1} \equiv 1 \mod n$? In this case $n$ might or might not be a prime (it will be called a Fermat pseudoprime with base $2$) and you go to the next step.
If in the step above you obtained $2^{n-1} \equiv 1 \mod n$, then move on to $a=3$ and repeat the previous step as above. And so on, and so on, until you either find an $a$ with $a^{n-1} \not\equiv 1 \mod n$ (in which case $n$ will not be prime), or you exhaust the numbers between $2$ and $n-1$ and for each of them you get $a^{n-1} \equiv 1 \mod n$ (in which case $n$ will be prime).
Note that the above algorithm is very slow if $n$ happens to be a large prime.
Finally, a pseudoprime to base $a$ is a number $n$ such that $a^{n-1} \not\equiv 1 \mod n$, and yet $n$ is not prime.
