<s>[INST] Proof by Contradiction: let a,b $\in$Z . Prove that if 3 $\nmid$ a and 3 $\nmid$ b then $3 | a^2 - b^2$ Just wondering if this works for this question, book had a different answer and I couldn't find another answer for the question.
Assume, to the contrary, that 3 | a and 3 | b, then a = 3k, and b = 3x for x,k $\in$ Z, then $a^2 - b^2$ = $(3k)^2 - (3x)^2$ which is equal to $3(3k^2 - 3x^2)$, since $3k^2 - 3x^2$ is an integer, 3 | $a^2 - b^2$ which is a contradiction.
Is this correct?  
 [/INST] Proof by contradiction:
Suppose 3 does not divide $a^2-b^2$ the we must have:
$ 3  ł (a-b)(a+b)$
Suppose:
$a+b=3k_1 + r_1; r_1<3  ⇒ r_1 =1 , 2$
$a-b=3k_2 +r_2; r_2<3   ⇒  r_2=1, 2$
$2a=3(k_1 +k_2) + r_1 +r_2$
$2b=3(k_1-k_2) +r_1 -r_2$
1): $r_1 =1 $ and $r_2 =1$   ⇒ $2b=3(k_1-k_2) +1 - 1=3(k_1-k_2)$ ; cntradicts 3łb
2): $r_1 =1 $ and $r_2 =2$  ⇒ $2a=3(k_1 +k_2) + 1 +2=3(k_1 +k_2+1)$; contradicts 3ła
3): $r_1 =2 $ and $r_2 =2$  ⇒ $2b=3(k_1 -k_2) + 2 -2=3(k_1 -k_2)$; contradicts 3łb
4): $r_1 =2 $ and $r_1 =1$  ⇒ $2a=3(k_1 +k_2) + 2 +1=3(k_1 +k_2+1)$; contradicts 3ła
That is 3 must divide $a^2 - b^2$.   
</s>