If $2^x\bmod x = 2$, how does that prove that $x$, a prime number, is prime?

Question

I saw this on l. 13 of this code here.

I don't have a degree in maths but have read about Fermat's Theorem (which a comment below prompted me to remember), and have done first year university calculus and algebra, plus self-study of maths related to cryptography.

it does not generally prove it, but what is true is that if $p$ is prime then indeed $a^p \equiv a \pmod p$ (Fermat's little theorem). The converse does not always hold, but the idea is the basis of some more sophisticated primality tests. — Tob Ernack, Jan 08 '18 at 23:38
A counterexample for the converse would be any Carmichael number (for example $561$ is not prime but $2^{561} \equiv 2 \pmod {561})$. — Tob Ernack, Jan 08 '18 at 23:41

Robert Soupe · Accepted Answer · 2018-01-09T16:58:26.253

If you already know that $x$ is a prime number, then $2^x \equiv 2 \bmod x$ merely confirms it. But if you don't know that it is or it isn't, satisfying the congruence is a pretty decent indicator.

Among the first thousand positive integers, 170 integers that are odd satisfy the congruence, but there are only 167 primes that are odd between 1 and 1000. Which means that three odd composite numbers were falsely flagged prime by our test: 341, 561, 645.

That's a failure rate of less than 1%. And if you put those three "false primes" into Sloane's OEIS, the first result will be

A001567 Fermat pseudoprimes to base 2, also called Sarrus numbers or Poulet numbers. (Formerly M5441 N2365)

http://oeis.org/A001567

Also note that the fortieth number listed there is 29341, and $\pi(29341) = 3188$. ~~So the failure rate has gone up almost to 11%.~~ Depending on your application, that might be perfectly acceptable.

EDIT, January 9: I got a little confused with directions of percentages yesterday. Sorry about that.

OK so there is a small probability that it may not actually be prime. I had to remind myself what the Pi function was. https://en.wikipedia.org/wiki/Prime-counting_function. "So the failure rate has gone up almost to 11%." $40/3188 = 0.0125$. Perhaps you mean almost by 11%. $3/170 = 0.0176$. But it has actually gone down. — James Ray, Jan 09 '18 at 05:51

If $2^x\bmod x = 2$, how does that prove that $x$, a prime number, is prime?

1 Answers1