Thursday, 21 November 2013

elementary number theory - Compute $gcd(a+b, 2a+3b)$ if $gcd(a,b) = 1$

A question from a problem set is asking to compute the value of $\gcd(a+b, 2a+3b)$ if $\gcd(a+b) = 1$, or if it isn't possible, prove why.



Here's how I ended up doing it:



$\gcd(a,b) = 1$ implies that for some integers $x$, and $y$, that $ax+by = 1$.



Let $d = gcd(a+b, 2a+3b)$. This implies:



$\implies \text{d is divisible into }2(2a+3b) - 4(a+b) = 2b\cdots (1)$




$\implies \text{d is divisible into} 6(a+b) - 2(2a+3b) = 2a\cdots (2)$



Statement $(1)$ implies that $d$ divides $2by$ for some integer $y$



Statement $(2)$ implies that $d$ divides $2ax$ for some integer $x$



This implies that $d$ is divisible into $2(ax+by)$, which implies:



$\gcd(a+b, 2a+3b) =\text{ either 1 or 2}$




Thus the result is not generally determinable as it takes $2$ possible values.



Are my assumptions and logic correct? If not, where are the errors?



Thank you!

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}...