Results 1 to 7 of 7

Math Help - simple gcd proofs

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    204

    simple gcd proofs

    (a) prove that gcd(a,b,c) = gcd(a,gcd(b,c))
    (b) a,b,c \in N, with gcd(a,b) = gcd(a,c) = gcd(b,c). prove that gcd(a,b,c) = 1
    (c) find a,b,c \in N with gcd(a,b,c) = 1 but gcd(a,b), gcd(a,c), gcd(b,c) all > 1

    i thought i would put them all in the same thread seeing as they may relate to each other
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1
    Quote Originally Posted by wik_chick88 View Post
    (a) prove that gcd(a,b,c) = gcd(a,gcd(b,c))
    (b) a,b,c \in N, with gcd(a,b) = gcd(a,c) = gcd(b,c). prove that gcd(a,b,c) = 1
    (c) find a,b,c \in N with gcd(a,b,c) = 1 but gcd(a,b), gcd(a,c), gcd(b,c) all > 1

    i thought i would put them all in the same thread seeing as they may relate to each other
    show some working for part (a).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2011
    Posts
    6
    a) Let x = GCD(a,b,c). Let y = GCD(a, GCD(b,c)). Then, by definition of GCD, y divides a.

    Also, y divides GCD(b,c). Therefore y divides b and y divides c.

    Thus, y divides a, b, and c. This implies that y divides GCD(a,b,c) = x since any common divisor divides the GCD.

    On the other hand, x divides a, b, and c. In particular, since x divides b and c, x divides GCD(b,c). Thus, since x divides a and x divides GCD(b,c), it follows that x divides GCD(a, GCD(b,c)) = y.

    We have shown y divides x and we have also shown x divides y. Thus, x = y. IOW, GCD(a,b,c) = GCD(a, GCD(b,c)).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jun 2011
    Posts
    6
    b) This claim is actually false. Counterexample: Let a = 10, let b = 15, let c = 25.
    Then GCD(10,15) = 5, GCD(15,25) = 5, GCD(25,10) = 5, and GCD(10,15,25) = 5.

    So, you might have transcribed the problem statement incorrectly. Otherwise, it's a typo in the source textbook or whatever.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jun 2011
    Posts
    6
    c) Let a = 6, b = 15, c = 10.

    Then GCD(6,15,10) = 1, yet GCD(6,15) = 3, GCD(15,10) = 5, GCD(10,6) = 2.


    More generally, we can find such numbers by first selecting 3 distinct prime numbers p1, p2, and p3. The next step would be to let a = p1*p2, b = p2*p3, and c = p3*p1.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Apr 2008
    Posts
    204
    Quote Originally Posted by Solvoid View Post
    b) This claim is actually false. Counterexample: Let a = 10, let b = 15, let c = 25.
    Then GCD(10,15) = 5, GCD(15,25) = 5, GCD(25,10) = 5, and GCD(10,15,25) = 5.

    So, you might have transcribed the problem statement incorrectly. Otherwise, it's a typo in the source textbook or whatever.
    i did type it down properly sorry! i meant that gcd(a,b)=gcd(a,c)=gcd(b,c)=1
    prove that gcd(a,b,c)=1
    is there a quicker way to do this than proof by contradiction?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jun 2011
    Posts
    6
    Quote Originally Posted by wik_chick88 View Post
    i did type it down properly sorry! i meant that gcd(a,b)=gcd(a,c)=gcd(b,c)=1
    prove that gcd(a,b,c)=1
    is there a quicker way to do this than proof by contradiction?

    Yes, there definitely is!

    By part (a), GCD(a,b,c) = GCD(a, GCD(b,c)) = GCD(a, 1) = 1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. a few simple proofs
    Posted in the Calculus Forum
    Replies: 7
    Last Post: March 15th 2011, 06:23 PM
  2. Simple set proofs
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 3rd 2011, 04:52 AM
  3. Two Simple Proofs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 26th 2009, 08:43 PM
  4. Simple Proofs Problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 19th 2009, 06:14 PM
  5. 'simple' proofs
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 30th 2007, 12:12 PM

Search Tags


/mathhelpforum @mathhelpforum