# Divisibility proof for numbers coprime to $6$

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

• You have a slight problem: you never say who $x_2$ is for your first expression (that is, you are trying to express $a^2-bx_2$ as a linear combination of $a$ and $24$... but you don't say who $x_2$ is); it can't be the one from the second expression, because in order to calculate the second expression (when you are using $b$ and $24$) you need to know who $x_1$ is; but in order to now who $x_1$ is, you need to know who $x_2$ is. But in order to know who $x_2$ is, you need to know who $x_1$ is. But... – Arturo Magidin Sep 6 '19 at 20:12
• Make a list of a few $x$s for which $(6,x)=1$ Check and see if they all work for your hypothesis. I think this is a great question. – steven gregory Sep 6 '19 at 20:17
• @stevengregory: Given that there are infinitely many such $x$s, that's going to take a while... – Arturo Magidin Sep 6 '19 at 20:17
• @stevengregory I don't recall seeing "a few" before it was edited.... But then, how will checking a few examples prove that something always holds? – Arturo Magidin Sep 6 '19 at 20:20
• 5,1 25-1 = 24 and 24 divides 24. 5,7 25 - 49 = -24 and 24 divides -24... – John Mancini Sep 6 '19 at 20:21

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.

• Ah I suspected that was faulty. Hmm... I am not quite sure how to proceed from here. Thank you for the help! – John Mancini Sep 6 '19 at 20:18
• @JohnMancini You are welcome, wish you good luck in trying to figure it out! – Stinking Bishop Sep 6 '19 at 20:21

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