Given an integer $a$, suppose $d=\gcd(3a+5,\,5a+7)>2$. Determine $d$. The only solution that I have been able to come up with is $d=1$, but because $d>2$, I can't seem to figure out how to find a solution.
 A: 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$
A: 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$.
