Friday, 8 July 2016

number theory - Confirmation of Proof: gcd(k,b)Rightarrowgcd(ka,b)=gcd(a,b)



Not sure how to approach this.




I know k and b are relatively prime. And that, x,y{Z:xk+yb=1}.



I want to show gcd. 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}...