GCD of Integers with Common Divisor/Proof 2
Jump to navigation
Jump to search
Theorem
Let $a, b \in \Z$ be integers such that not both $a = 0$ and $b = 0$.
Let $k \in \Z_{>0}$ be a strictly positive integer.
Then:
- $\gcd \set {k a, k b} = k \gcd \set {a, b}$
where $\gcd$ denotes the greatest common divisor.
Proof
\(\ds \exists x, y \in \Z: \, \) | \(\ds \gcd \set {a k, b k}\) | \(=\) | \(\ds \paren {a k} x + \paren {b k} y\) | Bézout's Identity: $\gcd \set {a k, b k}$ is the smallest such integer combination | ||||||||||
\(\ds \) | \(=\) | \(\ds k \paren {a x + b y}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds k \gcd \set {a, b}\) | Bézout's Identity |
$\blacksquare$
Sources
- 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm