The following question is from Pinter's Abstract Algebra:

Suppose that for all integers $x$, $x|a$ and $x|b$ if and only if $x|c$. Prove $c = \gcd(a,b)$.

The definition of greatest common divisor is the usual two conditions:
(1) $c$ is a common divisor of $a$ and $b$; and
(2) any common divisor of $a$ and $b$ must divide $c$.

Further, here $\gcd$ means the greatest common positive divisor.

I just can't seem to figure out how to approach the problem.
I've tried starting with the following idea: if we have $x|a \iff x|c$, then we have that either $a|c$ or $c|a$. Similarly, $b|c$ or $c|b$.
If I could then deduce that $c|a$ and $c|b$ then it would be possible to almost conclude it there, but there appears to be no way to get to this point.

Any help would be appreciated, thanks.

  • $\begingroup$ Notice that $c$ divides $c$, so $c$ divides $a$ and $b$. Also, $\gcd(a,b)$ divides $a$ and $b$, so $\gcd(a,b)$ divides $c$. $\endgroup$ – awllower Jan 30 '18 at 13:06

As John Hughes points out you need $c > 0$.

Suppose $x|a$ and $x|b$ implies $x|c$. Since $\gcd(a,b)$ divides both $a$ and $b$, it divides $c$ too. Thus $\gcd(a,b) | c$ and in particular $\gcd(a,b) \le c$. (Here you need $c > 0$).

Suppose $x|c$ implies $x|a$ and $x|b$. Since $c|c$, you conclude that $c|a$ and $c|b$. Thus $c$ is a common divisor of $a$ and $b$ it cannot exceed the greatest common divisor, so $c \le \gcd(a,b)$.

If both implications hold you get $c = \gcd(a,b)$.


This claim is false. For instance, if $c = -1$, $a = 2$ and $b = 3$, the conditions are met, but $gcd(2, 3) = +1$, not $-1$.

  • $\begingroup$ Sorry, I think we need $c>0$. The book is a bit lax in pointing out this requirement, I'll make an edit. $\endgroup$ – K.Reeves Jan 30 '18 at 13:12
  • $\begingroup$ You might want to get a better book. I also suggest that in general, you spend a few minutes trying both to prove things and to DISprove them. Your failure to disprove can often show you how you might prove them. (Or, in some cases, show you that the author of your book is sloppy, and you should treat all future problems with deep suspicion.) $\endgroup$ – John Hughes Jan 30 '18 at 13:22

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.