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!
Best Answer
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.)