# GCD's and Relatively Prime numbers

Prove that $gcd(a,bc)=1$ iff both $gcd(a,b)=1$ and $gcd(a,c)=1$.

I know I need to prove it both ways but is this how you do it?

Proof: Assume that $gcd(a,bc)=1$. So $a$ and $bc$ are relatively prime integers. Thus we can write $ax+bcy=1$. From this equation we can now say $gcd(a,b)=1$ and $gcd(a,c)=1$.

And then for the reverse method

Proof: Assume both $gcd(a,b)=1$ and $gcd(a,c)=1$. Since $a$, $c$, and $bc$ are relatively prime integers We can say $ax+cy=1$ and $az+bq=1$.

So $(ax+cy)(az+bq)=1\cdot 1$ Then foil it out and to get $a^2zx+axbq+cyaz+cybq=1$ And Since $z,x,a,b,q,c,y\in Z$ $gcd(a,bc)=1$

QED???

Is this the right idea of how to go about this problem? Or am I missing just some small step?

• This shows one part- you also need to show the other part. – voldemort Sep 7 '14 at 15:12
• Seems good to me – Snufsan Sep 7 '14 at 15:12
• That shows the easy way - if $\gcd(a,bc)=1$ then $\gcd(a,b)=1=\gcd(a,c)$. Next you need to show that if $\gcd(a,b)=\gcd(a,c)=1$ then $\gcd(a,bc)=1$. – Thomas Andrews Sep 7 '14 at 15:15
• Your second half is good, but better to be explicit after applying FOIL, you get:$$a(azx+xbq+cyz)+(bc)(yq)=1$$ So $(a,bc)=1$. – Thomas Andrews Sep 7 '14 at 15:20

...So $(ax+cy)(az+bq)=1⋅1$. Then foil it out and to get $a^2zx+axbq+cyaz+cybq=1$...
My recommendation would be to gather like factors of $a$ and of $bc$ to show explicitly the linear combination of $a, bc$: $$a(azx+xbq+cyz)+ bc(yq)=1$$
Then end as you did: Since $z,x,a,b,q,c,y\in Z$, [we conclude] $gcd(a,bc)=1$.