Given an integer $a$, suppose $d=\gcd(3a+5,\,5a+7)>2$. Determine $d$.

Below are hints/sketches for $\,4\,$ proofs, by elimination and Euclid's algorithm, and linear algebra.

$(1)\ \ d\mid 3a\!+\!5,5a\!+\!7\,\Rightarrow\,d\mid 5(3a\!+\!5)\!-\!3(5a\!+\!7) = 4\ $ by eliminating $\,a.\,$ Done modularly:

$(2)\ \ {\rm mod}\ d\!:\ 5\equiv -3a, -5a\equiv 7\,\Rightarrow\, 5\cdot 5\equiv -15a \equiv 3\cdot 7\,\Rightarrow\,0\equiv 25\!-\!21\equiv 4\,$ so $\,d\mid 4$

or, via fractions: $\ \dfrac{5}3\equiv -a\equiv \dfrac{7}5\,$ so cross multiplying $\Rightarrow\, 5\cdot 5\equiv 3\cdot 7\,\Rightarrow\, 4\equiv 0\,\Rightarrow\, d\mid 4$

$(3)\ $ By Euclid $\,(3a\!+\!5,5a\!+\!7)=(2a\!+\!2,5a\!+\!7)=(2a\!+\!2,a\!+\!3)=(-4,a\!+\!3)$

$(4)\ $ The linear map $\rm\,(a,1)\mapsto (5a\!+\!7,3a\!+\!5)\,$ has $\, \det = 5\cdot 5-7\cdot 3=\color{#c00}{4},\,$ therefore, by this very simple theorem $\ \gcd(5a\!+\!7,3a\!+\!5)\mid \color{#c00}4\gcd(a,1)= 4$

The GCD of a pair of numbers is equal to the GCD of either number and the difference of the two numbers. For instance the GCD of $28$ and $36$ is equal to the GCD of $28$ and $8$.

This can be continued until you end up with numbers that are equal to one another, at which point their GCD is themselves. So the GCD of $28$ and $8$ equals the GCD of $20$ and $8$, equals the GCD of $12$ and $8$, equals the GCD of $8$ and $4$, equals the GCD of $4$ and $4$, which equals $4$.

Now try the same thing with $3a+5$ and $5a+7$.