# 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!

• why x should be a/d ?
– user268307
Commented Sep 21, 2015 at 19:11
• $\gcd(5\cdot 1 + 2, 3\cdot 1 + 2\cdot 2)$ Commented Sep 21, 2015 at 19:12
• @AnuragJain I thought that if ax + by = d then d = a divisor of a and b ? I might be mixing this up with something else though =S Commented Sep 21, 2015 at 19:18
• Similar to math.stackexchange.com/q/1105240/589.
– lhf
Commented Sep 22, 2015 at 1:46

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.

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\cdot\lvert\det({A})\rvert$$.

• See this Apr 14 '11 answer for an explicitly worked example, and connections with Gaussian arithmetic. Commented Nov 5, 2016 at 13:54

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.