Guest Post: An Interesting Property of Prime Numbers

Although I have already discussed modulo division, I believe that this proof is beyond the reach of average high school students. To explain further, I made additional notes on Patrick’s proof . I hope these explanations would be able to help students who want to delve on the proof.

***

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.

Explanation of the Prime Number Trick

We are trying to show that $(p^2 + 5) \mod 8 \equiv 6$ .

This is equivalent to showing that $(p^2 - 1) \mod 8 \equiv 0$ , or that $(p + 1)(p-1)$ is divisible by $8$ . (i)

Because $p > 3$ and is prime, then either $p \equiv 1 \mod 4$ or $p \equiv 3 \mod 4$ . (ii)

Consequently, it must be the case that (a) $p + 1 \equiv 2 \mod 4$ and $p - 1 \equiv 0 \mod 4$ or (b) $p - 1 \equiv 2 \mod 4$ and $p + 1 \equiv 0 \mod 4$ . (iii)

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. (iv)

***

Notes:

(i) In the congruence, $(p^2 - 1) \mod 8 \equiv 0$ , 6 was just subtracted from both sides of the congruence to obtain $p^2 - 1 \mod 8 \equiv 0$ . As you can see, congruence works just like equations.

(ii) This explains that any prime number greater than 3 gives remainders of either 1 or 3 when divided by 4. All prime numbers greater than 3 are odd integers, so it cannot give an even remainder when divided by an even number . Can you see why?

(iii) In (a) $1$ was added to both sides of $p \equiv 1 \mod 4$ and $p \equiv 4$ and $4$ was subtracted from both sides of $p \equiv 3 \mod 4$ . In (b), 2 was subtracted from both sides of $p \equiv 2 \mod 4$ and 1 was added to both sides of $p \equiv 3 \mod 4$ .

(iv) QED stand for quod erat demonstrandum which translates to “which was to be demonstrated.” This is usually placed at the end of the proof to signify that the statement above had been proven.

Author

Patrick Vennebush wrote Math Jokes 4 Mathy Folks, a collection of 400+ math jokes. He now shares jokes and blogs about math stuff in his blog Math Jokes for Mathy Folks. .

4 comments modulo division, prime number divided by 4, prime trick, prime trick proof, property of prime numbers, remainder of prime number over 4

Guest Post: An Interesting Property of Prime Numbers

Leave a ReplyCancel reply