3
$\begingroup$

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.

Could you help me please?

  • 0
    @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.2012-07-10

2 Answers 2

1

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$.

1

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}$.