Common Divisor Divides Difference

From ProofWiki
Jump to navigation Jump to search

Theorem

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

That is:

$a, b, c \in \Z: c \divides a \land c \divides b$


Then:

$c \divides \paren {a - b}$


Proof 1

Let $c \divides a \land c \divides b$.


From Common Divisor Divides Integer Combination:

$\forall p, q \in \Z: c \divides \paren {p a + q b}$


Putting $p = 1$ and $q = -1$:

$c \divides \paren {a - b}$

$\blacksquare$


Proof 2

\(\ds c\) \(\divides\) \(\ds a\)
\(\ds \leadsto \ \ \) \(\, \ds \exists x \in \Z: \, \) \(\ds a\) \(=\) \(\ds x c\) Definition of Divisor of Integer
\(\ds c\) \(\divides\) \(\ds b\)
\(\ds \leadsto \ \ \) \(\, \ds \exists y \in \Z: \, \) \(\ds b\) \(=\) \(\ds y c\) Definition of Divisor of Integer
\(\ds \leadsto \ \ \) \(\ds a - b\) \(=\) \(\ds x c - y c\) substituting for $a$ and $b$
\(\ds \) \(=\) \(\ds \paren {x - y} c\) Integer Multiplication Distributes over Addition
\(\ds \leadsto \ \ \) \(\, \ds \exists z \in \Z: \, \) \(\ds a - b\) \(=\) \(\ds z c\) where $z = x - y$
\(\ds \leadsto \ \ \) \(\ds c\) \(\divides\) \(\ds \paren {a - b}\) Definition of Divisor of Integer

$\blacksquare$


Sources