= Solution
The <greatest common divisor> $d=\gcd(m,n)$ is the largest positive integer dividing both $m$ and $n$. To prove <Bézout's identity> without assuming a factorization theorem, consider the nonempty set of positive integer linear combinations
$$
\mathcal L=\{am+bn>0:a,b\in\mathbb Z\}.
$$
It contains $m$, so the <well-ordering principle> gives a least element $d_0=am+bn$. By <Euclidean division>, write $m=qd_0+r$ with $0\leq r<d_0$. Then
$$
r=(1-qa)m-qbn
$$
is another integer linear combination. If $r>0$, it contradicts minimality, so $r=0$ and $d_0\mid m$. Applying the same argument to $n$ gives $d_0\mid n$. Conversely, every common divisor divides every integer linear combination and therefore divides $d_0$. In particular every positive common divisor is at most $d_0$. Thus $d_0=d$ and
$$
\boxed{\gcd(m,n)=am+bn\quad\text{for some }a,b\in\mathbb Z.}
$$
This also proves the requested divisibility implication for any integer $k$: if $k\mid m$ and $k\mid n$, then $k\mid(am+bn)=d$.
For the <scaling identity for greatest common divisors>, put $D=\gcd(km,kn)$ with $k>0$. Since $kd$ divides $km$ and $kn$, $D\geq kd$. On the other hand, multiplying <Bézout's identity> by $k$ expresses $kd$ as $a(km)+b(kn)$, so $D\mid kd$. Positivity gives $D\leq kd$. Therefore \b[without using prime factorization],
$$
\boxed{\gcd(km,kn)=k\gcd(m,n).}
$$
Back to article page
