1

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?

Jacob B.
  • 19
  • No, for a proof by contradiction one needs to assume $3\nmid a$, $3\nmid b$ and $3\nmid(a^2-b^2)$. – Angina Seng Nov 01 '17 at 07:08
  • D'oh! Thanks. Whoops! – Jacob B. Nov 01 '17 at 07:14
  • Note if $p$ is a prime and if $p\mid ab$, then $p\mid a$ or $p\mid b$. The negation of this is $p\nmid a$ and $p\nmid b$ implies $p\nmid ab$. – C.S. Nov 01 '17 at 07:15
  • Elaborating on what Lord said: when showing $A \implies B$, to proceed by contradiction you assume $A$ and $\neg B$. Then show that by assuming both of this things, you arrive at something absurd. This means that our assumption was false, so the law of the excluded middle tells us that its negation must be true. But the negation of $A$ and $\neg B$ is $A \implies B$. – Prince M Nov 01 '17 at 07:44
  • It could be seen that generally if $n ł a$ and $n ł b$ but$ n | (a-b)$ then $n | (a^2 - b^2)$; suppose $a ≡ r_1 mod n$ and $ b ≡ r_2 mod n$ , $ a-b≡ (r_1-r_2)mod n$ if $n | a -b$ then we must have $r_1 - r_2 = 0$, that is $ r_1 = r_2$ and $a^2 - b^2 ≡ 0 mod n$ that is $n | a^2 - b^2$ – sirous Nov 02 '17 at 18:04
  • The condition $n ł a$ and $n ł b$ is not enough , also n must also divide $a - b$ for $ n | a^k - b^k $ in general. – sirous Nov 03 '17 at 06:24

2 Answers2

1

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$.

sirous
  • 10,751
0

If you don't have to use contradiction, here is a direct proof.

  • $a = 3A+1$ and $b = 3B+1$. Then $a^2-b^2=(a+b)(a-b)=(a+b)(3A-3B)=3(a+b)(A-B)$.

  • $a = 3A+1$ and $b = 3B+2$. Then $a^2-b^2=(a+b)(a-b)=(3A+3B+3)(a-b)=3(A+B+1)(a-b)$.

The case $a = 3A+2$ and $b = 3B+1$ follows by symmetry.

lhf
  • 216,483