Show that $\gcd(5a+8, 7a+3)=1\textrm{ or } 41$. Best way to solve a problem of this sort?

Question

Let $a\in \mathbb Z$. Show that $\gcd(5a+8, 7a+3)=1\textrm{ or } 41$. Knowing that $\forall k \in\mathbb Z, \gcd(a,b)=\gcd(b, a-kb)$.

I actually know how to solve this particular problem: $\gcd(5a+8, 7a+3)=\gcd(5a+8,2a-5)=\gcd(a+18,2a-5)=\gcd(a+18:-41)$. So $(a+8:-41)\in \{1, 41\}$.

What I want to know is if there's an efficient way to solve any problem of this sort. The goal being to eliminate variables from either side of the gcd no matter the parity of the terms involved. Manually adding and substracting to each sum to have the variable $a$ cancelled. This is only the simplest example. Another one is: $\gcd(2a^2+3a-1, 5a+6)$.

Any ideas?

Answer 1

Say there is $d$ which divide both. Then $d\mid 7(5a+8)$ and $d\mid 5(7a+3)$ so $d$ divide their difference: $$d\mid 7(5a+8)-5(7a+3) = 41$$

So $d\in\{1,41\}$.