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