GCD of Integers with Common Divisor/Proof 2

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