GCD for Negative Integers

From ProofWiki
Jump to: navigation, search

Theorem

$\gcd \left\{{a, b}\right\} = \gcd \left\{{\left|{a}\right|, b}\right\} = \gcd \left\{{a, \left|{b}\right|}\right\} = \gcd \left\{{\left|{a}\right|, \left|{b}\right|}\right\}$


Alternatively, this can be put:

$\gcd \left\{{a, b}\right\} = \gcd \left\{{-a, b}\right\} = \gcd \left\{{a, -b}\right\} = \gcd \left\{{-a, -b}\right\}$

which follows directly from the above.


Proof

Note that $\left|{a}\right| = \pm a$.

Suppose $u \backslash a$. Then $\exists q \in \Z: a = q u$.

Then $\left|{a}\right| = \pm q u = \left({\pm q}\right) u \implies u \backslash \left|{a}\right|$.

So every factor of $a$ is a factor of $\left|{a}\right|$.

Similarly, note that $a = \pm \left|{a}\right|$, so every factor of $\left|{a}\right|$ is a factor of $a$.

So it follows that the common factors of $a$ and $b$ are the same as those of $a$ and $\left|{b}\right|$, etc., and in particular $\gcd \left\{{a, b}\right\} = \gcd \left\{{a, \left|{b}\right|}\right\}$ etc.

$\blacksquare$