Greatest common divisor with one parameter and condition

Question

I have this homework question:

Find $d = \gcd(10x+6, 3x+1) $ where $d > 5$ and $x$ is natural

How can I solve it?

Answer 1

$$\gcd(10x+6,3x+1) = \gcd(10x+6 - 3(3x+1), 3x+1) = \gcd(x+3, 3x+1) = \gcd(3x+1 - 3(x+3), x+3) = \gcd(-8, x+3) = \gcd(8, x+3)\text{.}$$ The only way the gcd can be $>5$ is to be $8$. So for what $x$ does that happen?

Answer 2

$d\mid \color{#c00}{10x\!+\!6},\color{#0a0}{3x\!+\!1}\,\Rightarrow\,d\mid \overbrace{3(\color{#c00}{10x\!+\!6})-10(\color{#0a0}{3x\!+\!1})}^{\large {\rm eliminate}\ x}=8,\ $ so $\ d\mid 8,\,\ d>5\,\Rightarrow\,d = 8\ \ $ QED