If $2^x\bmod x = 2$, how does that prove that $x$, a prime number, is prime? 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.
 A: 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.
