[proofplan] The proof uses only the divisibility characterisation of the [greatest common divisor](/page/Greatest%20Common%20Divisor). First we show that $|k|\gcd(a,b)$ is a common divisor of $ka$ and $kb$. Then we show that every common divisor of $ka$ and $kb$ divides $|k|\gcd(a,b)$ by cancelling the common factor $|k|$ after writing an arbitrary common divisor relative to that factor through Bezout coefficients for $a$ and $b$. [/proofplan] [step:Show that $|k|\gcd(a,b)$ divides both scaled integers] Let \begin{align*} g := \gcd(a,b). \end{align*} Since $(a,b) \ne (0,0)$, the integer $g$ is positive. By the defining divisibility property of the greatest common divisor, $g$ divides both $a$ and $b$. Hence there exist $r,s \in \mathbb{Z}$ such that \begin{align*} a = gr \end{align*} and \begin{align*} b = gs. \end{align*} Since $k \ne 0$, define \begin{align*} \varepsilon := \frac{k}{|k|}. \end{align*} Then $\varepsilon \in \{-1,1\}$ and $k=\varepsilon |k|$. Therefore \begin{align*} ka = \varepsilon |k|gr \end{align*} and \begin{align*} kb = \varepsilon |k|gs. \end{align*} Thus $|k|g$ divides both $ka$ and $kb$. [guided] Set \begin{align*} g := \gcd(a,b). \end{align*} The goal of this step is to prove that the proposed answer, namely $|k|g$, is at least a common divisor of the scaled pair. Since $(a,b) \ne (0,0)$, the greatest common divisor $g$ is positive. By the defining divisibility property of $g=\gcd(a,b)$, the integer $g$ divides $a$ and divides $b$. Therefore there are integers $r,s \in \mathbb{Z}$ with \begin{align*} a = gr \end{align*} and \begin{align*} b = gs. \end{align*} The absolute value appears because the greatest common divisor is positive, while $k$ may be negative. Since $k \ne 0$, define \begin{align*} \varepsilon := \frac{k}{|k|}. \end{align*} Then $\varepsilon$ is either $1$ or $-1$, and $k=\varepsilon |k|$. Multiplying the equations $a=gr$ and $b=gs$ by $k$ gives \begin{align*} ka = \varepsilon |k|gr \end{align*} and \begin{align*} kb = \varepsilon |k|gs. \end{align*} Because $\varepsilon r$ and $\varepsilon s$ are integers, both $ka$ and $kb$ are integer multiples of $|k|g$. Hence $|k|g$ is a common divisor of $ka$ and $kb$. [/guided] [/step] [step:Show that every common divisor of the scaled pair divides $|k|\gcd(a,b)$] Let $d \in \mathbb{Z}$ be a positive common divisor of $ka$ and $kb$. Then there exist $u,v \in \mathbb{Z}$ such that \begin{align*} ka = du \end{align*} and \begin{align*} kb = dv. \end{align*} Since $g=\gcd(a,b)$, Bezout's identity gives integers $x,y \in \mathbb{Z}$ such that \begin{align*} g = ax + by. \end{align*} Multiplying by $k$ gives \begin{align*} kg = kax + kby. \end{align*} Substituting $ka=du$ and $kb=dv$ gives \begin{align*} kg = d(ux+vy). \end{align*} Thus $d$ divides $kg$. Since $d$ is positive and divisibility is unchanged by changing the sign of the multiple, $d$ divides $|k|g$. The previous step proved that $|k|g$ is itself a positive common divisor of $ka$ and $kb$. The present step proves that every positive common divisor of $ka$ and $kb$ divides $|k|g$. By the divisibility characterisation of the greatest common divisor, \begin{align*} \gcd(ka,kb) = |k|g. \end{align*} Substituting $g=\gcd(a,b)$ yields \begin{align*} \gcd(ka,kb) = |k|\gcd(a,b). \end{align*} This proves the claimed scaling law. [/step]