1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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