Monday, 21 May 2018

elementary number theory - Proving gcdleft(fracagcd(a,b),fracbgcd(a,b)right)=1



How would you go about proving that gcd(agcd(a,b),bgcd(a,b))=1



for any two integers a and b?



Intuitively it is true because when you divide a and b by gcd(a,b) you cancel out any common factors between them resulting in them becoming coprime. However, how would you prove this rigorously and mathematically?


Answer



Very simply it can be done like this: gcd(a,b)=d.




Now we ask can: gcd(ad,bd)=e for e>1?



Well, this implies ead,ebdem=ad,en=bddem=a,den=bde is a common divisor of a,b which is greater than d, thus a contradiction as d by definition was supposed as the gcd. Hence, e=1.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

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