# Math Help - Greatest common divisor-proofs?

1. ## 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

2. Could someone help with the third question posted above please? Thanks.

3. #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?