1. Not finding help here? Sign up for a free 30min 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!

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?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: GCD proof
  1. Proofs . . . (Replies: 5)

  2. Proof that a=a (Replies: 3)

  3. Uniqueness proof (Replies: 2)

  4. Proof of epimormphism? (Replies: 3)