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: A proof involving the greatest common divisor

  1. Aug 20, 2010 #1
    1. The problem statement, all variables and given/known data

    Don't have the book with me, but the problem basically asked me to prove that

    gcd(a,b)=1 [tex]\Rightarrow[/tex] gcd(an,bn)=n

    2. Relevant equations

    Since gcd(a,b)=1 is a fancy way of saying a and b are relatively prime (or is "a and b are relatively prime" a fancy way of saying gcd(a,b)=1?), I know of a theorem that may prove useful.

    If a and b are relatively prime then there exist integers m, n such that ma+nb=1.

    3. The attempt at a solution

    It just seems so intuitive ... I don't know where to start.
  2. jcsd
  3. Aug 20, 2010 #2
    hmm, you can multiply both side by n, since integer are well defined
  4. Aug 20, 2010 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That's too much machinery. Just go with the definition. gcd(na,nb) is the largest number dividing both na and nb. So two parts:

    1)Show that n divides na and nb (I hope this is easy)
    2) Show that n is the largest such number (this will require the co-prime part)
  5. Aug 20, 2010 #4

    Proof. Let z be a number that divides na and nb. At least z=n. Now let z=a>n. z divides a but not b; otherwise gcd(a,b) would equal a. Our only other option is z=b>n, but it does not work for the same reason as before. Therefore, if gcd(a,b)=1, then gcd(na,nb)=1.
  6. Aug 20, 2010 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Why does a number dividing na and nb have to be a or b? Your final conclusion is wrong, gcd(na,nb)=n
  7. Aug 21, 2010 #6
    Whoops! I meant my final conclusion to be gcd(na,nb)=n. All the work up to that point is correct.
  8. Aug 21, 2010 #7
    i don't get it too, T_T, do you mind explain it?
  9. Aug 21, 2010 #8
    If z divides a number, then z divides one of its factors. For example, I know 4|24 because 24=4*6 and 4|4. That's the point behind "if z divides an then z divides a or z divides n."
  10. Aug 21, 2010 #9


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    But you don't know that it's factored correctly. For example, given 4*6, 12 divides 24 but 12 doesn't divide 4 or 6.

    It sounds like you want to word it something like this: we know gcd(na,nb) is greater than or equal to n. Suppose it's greater than n. It has to be divisible by n (since the greatest common divisor is divisible by all divisors of na and nb), so is if of the form gcbd(na,nb)=nx. Now you want to show that x=1
  11. Aug 21, 2010 #10
    Well, it's a fact that if z divides a number y=a1*a2*a3*...*an, then z divides at least one ai, 1≤in.
  12. Aug 21, 2010 #11
    that statement is true provided that z is prime, in this case 4 is not prime
  13. Aug 23, 2010 #12
    What about a proof by contraposition? Say the gcd(an, bn) does not equal n. Then there is an integer k greater than n that divides both an and bn. Say an = k * l and bn = k * m, l and m integers, and so a = (k * l) / n and b = (k * m) / n. You know that a and b are integers since you are dividing out a factor. K is greater than n and divides both, so this seems to prove that the gcd of a and b is not 1. It seems like a trivial proof so there must be some gaping holes....

    EDIT: I think it is necessary to say that abs(k) > abs(n). Also that n cannot be zero, making it impossible for k = 1.
    Last edited: Aug 23, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook