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

GCD proof

  1. Apr 6, 2005 #1
    I'm having trouble with gcd proofs in general, but here is a specific problem.

    Let a and b be integers, not both zero, and let d be a positive integer that divides both a and b. Then there exists a1 and b1 such that a=a1*d and b=b1*d.
    Prove that d=gcd(a,b) if and only if 1=gcd(a1,b1)

    What I have so far:

    Pf: Let a and b be integers and since d|a and d|b then d|gcd(a,b) by definition. So let d*k=gcd(a,b) for some integer k. Then dk=ma+nb where m,n are integers. (I'm not sure if I can do that last statment). Now dk=m(a1*d)+n(b1*d) where a=a1*d and b=b1*d. So dk=d(m*a1+n*b1) and therefore d|(m*a1+n*b1) ....

    I'm not sure if I'm heading in the right direction, but after that point I don't know how to get to 1=gcd(a1,b1).

    For the second part of the proof I have"

    Now assume a and b are integers such that 1=gcd(a1,b1). So there exists m and n that are integers such that 1=ma1+nb1. (Now I multiple by a integer d). Then d=md*a1 + nd*b1, and d=ma+nb where a1*d=a and b1*d=b.

    Again, I'm stuck after this point.
  2. jcsd
  3. Apr 6, 2005 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I think you're making it far too complicated.

    Let's do this way: suppose that gcd(a1,b1)=e and e is different from 1. Then a1=ea2 and b1=eb2 for some integers a2 and b2, then a=a2ed, and b=b2ed.

    So, if d is the gcd, then e cannot be different from 1 as claimed, or de divides both a and b.

    For the second part, if ass ume gcd(a1,b1)=1 we can indeed conclude that d=am+bn, but this tells us that gcd(m,n) divides d, since the gcd divides the terms on the right. So d is less than gcd(a,b) since it is some divisor of a and b, and is also divisible by the gcd so it must equal the gcd.
  4. Aug 25, 2009 #3
    This was mathrocks' question: [tex]a,b \in Z[/tex] [tex]a,b \neq 0[/tex], and [tex]d=gcd(a,b)[/tex]. If [tex]a=da_1[/tex] and [tex]b=db_1[/tex] for some [tex]a_1, b_1 \in Z[/tex] then you want to show that [tex]gcd(a_1,b_1) = 1[/tex].

    I can't follow matt grime's proof but I know that there is a theorem which states:

    Let [tex]d=gcd(a,b)[/tex]. Then there exists integers x and y such that [tex]d=ax+by[/tex].

    I want to know how we can prove the problem above using this theorem.


    [tex]d=ax + by[/tex] and since [tex]a=da_1[/tex] and [tex]b=db_1[/tex],

    [tex]d=(da_1)x + (db_1)y = (dx)a_1 + (dy)b_1[/tex]

    I'm stuck at this point. Can anyone help please?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook