9
$\begingroup$

Prove $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ for $0\ne a,b,c\in \Bbb{Z}$. I tried solving it with sets but I sense there are some details I am missing. I would truly appreciate your reference.

$\endgroup$
12
$\begingroup$

Hint $\qquad d\mid(a,b,c)\!\!\!\color{#c00}{\overset{\rm\ U}\iff} d\mid a,b,c\!\!\!\color{#c00}{\overset{\rm\ U}\iff} d\,\mid (a,b),c\!\!\!\color{#c00}{\overset{\rm\ U}\iff} d\mid ((a,b),c)$

This is the associative property of the GCD. In the same way, by induction, we can erase (or normalize) brackets in $n$-argument gcds, showing general associativity of the gcd, e.g. see here.

Remark $\ $ For completeness, below is a proof of the $\rm\color{#c00}{red\ arrows\ U}$

Lemma $\ \ d\mid a_1,\ldots,a_n\!\iff d\mid (a_1,\ldots,a_n)\ \ \ $ [GCD Universal Property]

${\bf Proof}\quad\ d\mid a_1,\ldots,a_n\Rightarrow\, d\mid (a_1,\ldots,a_n) = j_1 a_1\!+\ldots+j_n a_n\,$ for some $\, j_i\in\Bbb Z,\,$ by Bezout.

$\qquad\qquad\, d\mid (a_1,\ldots,a_n)\mid a_1,\ldots,a_n\,\Rightarrow\, d\mid a_1,\ldots,a_n\,$ by transitivity of $ $ "divides".

Dually we have the universal property of LCM

Lemma $\ \ a_1,\ldots,a_n\mid m\iff {\rm lcm}(a_1,\ldots,a_n)\mid m\ \ \ $ [LCM Universal Property]

These universal properties are the definitions of GCD & LCM in more general rings - where the Bezout identity need not hold true, e.g. in $\,\Bbb Z[x]\,$ and $\,\Bbb Q[x,y]\,$ where the gcds $\,(x,2) = 1 = (x,y)\,$ cannot be written as linear combinations. Follow the links for further details.

$\endgroup$
  • $\begingroup$ How is it concluded (generally) that for evry $d|a,b \Rightarrow$ $d|\gcd(a,b)$? $\endgroup$ – Meitar Abarbanel Mar 14 '15 at 13:51
  • $\begingroup$ @Meitar See the added Remark. $\endgroup$ – Bill Dubuque Mar 14 '15 at 13:55
  • $\begingroup$ Oh... I wasn't taught Bezout theorem. I shall look for it. $\endgroup$ – Meitar Abarbanel Mar 14 '15 at 13:59
  • $\begingroup$ @Meitar I added a link to a simple, conceptual proof. $\endgroup$ – Bill Dubuque Mar 14 '15 at 14:01
  • 1
    $\begingroup$ @Elvin $\ a\mid b\ $ means $a$ divides $b,\,$ i.e. $\,an = b\,$ for some integer $\,n.\,$ This is widely used notation in number theory. $\endgroup$ – Bill Dubuque Sep 24 '19 at 13:48
7
$\begingroup$

The def of $d=\gcd(a,b)$ is $d|a$ and $d|b$ and if $f|a$ and $f|b$ then $f|d$.

Suppose $x=\gcd(a,b,c)$. Then $x|a$ and $x|b$ and $x|c$ so $x|\gcd(a,b)$ and $x|c$, so $x|\gcd(\gcd(a,b),c)$. Conversely if $x=\gcd(\gcd(a,b),c)$ then $x|\gcd(a,b)$ and $x|c$. So $x|a$ and $x|b$ and $x|c$, so $x|\gcd(a,b,c)$. Thus $\gcd(a,b,c) | \gcd(\gcd(a,b),c)$ and $\gcd(\gcd(a,b),c)| \gcd(a,b,c)$. Therefore $\gcd(\gcd(a,b),c) = \gcd(a,b,c)$

$\endgroup$
  • $\begingroup$ In the definition I was given, nothing is said about every divisor dividing the gcd. How is it shown? $\endgroup$ – Meitar Abarbanel Mar 14 '15 at 13:55
  • $\begingroup$ It doesn't need to be shown, it's part of the definition, so you can assume it once you know $d=\gcd(a,b)$ then automatically any other divisor of $a$ and $b$ must divide $d$. $\endgroup$ – Gregory Grant Mar 14 '15 at 15:30
  • $\begingroup$ Please post the definition you were given, so we can see how it differs from this one I gave. $\endgroup$ – Gregory Grant Mar 14 '15 at 15:30
  • $\begingroup$ "The greatest common divisor (gcd) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder." $\endgroup$ – Meitar Abarbanel Mar 14 '15 at 16:04
0
$\begingroup$

A different definition of gcd affords another proof.

For $p_i\in \mathbb P \land p_i\mid abc$, then $a=\prod p_i^{\alpha_i},\ b=\prod p_i^{\beta_i},\ c=\prod p_i^{\gamma_i} \Rightarrow \gcd(a,b,c)=\prod p_i^{\min(\alpha_i,\beta_i,\gamma_i)}$

Note that in some cases, an exponent $\alpha_i,\beta_i,\gamma_i$ will be $0$ when a particular $p_i$ is not a factor of one or another of $a,b,c$, but since $p_i\mid abc$, at least one of $\alpha_i,\beta_i,\gamma_i$ will be greater than $0$

Similarly, $\gcd(a,b)=\prod p_i^{\min(\alpha_i,\beta_i)}$

Hence, $\gcd(\gcd(a,b),c)=\prod p_i^{\min({\min(\alpha_i,\beta_i)},\gamma_i)}=\prod p_i^{\min(\alpha_i,\beta_i,\gamma_i)}=\gcd(a,b,c)$ QED

$\endgroup$
0
$\begingroup$

Since the minimum over a set is no greater than the minimum over a subset, $$ \begin{align} \gcd(\gcd(a,b),c) &={\min_{u,v}}^+\!\left({\min_{x,y}}^+(ax+by)u+cv\right)\\ &\ge{\min_{x,y,z}}^+(ax+by+cz)\\ &=\gcd(a,b,c)\tag1 \end{align} $$ $\gcd(a,b)\mid a,b$ and so $\gcd(\gcd(a,b),c)\mid a,b,c$. Thus, by the maximality of the gcd, $$ \gcd(\gcd(a,b),c)\le\gcd(a,b,c)\tag2 $$ $(1)$ and $(2)$ imply that $$ \gcd(\gcd(a,b),c)=\gcd(a,b,c)\tag3 $$

$\endgroup$
0
$\begingroup$

Proof: Let $d=gcd(a,b,c)$ for positive integers $a$,$b$, and $c$. Then $d\mid a$, $d\mid b$, and $d\mid c$. Hence, $d\mid gcd(a,b)$ and $d\mid c$ and so $d\mid gcd(gcd(a,b),c)$. Thus, $d\mid f$ where $f=gcd(e,c)$ and $e=gcd(a,b)$. Since $f=gcd(e,c)$, then $f\mid e$ and $f\mid c$. Hence, $f\mid a$, $f\mid b$, and $f\mid c$, so $f\mid gcd(a,b,c)$ which means $f\mid d$. Since $d\mid f$ and $f\mid d$, $d=f$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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