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

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.

• 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$. – 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$.
• Sorry, I think we need $c>0$. The book is a bit lax in pointing out this requirement, I'll make an edit. – K.Reeves Jan 30 '18 at 13:12