7
$\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\iff d\,\mid (a,b),c\!\!\!\color{#c00}{\overset{\rm\ U}\iff} d\mid ((a,b),c)$

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

Lemma $\ \ d\mid a,b,c\iff d\mid (a,b,c)\ \ \ $ [GCD Universal Property]

${\bf Proof}\quad\ d\mid a,b,c\,\Rightarrow\, d\mid (a,b,c)\,$ by $\ (a,b,c) = ia\!+\!jb\!+\!kc,\ i,j,k\in\Bbb Z,\,$ by Bezout.

$\qquad\qquad\, d\mid (a,b,c)\Rightarrow d\mid a,b,c\ $ by $\ (a,b,c)\mid a,b,c\,$ and transitivity of $ $ "divides".

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.

Dually we have the universal property of LCM

Lemma $\ \ a,b,c\mid m\iff {\rm lcm}(a,b,c)\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
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

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.