Results 1 to 3 of 3

Math Help - Greatest common divisor-proofs?

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    23

    Greatest common divisor-proofs?

    Need proofs for the following lemmas:
    1. Let a, b, c belong to Z (integers) and suppose gcd(c,a)=1. If c|ab implies c|b.
    2. Let a,b,q,r belong to Z with a=qb+r, then

    • gcd(a,b)=gcd(b,r)
    • gcd(a,b)=gcd(-a,b)=gcd(a,-b)=gcd(-a,-b)
    3. Let x,y,z belong to Z. Then gcd (x,y,z)=1 IF AND ONLY IF gcd(x,y) and gcd (x,z)=1
    Last edited by mr fantastic; May 25th 2009 at 12:11 AM. Reason: Restored original question deleted by OP.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Oct 2008
    Posts
    23
    Could someone help with the third question posted above please? Thanks.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Jes
    Jes is offline
    Newbie
    Joined
    Oct 2008
    Posts
    12
    #1. If \gcd(c,a) =1, then c \not | a because c, a are co-prime. Try to finish it from here.

    #2 Define two sets S = \{d \in \mathbb {Z} : d | b, d |a \} and T = \{d \in \mathbb {Z} : d | b, d |r \}. These sets are nonempty since you can take d= 1. Now show S=T.

    (\subseteq) Let d \in S. Then d|b and d|a. There are q_1, q_2 \in \mathbb{Z} so that b = dq_1 and a = dq_2. Substitute into your equation and you get a = (dq_2) = (dq_1)q+r \Rightarrow d(q_2-q_1q) = r. So d \vert r and d \in T.

    Do the other direction now. Then S=T. By definition, \gcd(a, b) = \max(S) = \max(T) = \gcd (b,r)

    The second part is very easy. Just note that if d \vert a, then d \vert -a. How does that affect the gcd?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 05:45 AM
  2. Greatest common divisor
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: April 18th 2010, 03:16 PM
  3. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 17th 2009, 07:16 PM
  4. Greatest common divisor proofs
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 15th 2009, 11:04 AM
  5. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 4th 2008, 01:08 AM

Search Tags


/mathhelpforum @mathhelpforum