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 $\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?