Find all possible values of $(7a+12,3a+5)$.

Question

If $a$ is an integer. Find all possible values of $(7a+12,3a+5)$.

I started with:

Let $d$=$gcd(7a+12, 3a+5)$.

Then $d|7a+12$ and $d|3a+5$.

I am not sure what to do after this.

I have seen online someone saying that

$(3)(7a+12)+(-7)(3a+5)=1$

and that $d=1$ but I don't understand how.

Answer 1

But you found the very solution: when a linear combination $ax+by=1$, we have that $\operatorname{gcd}(a,b)=1$, as $\operatorname{gcd}(a,b)\mid (ax+by)$, hence $\operatorname{gcd}(a,b)\mid1$.

Answer 2

Note that $$(m,n)= (m,m-n)$$

Thus $$(7a+12,3a+5)=(7a+12 -(3a+5), 3a+5)$$

$$=(4a+7, 3a+5) = (a+2,3a+5 )$$

$$= (a+2,2a+3)= (a+2,a+1)=1$$

Answer 3

If $d$ is the greatest common divisor, then $d\bigm|\bigl(3(7a+12)-7(3a+5)\bigr)$, hence $d\mid 1$.

Indeed, $7a+12=dr$ and $3a+5=ds$, for some integers $r$ and $s$. Then $$ 3(7a+12)-7(3a+5)=3dr-7ds=d(3r-7s) $$

Removing $a$ this way should be the first thing to do. If we change the problem into finding the possible values of $\gcd(7a+12,3a+4)$, the same computation would tell us that the gcd divides $$ 3(7a+12)-7(3a+4)=8 $$ so the possible values would be $1$, $2$, $4$ or $8$. Further analysis may (perhaps) exclude some of these, or prove that there's a suitable $a$ for each of the cases.