3
$\begingroup$

If we want to know if $n$ is prime, we can do the Fermat primality test:

if $a^{n-1}\not\equiv 1 \mod n$, then $n$ is not prime.

Now I often find that we choose therefore $a\in\{2,\ldots, n-2\}$. Why not $a=n-1$? In Wikipedia, I found that for $a=n-1$ the congruence always holds. Why?

$\endgroup$
2
$\begingroup$

If $n$ is odd (usually, this is assumed) and $a=n-1$, then we have $$(n-1)^{n-1}\equiv (-1)^{n-1}=1\mod n;$$ hence the criterion is satisfied whenever $n$ is odd.

$\endgroup$
1
$\begingroup$

For $n>2$, $(n-1)^{n-1}=k(n).n+(-1)^{n-1}$ where $k(n)$ is given by the rest of the terms via the binomial expansion. Since all prime numbers greater than 2 are odd, $n-1$ is even for all cases of interest. So, one has $(n-1)^{n-1}\equiv1\ (mod\ n)$, for odd $n$. So, you don't have to check this case.

$\endgroup$
  • $\begingroup$ All prime numbers except $2$ are odd; $2$ is an "odd" prime $\endgroup$ – J. W. Tanner Feb 19 at 16:23
  • $\begingroup$ You might clarify what you meant by $k(n)$ $\endgroup$ – J. W. Tanner Feb 19 at 16:24
1
$\begingroup$

Computational expense, and as others have mentioned it works for any odd number in that case. If n is say 200 bits(25 bytes) long, it will Take 625 byte multiplies, and about the same number of byte additions with carries, Just to implement in Karatsuba multiplication ( for 1 increase in power). It doesn't take much overhead to make one method slower than another in certain ranges. About the only use for it if too slow for primality is the:$$a^{-1}\equiv a^{n-2} \pmod n$$ version of the test.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.