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