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!
Answer
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)$$
No comments:
Post a Comment