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!
It's simple if you use matrices. Suppose a positive integer $d$ divides both $a + b$ and $2a + 3b$. This can be restated as $d$ dividing both entries of the vector
\begin{equation}\begin{bmatrix} 1 & 1 \\ 2 & 3\end{bmatrix}\begin{bmatrix} a \\ b\end{bmatrix}\end{equation} Multiplying on the left by the inverse matrix, which has integer coefficients, $d$ must therefore also divide each entry of \begin{equation}\begin{bmatrix} 3 & -1 \\ -2 & 1\end{bmatrix}\begin{bmatrix} 1 & 1 \\ 2 & 3\end{bmatrix}\begin{bmatrix} a \\ b\end{bmatrix}\end{equation} \begin{equation}=\begin{bmatrix} a \\ b\end{bmatrix}\end{equation} Thus $d$ divides both $a$ and $b$ and hence is $1$. Thus $gcd(a+b,2a + 3b) = 1$.