# Confirmation of Proof: $\gcd(k,b) \Rightarrow \gcd(ka,b) = \gcd(a,b)$

Not sure how to approach this.

I know $k$ and $b$ are relatively prime. And that, $$\exists x, y \in \left\{\mathbb{Z} : xk + yb = 1\right\}.\tag{by Bezout’s Lemma}$$

I want to show $\gcd(ka, b) = \gcd(a,b)$. So again using the same lemma, we know, $$\exists \{x', y', x'', y''\}\subset \mathbb{Z},$$ such that $x'(ka) + y'b = d$ and $x''(a) + y''b = d'$.

Goal is to show $d = d'$ but not sure quite how to do this. Appreciate any help!

• Try showing any common divisor of $a$ and $b$ is also a common divisor of $ka$ and $b$, and vice-versa. – Dave Feb 2 '18 at 4:16
• Yup Dave's approach is better than applying Bezout's lemma (I have tried and it takes a very long time) – ElfHog Feb 2 '18 at 4:20
• Would it be correct to say for $d = gcd(a,b)$, <$d$> = {$ax + by$ | $x, y \in \mathbb{Z}$} and $d_0 = gcd(na,b)$, we know <$d$> is a cyclic subgroup of Z and is preserved under +/-. So take $x = (nx)$ and this is also in <$d$> so <$d$> = <$d_0$>...something along those lines? Sorry if I'm way off base here. – SS' Feb 2 '18 at 4:59

Let $\gcd(ka, b) =l$ and $\gcd(a, b) = m$ $\implies l\mid ka, \; l\mid b$ and $m\mid a, \; m\mid b$ since b and k are co-prime so $l\mid a$ which implies that $l\mid m$ and $m\mid a \implies m\mid ka \implies m\mid l$ Hence $l = m$. $$\gcd(ka, b) = \gcd(a, b)$$
• Use \gcd to generate $\gcd$ and \mid to generate $\mid$ so the display looks better, i.e. $$\gcd(ka, b) = l, \quad l\mid ka$$ You can also use \big| or \bigg| to change the size of $\mid$ if you were to integrate, for instance: $$\int_a^b F(x)\text{d}x = f(x)\big|_a^b = f(b) - f(a)$$ – Mr Pie Feb 2 '18 at 6:49