Math: number theory: (n mod 3)²

The tutor shows an interesting consequence of mod 3 arithmetic.

Back in my March 25, 2014 post, I mentioned that mod means remainder. For example, 19 mod 4 = 3, because when you divide 19 by 4, you get 3 left over.

Claim: If neither of two numbers is divisible by 3, the difference of their squares must be.

Proof:

If a number n is not divisible by 3, then either n mod 3 = 2 or n mod 3 = 1.

If n mod 3 = 2, then n = 3x+2 for some integer x. n², then, is

(3x+2)²=(3x+2)(3x+2)=9x²+6x+4. 9x²+6x+4=9x²+6x+3+1=3(3x²+2x+1) + 1.

If, on the other hand, n=3y+1, then n²=(3y+1)²=(3y+1)(3y+1)=9y²+6y+1=3(3y²+2y)+1.

Therefore, if two numbers m and n are both indivisible by 3, then m²-n² has the form 3p+1 – (3q+1) = 3p+1-3q-1=3p-3q=3(p-q). The difference of the squares of m and n must be divisible by 3.

Source:

Dudley, Underwood. Elementary Number Theory. New York:
  W H Freeman and Company, 1978.

Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.

Tagged with: , ,

Leave a Reply