Thread: if (a,n)=1 and (b,n)=1, then (ab,n)=1

if and , then

I believe this is true but not sure on how to prove it. I tried Bezout's identity, but I couldn't see what to do next or it just didn't go anywhere.

Originally Posted by dwsmith

if and , then

I believe this is true but not sure on how to prove it. I tried Bezout's identity, but I couldn't see what to do next or it just didn't go anywhere.

Let gcd(a,n)=1 and gcd(b,n)=1 and suppose that gcd(ab,n)=N>1.

Let p be a prime divisor of N, then p|ab and p|n. But p|ab implies p|a or p|b which is a contradiction. Therefore gcd(ab,n)=1.

CB