0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ This shows one part- you also need to show the other part. $\endgroup$ – voldemort Sep 7 '14 at 15:12
  • $\begingroup$ Seems good to me $\endgroup$ – Snufsan Sep 7 '14 at 15:12
  • $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Sep 7 '14 at 15:15
  • 2
    $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Sep 7 '14 at 15:20
1
$\begingroup$

You've done quite nicely. Just one recommendation (in agreement with Thomas Andrews' comment):

In your "reverse" proof, you have:

...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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.