Results 1 to 3 of 3

Thread: 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 $\displaystyle \gcd(c,a) =1$, then $\displaystyle c \not | a$ because $\displaystyle c, a$ are co-prime. Try to finish it from here.

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

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

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

    The second part is very easy. Just note that if $\displaystyle d \vert a$, then $\displaystyle 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: Oct 25th 2010, 05:45 AM
  2. Greatest common divisor
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: Apr 18th 2010, 03:16 PM
  3. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 17th 2009, 07:16 PM
  4. Greatest common divisor proofs
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 15th 2009, 11:04 AM
  5. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Dec 4th 2008, 01:08 AM

Search Tags


/mathhelpforum @mathhelpforum