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 .
- 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 .
This is equivalent to showing that , or that is divisible by . (i)
Because and is prime, then either or . (ii)
Consequently, it must be the case that (a) and or (b) and . (iii)
That is, both numbers will be even, and at least one of them will be a multiple of . For either (a) or (b), the product will be a multiple of . Q.E.D. (iv)
(i) In the congruence, , 6 was just subtracted from both sides of the congruence to obtain . 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) was added to both sides of and and was subtracted from both sides of . In (b), 2 was subtracted from both sides of and 1 was added to both sides of .
(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.