elementary number theory - Let $a,k,m$ be integers. Prove that $gcd(ka,km) = kgcd(a,m)$.

Here is what I got so far:

Let $\gcd(ka,km) = d$

Then by the Euclidean Algorithm, we have integers $s,t$ such that:

$$s(ka) + t(km) = d \implies k|d $$

Let $$d/k = g = sa + tm. \tag{1}$$

So now I need to show that $g$ is indeed = $\gcd(a,m)$. Let $\gcd(a,m) = h$

Now since $k|d \implies d|a , d|m \space $ (since $$\gcd(ka,km) = d \implies g| \gcd(a,m) = h \\\implies h = dj ,$$ for some integer $j$.

Putting this into (1):

$$ h/jk = g = sa + tm $$

since $$h = dj \implies dj/j = kg \\ \implies d = kg. $$

So $g$ is the $\gcd(a,m)$?

Is this a correct proof? Or have I gone in some sort of circle? Many thanks for any hints or direction!

Answer

You seem to be on the right track, although I'm not so sure about your last step. Also, I would avoid using fractions when possible. Here's my approach.

Let $g = \gcd(a,m)$ and let $d = \gcd(ka,km)$. We want to show that $d = kg$.

Since $d = \gcd(ka,km)$, we know by the Extended Euclidean Algorithm that $d = (ka)s + (km)t$ for some $s,t \in \Bbb Z$. But then observe that $d = k(as + mt)$. Hence, it suffices to prove that $g = as + mt$.

Since $g = \gcd(a,m)$, we know by the Extended Euclidean Algorithm that $g$ is the smallest possible integer that can be expressed in the form $ax + my$, where $x,y \in \Bbb Z$. But since $as + mt$ can also be expressed in this form, we know that $\boxed{g \leq as + mt}$.

Since $g=ax+my$, we may scale this equation by $k$ to obtain $kg = (ka)x + (km)y$. But recall that $d$ is the smallest possible integer that can be expressed in the form $(ka)s + (km)t$, where $s,t \in \Bbb Z$. Hence, we have $k(as + mt)=d \leq kg$ so that cancelling the $k$ from both sides yields the inequality $\boxed{as + mt \leq g}$ (we assume, without loss of generality, that $k\geq0$).

Finally, since $g \leq as + mt$ and $as + mt \leq g$, we have shown that $g=as+mt$, as desired.