# Prove three things related to the GCD

I have to demonstrate this three formulae:

1. $\gcd(ac,bc)=c\gcd(a,b), \forall a,b,c \in \mathbb{N}$
2. $a\mid c \land b\mid c \land \gcd(a,b)=1 \implies ab\mid c$
3. $\gcd(a,b,c)=xa+yb+zc, \forall a,b,c,x,y,z \in \mathbb{Z}$

and I have no idea to get started using the definition of GCD ($\gcd=\max(k\in \mathbb{N} : k\mid ac\land k\mid bc)$) or other things.

-
One way to prove two positive integers are equal is to prove that the are divisors of each other. I suspect you'll find that useful in some of this. – Michael Hardy Jul 10 '12 at 18:16
3. is not correct. The gcd(a,b,c) is the least positive value of the right hand side. This property of gcd you can use to prove 1. – PAD Jul 10 '12 at 18:17
3.should be this $\gcd(a,b,c)=xa+yb+zc, \forall a,b,c \quad \exists x,y,z \in \mathbb{Z}$ – Saurabh Jul 10 '12 at 18:22
@SaurabhHota : I'd write it as $\Big(\gcd(a,b,c)=xa+yb+zc,\ ∀a,b,c\Big)\ ∃x,y,z∈Z$, to be clear that the way in which the quantifiers are nested matters. – Michael Hardy Jul 10 '12 at 22:00

1)
Let $d=(a,b)$ and $d_1=(ac, bc)$. Since $cd |ac$ and $cd |bc$ we have that $cd \le d_1$.

Write $d=ax+by$ for some integers $x,y$. Then $dc=ac x+ bcy$. Therefore $d_1 \le dc$.

2) Write $c=ar$, $c=bs$. Since $(a,b)=1$ there exists integers $x,y$ such that $ax+by=1$. We multiply this equation by $c$ to obtain $acx+bcy=c$. Therefore $absx+bary=c$ and finally $ab(sx+ry)=c$ which implies $ab|c$.

-

As Bill Dubuque likes to insist, use the universal properties. Recall that $d=\gcd(a,b)$ if and only if:

• $d|a$ and $d|b$; and
• If $c|a$ and $c|b$, then $c|d$.

Using this property, we can proceed:

1. $\gcd(a,b)|a,b$, so $c\gcd(a,b)|ac,ab$, so $c\gcd(a,b) |\gcd(ac,bc)$. Conversely, $c|\gcd(ac,bc)$, so $\frac{1}{c}\gcd(ac,bc)|\frac{1}{c}(ac),\frac{1}{c}(bc)$; hence $\frac{1}{c}\gcd(ac,bc)|a,b$, so $\frac{1}{c}\gcd(ac,bc)|\gcd(a,b)$. Hence $\gcd(ac,bc)|c\gcd(a,b)$. Thus, $c\gcd(a,b)=\gcd(ac,bc)$.

2. $\def\lcm{\mathrm{lcm}}$We can use the dual of the gcd, the lcm. $m=\lcm(a,b)$ if and only if:

• $a|m$ and $b|m$; and
• If $a|k$ and $b|k$, then $m|k$.

Since $\gcd(a,b)\lcm(a,b) = |ab|$, we have: \begin{align*} a|c\text{ and }b|c &\iff \lcm(a,b)|c\\ &\iff \frac{|ab|}{\gcd(a,b)}|c\\ &\iff |ab||\gcd(a,b)c\\ &\iff ab|\gcd(a,b)c. \end{align*} In particular, if $\gcd(a,b)=1$, then $ab|c$.

Or, if you don't want to use the lcm (or the formula $\gcd(a,b)\lcm(a,b)=|ab|$), note that $ab|c$ if and only if $\gcd(ab,c)=ab$. Since $a|c$ we can write $c=ak$, so $$\gcd(ab,c) = \gcd(ab,ak) = a\gcd(b,k). Since b|c = ak, and \gcd(a,b)=1, then b|k, so we can write k=b\ell. So$$\gcd(ab,c) = \gcd(ab,ak) = a\gcd(b,k) = a\gcd(b,b\ell) = ab\gcd(1,\ell) = ab. Therefore, $ab|c$.

Number 3 is incorrect as currently stated. The fact that you can find some $x$, $y$, and $z$ such that $\gcd(a,b,c) = ax+by+cz$, follows from the fact that $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ (check the universal property), and that $\gcd(a,b)$ can be expressed as $ak+b\ell$ for some $k,\ell\in\mathbb{Z}$.

-