Results 1 to 2 of 2

Math Help - if (a,n)=1 and (b,n)=1, then (ab,n)=1

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

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

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

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

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

    Quote Originally Posted by dwsmith View Post
    if gcd(a,n)=1 and gcd(b,n)=1, then gcd(ab,n)=1

    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
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum