25. Most people have heard of Fermat's Last Theorem, but fewer people have heard of his Little Theorem. What is it?
From Quiz Quod Erat Demonstrandum
Answer:
If p is prime then, for any integer a, ap = a (mod p).
This theorem is the motor behind the Fermat Primality Test. The Fermat Primality Test can say for certain that a number is not prime, but can only give a probability that something is prime. Say you want to see whether 319 is prime. Pick an a less than 319, say 101. So a=101 and p=319. 101^319 ≡ 182 (mod 319), so we can conclude that 319 is not prime (because our result was 182 and it should have been 101). It turns out that 11*29 = 319. Now let's test to see whether 317 is prime. We'll use 101 again. 101^317 ≡ 101 (mod 317). So far so good. Let's try another value for a, such as a = 251. 251^317 ≡ 251 (mod 317). Let's check one more, say a = 299. 299^317 ≡ 299 (mod 317). So we can conclude that 317 is probably prime, because Fermat's Test worked for three random, unrelated integers. It turns out that 317 is prime. However, it could have been the case that I was just lucky with my selections. There are times when a^p ≡ a (mod p) holds even when p is not prime. An example of this (from Wikipedia) is p=221 and a=38. The above equation is true even though 221 is composite. (It's 13*17.)
Note that if a is larger than p, you will have to take into account the fact that there exists b such that a ≡ b (mod p) and 0 ≤ b ≤ p. For instance, take p=2 and a=3. 3^2 ≡ 1 (mod 2). This may raise a red flag, but remember that 3 ≡ 1 (mod 2), so by the transitive property, 3^2 ≡ 1 ≡ 3 (mod 2).
For the other choices:
"If x, y, z, and n are natural numbers, there are no x, y, z such that x^n+y^n=z^n for n≥3." - This is Fermat's Last Theorem.
"If n≥2 and (n-1)! ≡ -1 (mod n), then n is prime." - This is Wilson's Theorem.
"If a and p are relatively prime, then a mod p ≠ 0." - This is a true statement though it's nothing earth-shattering.