We have arbitrary $a, b, c \in \mathbb N.$

Let $d$ be the biggest natural number, such that $d\mid a,\; d\mid b,\;$ and $\;d\mid c.$

Prove that $d = \gcd ( \gcd (a,b), c).$

I think that considering that d is divisible by a and b, so does their GCD have to be and since c is also a divisor of d, GCD of these two numbers has to be d.

Am I right? How do I formulate this into a real proof? If it's even correct.

  • $\begingroup$ What's the definition of greatest common divisor? $\endgroup$ – Trevor Gunn Dec 17 '17 at 19:28
  • $\begingroup$ Why all these downvotes ? The OP explained what he tried, and the question is interesting. $\endgroup$ – Yves Daoust Dec 17 '17 at 19:37
  • $\begingroup$ Also @Kate you are confusing which things divide which: $a$ and $b$ are divisible by $d$ not the other way around. This implies that $\gcd(a,b)$ is divisible by $d$ (by definition). These are the kinds of steps you need to write down. You also need to use the fact that $d$ is the biggest such number somewhere in order to finish the proof. $\endgroup$ – Trevor Gunn Dec 17 '17 at 19:43
  • $\begingroup$ " d is divisible by a and b". $d$ is (probably) NOT divisible by $a$ nor $b$. $a$ and $b$ are divisible by $d$. " so does their GCD have to be". Obviously $a$ and $b$ are divisible by $\gcd(a,b)$ but equally obviously $\gcd(a,b)$ is NOT divisible by $a$ nor $b$. You are confusing whether something divides something else with whether it is divisible by something else. If two things are not equal (and we are dealing with positive values) divisibility is strictly a one-way affair. $\endgroup$ – fleablood Dec 17 '17 at 20:02

If $d|a$ and $d|b$, then $d|\gcd(a,b)$ by definition of the $\gcd$. And if $d|c$, then $d|\gcd(\gcd(a,b),c)$.

Then, assume that $d'=\gcd(\gcd(a,b),c)>d$. This means that $d'|gcd(a,b)$ and $d'|c$, then $d'|a,d'|b$. But $d$ is the largest number with this property, a contradiction.


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.