Let $a,k,m$ be integers. Prove that $\gcd(ka,km) = k\gcd(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! 
 A: 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.
A: This is proven using Bezout's Identity in this answer.
Bezout says that
$$
\gcd(a,b)=\inf\{ax+by\gt0:x,y\in\mathbb{Z}\}
$$
Then we simply note that
$$
\inf\{cax+cby\gt0:x,y\in\mathbb{Z}\}
$$
is both $c\gcd(a,b)$ and $\gcd(ac,bc)$.
I believe this is very similar to your proof, but I think you need to exploit the fact that $\gcd(a,b)$ is the smallest positive $ax+by$ for any $x,y\in\mathbb{Z}$.
