 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 combinationsIt contains $m$, so the well-ordering principle gives a least element $d_0=am+bn$. By Euclidean division, write $m=q{d}_0+r$ with $0\le r<d_0$. Thenis 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$ andThis 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\ge 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\le kd$. Therefore without using prime factorization,