1
$\begingroup$

I've come up with this question in a programming book, and couldn't figure it out :

Given four positive integers $a, b, c$ and $d$, explain what value is computed by $\gcd(\gcd(a, b), \gcd(c, d))$.

$\endgroup$
  • 1
    $\begingroup$ Recall gcd is associative $\endgroup$ – Bill Dubuque Apr 12 '15 at 14:31
  • $\begingroup$ Instead of recalling that gcd is associative, maybe one should suggest that the poster learn that gcd is associative, perhaps by writing a proof. $\endgroup$ – Michael Hardy Jul 6 '15 at 19:21
1
$\begingroup$

Let $g=\gcd(\gcd(a, b), \gcd(c, d))$. Then by the definition $g\mid \gcd(a, b)$ and since $\gcd(a, b)\mid a, \gcd(a, b)\mid b$ therefore $g\mid a$ and $g\mid b$. similarly $g\mid c$ and $g\mid d$. So g is a common divisor of these four integers. To see why $g$ is the greatest common divisor of these integers, assume that $f$ is any common divisor of $a,b,c$ and $d$. Then $f\mid a$ and $f\mid b$ and hence $f\mid \gcd(a, b)$ and indeed, $f\mid \gcd(c, d)$. So $f$ must divide $\gcd(\gcd(a, b), \gcd(c, d))$ or $f\mid g$. By the definition, $g$ is the greatest common divisor of $a,b,c$ and $d$.

$\endgroup$
2
$\begingroup$

Your title give the answer: the expression gives the greatest common divisor of all four of the integers $a,b,c,$ and $d$.

This is the largest integer that divides all four of the numbers. Such a number exists since $1$ divides all four numbers and anything larger than the maximum of the four numbers will not divide any of them.

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