# Show that $\gcd(a,bc)=1$ if and only if $\gcd(a,b)=1$ and $\gcd(a,c)=1$

Show that $\gcd(a,bc)=1$ if and only if $\gcd(a,b)=1$ and $\gcd(a,c)=1$.

I am new at proofs and I think I should use Euclid's Lemma which states "If $p$ is a prime that divides $ab$, then $p$ divides $a$ or $p$ divides $b$. However, I am not sure how to create a concrete proof or argument.

Any hints or help would be greatly appreciated. Thanks!

One direction should be clear: If $a$ and $bc$ have no common factors greater than $1$, then certainly neither do $a$ and $b$ nor $a$ and $c$. If this is not quite clear, argue thus: If $q$ divides $c$, then $q$ divides $bc$. So, any common factor of $a$ and $c$ is also a common factor of $a$ and $bc$. Same with $b$ in place of $c$.

For the other direction, Bezout's lemma gives a nice argument. Note that if $m,n$ are integers, and there are integers $x$ and $y$ such that $mx+ny=1$, then $\mathrm{gcd}(m,n)=1$. This is because any common divisor of $m,n$, is also a divisor of $mx+ny$. The other direction also holds, and is the content of Bezout's lemma: If $\mathrm{gcd}(m,n)=1$, then there are integers $x,y$ with $mx+ny=1$.

Accordingly, fix integers $x,y,z,w$ such that $ax+by=1$ and $az+cw=1$. Multiply these two equations, to obtain $$a(axz+xcw+byz)+bc(yw)=1.$$ The numbers $k=axz+xcw+byz$ and $l=yw$ are integers, and we have $ak+(bc)l=1$, so (as explained above), it follows that $\mathrm{gcd}(a,bc)=1$.

By the way, this idea of multiplying linear combinations given by Bezout allows us to prove many similar results. For example, if $\mathrm{gcd}(a,b)=1$, then also $\mathrm{gcd}(a^2,b^3)=1$, etc. (Several problems along these lines have been asked on the site before.)

For the part that if $\gcd(a,b)=1$ and $\gcd(a,c)=1$, then $\gcd(a,bc)=1$:

Hint:

If $1=ax+by=au+cv$, then

$$1=(ax+by)(au+cv)=a(aux+cvx+byu)+bc(yv)$$

• You used Bézout identity/lemma. By the way, the other part is easier: if $\gcd(a,bc)=1$, then there exist $s,t$ such that $a(s)+bc(t)=1$, i.e. $a(s)+b(ct)=1$, i.e. $a(s)+c(bt)=1$. – user236182 Sep 12 '17 at 14:25

The forward direction. gcd(a,bc) = 1 is postulated. Then there are integers x,y such that $ax + (bc)y = 1.$

The fetch is to associate the terms $ax + (bc)y = 1.$ in two ways, to apply Bezout's Identity to precipitate $gcd(a,b)$ and $gcd(a,c)$.

Group cy together to precipitate $b, a(x) + b(cy) = 1 => gcd(a,b) = 1$

Group by to precipitate $c, a(x) + (by)c = 1 => gcd(a,c) = 1.$

My proof of the backward direction is founded on https://math.stackexchange.com/a/673135. https://math.stackexchange.com/a/675887 is similar but doesn't color anything. I query the same thing as Bill Dubuque in his comment - I don't know why robjohn rearranges 'before multiplying the Bezout identities?, thence I don't do this.

But can someone please edify me? I want to know.

By reason of Bezout's Identity, there exist $x,y,u,v$ so that $\color{#C00000}{ax+by=1}$ and $\color{#00A000}{au+cv=1}$. The fetch is to multiply both these equations: \begin{align} \color{#C00000}{ (ax + by) }\color{#00A000}{ (au + cv) } &=\color{#C00000}{(1)}\color{#00A000}{(1)}\\ \color{magenta}{a}(axu + cv + buy)+\color{magenta}{bc}vy &= \end{align}

By reason of Bezout's Identity again, the last equation conveys $(\color{magenta}{a},\color{magenta}{bc})=1$.