Results 1 to 5 of 5

Math Help - gcd of 3 integers

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    79

    gcd of 3 integers

    Consider three positive integers a, b, and c, and let d = gcd(a,b). Prove that the greatest number dividing all three of a,b,c is gcd(d,c). We know that the common divisors of a and b are the divisors of d.


    I can certainly see why this is true, but I'm not really sure where to start here. Would I break a,b, and c up into their prime factors and say that p(1),...,p(i) are common between all three? Then maybe show that d contains all those factors as well? I'm not really sure how this would exactly work.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by uberbandgeek6 View Post
    Consider three positive integers a, b, and c, and let d = gcd(a,b). Prove that the greatest number dividing all three of a,b,c is gcd(d,c). We know that the common divisors of a and b are the divisors of d.


    I can certainly see why this is true, but I'm not really sure where to start here. Would I break a,b, and c up into their prime factors and say that p(1),...,p(i) are common between all three? Then maybe show that d contains all those factors as well? I'm not really sure how this would exactly work.
    Prime factorization would work I think, but it should also follow from the definition of gcd.

    For any integers x and y where x and y are not both 0, g=gcd(x,y) iff

    1) g | x
    2) g | y
    3) for all integers z: z | x and z | y implies g | z.

    Notice that by this general definition the gcd is unique up to multiplication by units (1 or -1) but by convention we take the positive value.
    Last edited by undefined; September 16th 2010 at 07:01 AM. Reason: "x and y are not both 0"
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2008
    Posts
    79
    Still not sure what to start with. I'm thinking "Suppose there is a number k such that k > gcd(d,c) and k divides a,b,c," and show a contradiction, but I don't understand where I should go from there.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Suppose that e = \gcd \left\{ {c,d} \right\}
    Is it clear to you that e divides a,~b,~\&~c?
    What if some f>e divides a,~b,~\&~c?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by uberbandgeek6 View Post
    Still not sure what to start with. I'm thinking "Suppose there is a number k such that k > gcd(d,c) and k divides a,b,c," and show a contradiction, but I don't understand where I should go from there.
    We can actually use direct proof.

    Given d = gcd(a,b). Let g = gcd(d,c).

    Then by definition,

    1) g | d
    2) g | c
    3) for all z: z | d and z | c implies z | g

    (Note that g | d implies g | a and g | b.)

    Suppose z | a and z | b and z | c.

    From the definition of gcd, z | a and z | b implies z | d.

    So z | d and z | c.

    Again by definition, z | g.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: December 5th 2011, 11:47 PM
  2. Replies: 7
    Last Post: August 3rd 2010, 01:31 PM
  3. Matrix of integers whose inverse is full of integers
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 19th 2010, 02:02 PM
  4. Replies: 4
    Last Post: February 24th 2008, 03:08 PM
  5. Replies: 2
    Last Post: October 14th 2007, 03:18 PM

Search Tags


/mathhelpforum @mathhelpforum