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