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.

  1. Choose any prime number p > 3.
  2. Square it.
  3. Add 5.
  4. 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.

Related Posts Plugin for WordPress, Blogger...

4 thoughts on “Guest Post: An Interesting Property of Prime Numbers

  1. Not everything has to be about primes. It tells practicaly nothing about them. This property holds true for all odd numbers >=3.
    In fact this says that even multiples of 2 are divisible by 4 ( I hope this does not surprise anyone! )

Leave a Reply