True or False: $\operatorname{gcd}(a,b) = \operatorname{gcd}(5a+b, 3a+2b)$ I'm trying to work through the above homework question ($a$ and $b$ are positive integers), and I'm not sure if my reasoning is correct. 
I've been told that it is true.
I think that if the $\operatorname{gcd}(a,b) = d$, then we would have $ax +by = d$. where $\frac{a}{d} = x$ and $\frac{b}{d} = y$. 
Then if I divide both $5a + b$ and $ 3a + 2b$ by $d$ I get $5x +y$ and $3x+2y$ respectively. Assuming that  $x \neq y$ (which seems safe to say...unless $a=b$) there are no common factors between $5$ and $1$ in the first bit, and $3$ and $2$ in the second bit, so there isn't anything I can factor out. 
The problem I'm having is that although this doesn't ask for a proof, because I can't provide one for myself, I'm not sure if my process is correct. 
Any hints, or suggestions would be greatly appreciated! 
 A: Note that if $a=1,b=2$ then $\gcd(a,b)=1$ but $\gcd(5a+b,3a+2b)=7.$
Some elaboration on method:
One way to do this kind of problem is to use linear operations to get multiples of $a,b$ separately. Here $2(5a+b)-(3a+2b)=7a,$ while $-3(5a+b)+5(3a+2b)=7b.$ So in this example so far we know $\gcd(5a+b,3a+2b)$ must divide both $7a$ and $7b.$ [If in another example we wound up with coprime coefficients in front of $a,b$ at this stage, the gcd of the two linears would divide the gcd of $a,b$] Since the method so far only shows $\gcd(5a+b,3a+2b)$ is a divisor of $7 \gcd(a,b),$ it seemed useful to see if both linear terms could be made to be some multiple of $7$, which worked here.
Note: Going through the algebra, I found that the constants in front of $u_i=p_i a + q_i b$ ($i=1,2$) after elimination of each of $a,b$ is always $\pm D,$ where $D=p_1q_2-p_2q_1,$ the determinant of the system. Also it is easy using Cramer's rule to solve $u_1=u_2=D$ for integers $a,b.$ The expressions for $a,b$ in this solution are $\pm(p_1-p_2), \pm(q_1-q_2),$ so this approach doesn't necessarily lead to an example like the above, unless $|D|\ge 2$ and also the solutions for $x,y$ just mentioned happen to be coprime.
A: More generally, let $A$ be an integer matrix and let
$$
\begin{bmatrix}
u \\ v
\end{bmatrix}
=
A
\begin{bmatrix}
a \\ b
\end{bmatrix}
$$
Then Cramer's rule says that
$$
\mathrm{adj}({A}) \,  {A} = \det({A}) \, {I}
$$
where $ \mathrm{adj}({A})$ is the adjugate matrix (the transpose of the cofactor matrix), and so
$$
\det({A})
\begin{bmatrix}
a \\ b
\end{bmatrix}
=
\mathrm{adj}({A})
\begin{bmatrix}
u \\ v
\end{bmatrix}
$$
Let $d=\gcd(a,b)$ and $\delta=\gcd(u,v)$.
Then $d \mid \delta$ by the first matrix equation and $\delta \mid d\,|\det({A})| $ by the second matrix equation.
In particular, $\delta = d$ if $\det({A})=\pm 1$.
But in general $\delta$ can be as large as $d\,|\det({A})|$.
A: If x>1 and x  divides 5a+b and 3a+2b then x divides 2(5a+b)-(3a+2b)=7a and x divides divides 3(5a+b)-5(3a+2b)=-7b. So x divides a and b, OR x=7. A little trial and error shows that if a=1 and b=2 then 5a+2b=3a+2b=7=gcd(5a+b,3a+2b) but gcd(a,b)=gcd(1,2)=1. So it is false. The trial and error was to find a and b not divisible by 7, when 5a+b and 3a+2b are divisible by 7.
