Friday, 8 July 2016

number theory - 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!


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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...