Common Divisor Divides Difference/Proof 2
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
\(\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$