Divisibility proof for numbers coprime to $6$

114 Views Asked by At

Can someone check on this? If it is wrong please refrain from telling me the answer.

Suppose $(6,a) = (6,b) = 1$. We wish to prove $24 \mid (a^2-b^2)$.

We can see that $(4,a) = (4,b) = 1$ since $2 \mid 4$ and $2 \mid 6$, so, $(24, a) = (24, b) = 1$. By Bezouts identity, any integer can be represented by a linear combination of two integers that are relatively prime, so let $a^2 - bx_2 = ax_1 + 24y_1$ and $b^2 - ax_1 = bx_2 + 24y_2$ for some $x_1,y_1,x_2,y_2 \in \mathbb{Z}$. Then $a^2 - b^2 = bx_2 - bx_2 + ax_1 - ax_2 + 24y_1 - 24y_2$. So $a^2 - b^2 = 24(y_1 - y_2)$. So $24 \mid (a^2 - b^2)$. $\square$

2

There are 2 best solutions below

2
On

I believe you have a chicken-and-egg problem here.

When you say $a^2-bx_2=ax_1+24y_1$, you are saying that, for every given $x_2$, you can find corresponding $x_1, y_1$. Then you say $b^2-ax_1=bx_2+24y_2$, and this probably means that, for every $x_1$ (including the one we just found!), there exist corresponding $x_2, y_2$.

What does not follow is that $x_2$, found in the second step (using $x_1$ found in the first step from the initially chosen $x_2$), matches the initially chosen $x_2$. (I mean, you do have a freedom to choose $x_2$ to start with, but what if none of those $x_2$'s end up winding back to themselves???)

In fact, I wouldn't even use the same symbol $x_2$ for two different things! But then, from that point on, your proof doesn't work, because it substantially relies on $x_2$ being one and the same thing.

0
On

Hints.

  1. The numbers are all of the form $6n \pm 1$

  2. If $n$ is odd, then $3n \pm 1$ is even.

  3. $(6n \pm 1)^2 - 1$ is a multiple of 24.

  4. $(6a \pm 1)^2 - (6b \pm 1)^2 = [(6a \pm 1)^2 - 1] - [(6b \pm 1)^2 - 1]$.