# Proof explanation: suppose $a\mid bc$ and $\gcd(a, b) = 1$. Then $a\mid c$.

I have been given a proof, but I do not understand the "why" behind it. If someone could explain me each of its steps with great detail that would be amazing!

The proof I was given is the following one:

Since $$\gcd(a,b)=1$$, we have that $$ax+by=1.\label{1}\tag{1}$$ We need see the relation between $$c$$ and $$a$$, so we multiply both sides of \eqref{1} by $$c$$ and get $$c= acx+bcy.\label{2}\tag{2}$$ Now since $$c \mid cax+cby$$, $$a\mid bc$$ and $$a \mid bcy$$, we conclude $$a\mid cax$$ and this proves that $$a \mid c$$.

I do not get how $$a$$ has been proved to divide $$c$$ in this last step.

• Which proof do you want to be explained? There are several... – Michael Biro Jul 17 '19 at 0:36
• Welcome to MSE. Is there any particular reason you didn't provide your proof here? If you did, then when you ask about the "why", we can try to give you an explanation directly for it. – John Omielan Jul 17 '19 at 0:37
• What do you mean by the "why" behind the proof? Usually in a proof, the truth of each step is argued for, and in the end one reaches the conclusion one is after. That's all there is to it. Are you looking for something more? Some sort of reasoning for why one chooses to do each step, for instance? The answer to that is likely "because it turns out to work in the end". – Arthur Jul 17 '19 at 0:38
• @JohnOmielan I have added the proof that I was given. – Shailesh Jul 17 '19 at 0:52
• @Shailesh Thanks for adding it. I've given an answer which I hope explains what is going on in the proof you were given. – John Omielan Jul 17 '19 at 0:53

In the proof you were given, you have that $$c= acx+bcy$$ for some integers $$x$$ and $$y$$ (note Bézout's identity proves there exists these integers $$x$$ and $$y$$ which satisfy the original equation of $$ax + by = 1$$). Also, you know that $$a\mid bc$$, so $$a$$ divides the second term of $$bcy$$. In addition, $$a \mid acx$$, so $$a$$ divides the first term. Since $$a$$ divides both terms on the right, it must divide their sum (more generally, $$a$$ divides any linear combination of those terms), i.e., $$c$$, so $$a\mid c$$.

John explained the algebra. Below I explain one way to "understand the 'why' behind the proof".

Notice that the set $$D$$ of integers $$\,d\,$$ such that $$\,a\mid d c\,$$ is closed under subtraction by

$$a\mid dc,d'c\,\Rightarrow\, a\mid dc\!-\!d'c = (d\!-\!d')c\,\Rightarrow\, d-d'\in D\qquad$$

so a basic Theorem $$\Rightarrow D\,$$ is also closed under gcd, so $$\,a,b\in D\,\Rightarrow\, (a,b)\!=\!1\in D,\,$$ so $$\,a\mid 1c=c$$

The quoted proof is a special case of this proof, since the the gcd (and its Bezout identity) can be obtained by repeated subtraction: the Euclidean algorithm in subtractive (vs. remainder) form.

More conceptually:  nonzero $$d\in D$$ are all the possible denominators for $$\,c/a,\,$$ because

$$\,d\in D\!\!\iff\! a\mid dc\!$$ $$\iff\!\! \exists\, j\!:\, aj = dc\!$$ $$\iff\! \!\exists\, j\!:\, \large \frac{c}a = \frac{j}d\!$$ $$\iff\! \large \frac{c}a\,$$ is writable with denom $$\,d$$

The above closure property says these denominators are closed under subtraction so they are also closed under gcd. So $$\,a,b\,$$ denoms for $$\,c/a\Rightarrow$$ so too is their gcd $$(a,b)\! =\! 1,\,$$ i.e. $$\,c/a = j/1\,$$ so $$\,a\mid c$$.

Or, directly by Bezout $$\, f= c/a\,$$ and $$\, af,bf\in\Bbb Z\,\Rightarrow f = (ax\!+\!by)f = x(af)\!+\!y(bf)\in\Bbb Z,\,$$ which is a direct fractional view of the proof cited in the OP (but is still less conceptual, since it doesn't explicitly emphasize the fundamental innate structure - that denominators are closed under gcd).

Of course gcd-closure of denoms is also obvious from the well-known result that denominator set $$D = \ell\Bbb\,\! Z\,$$ is the set of multiples of the least denominator $$\ell,\,$$ so if $$\,j\ell, k\ell\,$$ are denoms then their gcd $$\,(j\ell,k\ell) = (j,k)\ell$$ is also a denom (being a multiple of $$\ell)$$. This well-known result is provable as above, see unique fractionization.

The algebraic (ring) essence of the matter is clarified when studying denominator (and order) ideals.