Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.