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.
Answer
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)$.
No comments:
Post a Comment