Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Show that m and n relatively prime if and only if no prime divides both

  1. Jun 16, 2012 #1
    1. The problem statement, all variables and given/known data
    Show that m and n are relatively prime if and only if no prime divides both.

    3. The attempt at a solution

    Now, if [itex]m[/itex] and [itex]n[/itex] are relatively prime, we have [itex]gcd(m,n) = 1[/itex]. All the common divisors of [itex]m[/itex] and [itex]n[/itex] must divide [itex]gcd(m,n)[/itex], but the only divisors of [itex]1[/itex] are [itex]1[/itex] and [itex]-1[/itex]. Thus they have no common prime divisor.

    The converse:

    Suppose we have the integers [itex]m[/itex] and [itex]n[/itex] with the following prime factorization:

    [itex]m = p_1^{a_1}p_2^{a_2}...p_r^{a_r}[/itex]
    [itex]n = p_1^{b_1}p_2^{b_2}...p_r^{b_r}[/itex]

    where [itex]p_i[/itex] are primes that divide at least one of [itex]m[/itex] and [itex]n[/itex], and an exponent is zero if the prime in question doesn't occur in that number.

    Now the [itex]gcd(m,n) = p_1^{k_1}p_2^{k_2}...p_r^{k_r}[/itex] where [itex]k_i = min(a_i,b_i)[/itex] for [itex]1≤i≤r[/itex].

    So, if [itex]m[/itex] and [itex]n[/itex] don't have any common primes, [itex]min(a_i,b_i) = 0[/itex] for [itex]1≤i≤r[/itex] thus having [itex]gcd(m,n) = 1[/itex]. If not, then there would be at least one prime dividing both, thus leading [itex]m[/itex] and [itex]n[/itex] not be relatively prime.

    I believe the first part is OK, but I'm not quite sure about the converse proof.
  2. jcsd
  3. Jun 16, 2012 #2
    Hi tonit!

    I think the second proof is correct... :smile:
  4. Jun 16, 2012 #3
    Hi tonit,
    that looks right, if a bit involved.
    Couldn't you just say that if m and n have a common prime than their gcd will be a muliple of it and therefore be >1, thereby showing they are not coprime ?

  5. Jun 16, 2012 #4
    thank you both for your replies.
    @oli4, It is about the converse: If they have no common prime divisor, then they are relatively prime. I know there may be other ways to prove it, but I am trying to put all the things I learned to work. Thanks though :D
  6. Jun 16, 2012 #5
    Tonit, you are right ! I just restated your first part :)
    Now, if m and n are not coprime, then by definition they have at least a common factor which is >1
    From those factors, any one that is not prime can be broken into products of primes, any of those being a factor too of course.
  7. Jun 16, 2012 #6
    gcd(m,n) = 1 <=> m and n have no common prime divisor...

    so after showing that gcd(m,n) = 1 => m and n have no common prime divisor.

    it needs to be shown that: m and n have no common prime divisor => gcd(m,n) = 1

    Now each integer has it's own unique prime factorization.

    And here's where my second part starts from up there.

    [itex]min(a_i,b_i) = 0[/itex] for [itex]1≤i≤r[/itex] means that [itex]gcd(m,n) = p_1^{0}p_2^{0}...p_r^{0} = 1[/itex] which yields that [itex]m[/itex] and [itex]n[/itex] are relatively prime.
  8. Jun 16, 2012 #7
    Hi tonit,
    sorry, I must be confusing things, or it might just be a matter of having different definitions in different courses for coprimes (since they are equivalent, this is not too surprising)
    For what I remember, two integers are coprime if the only integer that can divide them is 1, which is equivalent to saying their gcd is 1, or to say that they have no common prime divisor
    I guess you must be starting with gcd=1 as the initial definition and are sticking to it which is what you have to do.
    (I just checked wikipedia and it starts with the same definition I have and mentions indeed that this is the same thing as saying gcd=1)
  9. Jun 16, 2012 #8
    if and only if is <=>

    so after proving that gcd(m,n) = 1 means that no prime divides both, you need to prove that no prime divides both => gcd(m,n)=1


    Show that m and n relatively prime if and only if no prime divides both can be translated into:

    [itex]gcd(m,n) = 1 \Rightarrow[/itex] no prime divides both
    no prime divides both [itex]\Rightarrow gcd(m,n) = 1[/itex]
  10. Jun 16, 2012 #9
    Tonit, yes, this is what I just did.
    In my first post I said the exact same thing you did in the first part (but you were after the second anyway)
    "coprimes (gcd=1) => no common prime" (except by saying "common prime=> not coprimes")
    Now I'm saying "not coprimes (gcd>1) => common prime", which is the same thing as
    "no common prime => coprimes (gcd=1)"
    I must be tired (I am, in fact) :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook