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!
Best Answer
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.