Monday, 21 May 2018

elementary number theory - Proving $gcd left(frac{a}{gcd (a,b)},frac{b}{gcd (a,b)}right)=1$



How would you go about proving that $$\gcd \left(\frac{a}{\gcd (a,b)},\frac{b}{\gcd (a,b)}\right)=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(\frac{a}{d},\frac{b}{d})=e$ for $e>1$?



Well, this implies $e\mid\frac{a}{d},e\mid\frac{b}{d} \Rightarrow em=\frac{a}{d}, en=\frac{b}{d} \Rightarrow dem=a,den=b \Rightarrow de$ 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 $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}...