## Archive for August 26, 2012

### In Your Prime

I’ve got a prime number trick for you today.

- Choose any prime number
*p*> 3. - Square it.
- Add 5.
- Divide by 8.

Having no idea which prime number you chose, I can tell you this:

The remainder of your result is 6.

Pretty cool, huh?

I will now fill a bunch of space with quotes and jokes about prime numbers to prevent you from seeing the spoiler explanation below. But you can skip straight to the bottom if you’re not interested in the other stuff or if you just can’t control yourself.

Mark Haddon, author of *The Curious Incident of the Dog in the Night-time*, wrote the following:

Prime numbers are what is left when you have taken all the patterns away. I think prime numbers are like life. They are very logical, but you could never work out the rules, even if you spent all your time thinking about them.

(Incidentally, if you haven’t read that book, you should. Amazon reviewer Grant Cairns said it better than I could: “The integration of the mathematics into the fiction is better than any other work that I know of. The overall effect is a beautiful story that any maths fans will find hard to read without the tissue box close at hand.”)

Israeli mathematician Noga Alon said that he was interviewed on Israeli radio, and he mentioned that Euclid proved over 2,000 years ago that there are infinitely many primes. As the story goes, the host immediately interupted him and asked:

Are there still infinitely many primes?

And of course there’s this moldy oldie:

Several professionals were asked how many odd integers greater than 2 are prime. The responses were as follows:

Mathematician:3 is prime, 5 is prime, 7 is prime, and by induction, every odd integer greater than 2 is prime.

Physicist:3 is prime, 5 is prime, 7 is prime, 9 is experimental error, 11 is prime, …

Engineer:3 is prime, 5 is prime, 7 is prime, 9 is prime, 11 is prime, …

Programmer:3 is prime, 5 is prime, 7 is prime, 7 is prime, 7 is prime, …

Marketer:3 is prime, 5 is prime, 7 is prime, 9 is a feature, …

Software Salesperson:3 is prime, 5 is prime, 7 is prime, 9 will be prime in the next release, …

Biologist:3 is prime, 5 is prime, 7 is prime, the results for 9 have not yet arrived…

Advertiser:3 is prime, 5 is prime, 7 is prime, 11 is prime, …

Lawyer:3 is prime, 5 is prime, 7 is prime, there is not enough evidence to prove that 9 isnotprime, …

Accountant:3 is prime, 5 is prime, 7 is prime, 9 is prime if you deduct 2/3 in taxes, …

Statistician:Try several randomly chosen odd numbers: 17 is prime, 23 is prime, 11 is prime, …

Professor:3 is prime, 5 is prime, 7 is prime, and the rest are left as exercises for the student.

Psychologist:3 is prime, 5 is prime, 7 is prime, 9 is prime but tries to suppress it, …

Card Counter:3, 5, and 7 are all prime, but I prefer 21.

*Explanation of the Prime Number Trick*

We are trying to show that (*p*^{2} + 5) mod 8 = 6. This is equivalent to showing that (*p*^{2} ‑ 1) mod 8 = 0, or that (*p* + 1)(*p* ‑ 1) is divisible by 8.

Because *p* > 3 and is prime, then either *p* = 1 mod 4 or *p* = 3 mod 4. Consequently, it must be the case that (a) *p* + 1 = 2 mod 4 and p ‑ 1 = 0 mod 4 or (b) *p* ‑ 1 = 2 mod 4 and *p* + 1 = 0 mod 4. That is, both numbers will be even, and at least one of them will be a multiple of 4. For either (a) or (b), the product (*p* + 1)(*p* ‑ 1) will be a multiple of 8. Q.E.D.