Common Divisor Divides Integer Combination

From ProofWiki

Jump to: navigation, search

Theorem

Let $\left({D, +, \times}\right)$ be an integral domain.

Let $c$ be a common divisor of two elements $a$ and $b$ of $D$.

That is:

$a, b, c \in D: c \backslash a \land c \backslash b$.

Then:

$\forall p, q \in D: c \backslash \left({p \times a + q \times b}\right)$

Let $c$ be a common divisor of two integers $a$ and $b$.

That is:

$a, b, c \in \Z: c \backslash a \land c \backslash b$.

Then $c$ divides any integer combination of $a$ and $b$:

$\forall p, q \in \Z: c \backslash \left({p a + q b}\right)$

$\displaystyle $	$\displaystyle c \backslash a$	$\implies$	$\displaystyle \exists x \in D: a = x \times c$	$\displaystyle $
$\displaystyle $	$\displaystyle c \backslash b$	$\implies$	$\displaystyle \exists y \in D: b = y \times c$	$\displaystyle $
$\displaystyle $	$\displaystyle $		$\displaystyle \forall p, q \in D: p \times a + q \times b = p \times x \times c + q \times y \times c = \left({p \times x + q \times y}\right) c$	$\displaystyle $
$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle \exists z \in D: p \times a + q \times b = z \times c$	$\displaystyle $
$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle c \backslash \left({p \times a + q \times b}\right)$	$\displaystyle $

$\blacksquare$

Follows directly from the fact that Integers form Integral Domain.

$\blacksquare$

\(\displaystyle \)	\(\displaystyle c \backslash a\)	\(\implies\)	\(\displaystyle \exists x \in D: a = x \times c\)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle c \backslash b\)	\(\implies\)	\(\displaystyle \exists y \in D: b = y \times c\)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle \forall p, q \in D: p \times a + q \times b = p \times x \times c + q \times y \times c = \left({p \times x + q \times y}\right) c\)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \exists z \in D: p \times a + q \times b = z \times c\)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle c \backslash \left({p \times a + q \times b}\right)\)	\(\displaystyle \)