Prove $\gcd(ka,kb)=k\cdot\gcd(a,b)$

Question

This is my proof

Let $m$ be $\gcd(ka,kb)$ then exists $s$ and $t$ such that

$ska+ tkb = m => k(sa+tb) = m $

$=> sa + tb = m/k$ (1)

since (1) is linear combination of $a$ and $b$ and $m$ is smallest positive linear combination of $ka$ and $kb$ => $m/k$ is smallest positive then $\gcd(a,b) = m/k$.

Is this proof is good enough to prove $\gcd(ka,kb)=k\cdot \gcd(a,b)$

Answer 1

Let $a=p_{1}^{q_{1}}p_{2}^{q_{2}}...p_{k}^{q_{k}}$ and $b=p_{1}^{r_{1}}p_{2}^{r_{2}}...p_{k}^{r_{k}}$ be their respective prime decompositions.

Thus, $gcd(a,b)=p_{1}^{\min(q_{1},r_{1})}p_{2}^{\min(q_{2},r_{2})}...p_{k}^{\min(q_{k},r_{k})}$

Now, if $k=p_{1}^{s_{1}}p_{2}^{s_{2}}...p_{k}^{s_{k}}$ , then

$ka=p_{1}^{s_{1}+q_{1}}p_{2}^{s_{2}+q_{2}}...p_{k}^{s_{k}+q_{k}}$ and $kb=p_{1}^{s_{1}+r_{1}}p_{2}^{s_{1}+r_{1}}...p_{k}^{s_{k}+r_{k}}$

Now, note that $\min(i+x,j+x)=x+\min(i,j)$. Hence,

$$gcd(ka,kb)=p_{1}^{\min(s_{1}+q_{1},s_{1}+r_{1})}p_{2}^{\min(s_{2}+q_{2},s_{1}+r_{1})}...p_{k}^{\min(s_{k}+q_{k},s_{k}+r_{k})}$$ $$=(p_{1}^{s_{1}}p_{2}^{s_{2}}...p_{k}^{s_{k}})(p_{1}^{\min(q_{1},r_{1})}p_{2}^{\min(q_{2},r_{2})}...p_{k}^{\min(q_{k},r_{k})})$$ $$=k \cdot gcd(a,b)$$ Hence proved.

Basically, this has the simple intuition that by the definition of gcd, the gcd is the collection of the common factors. So, when we replace $a$ by $ka$ and $b$ by $kb$, there is one extra factor added to this collection, and that factor is nothing but $k$. Hence, we get the result.