# Proof involving gcd

Here is what I'm suppose to show:

Suppose that $a$ and $b$ are relatively prime. Show that if $c \in \mathbb{Z}$ and $a|cb$, then $a|c$.

I have a strong feeling that I did this proof correct, but I want to double check with the community to see how my proof can be improved, if need be.

Proof

Since $a$ and $b$ are relatively prime, $gcd(a,b) = 1.$ By Bezout's Identity and the fact that $gcd(a,b) = 1$, $\exists x,y \in \mathbb{Z}$ such that

$$ax+by = 1.$$

Multiply the equation above by $c$ on both sides to yield

$$cax+cby = c.$$

Since we know that $a|cb$, this means that $a$ is a divisor of $cb$. In other words, $ak = bc$ for some $k \in \mathbb{Z}.$ Thus, we have

$$(ca)x+(ak)y = c.$$

Thus, $a|c$ and this completes the proof.

QED.

• Absolutely correct – Lucas Corrêa Feb 13 '18 at 3:26
• Perhaps there is more than one way to skin a cat, but this is the approach that I went for. – John Smith Feb 13 '18 at 3:28
• I think this is the most natural way – Lucas Corrêa Feb 13 '18 at 3:30
• Now that I think about it, I believe so too Lucas. – John Smith Feb 13 '18 at 3:31

$\textbf{Alternative solution:}$ (Suppose $a, b, c >0$)
Let's write $c = aq + r$ with $0 \leq r < a$. Thus, $cb = abq + br$. Since $a\mid cb$ and $a\mid abq$, $a|br$. But $\gcd(a, b) = 1$ (has no prime factors in common), then $a\mid r$. Since $r < a$, $r = 0$, therefore, $c = aq$.