How can we prove $\gcd(3n^2+1, 2n-3)\mid 31$ I want to show that $\gcd(3n^2+1, 2n-3)$ divides 31 $\forall n\in\mathbb{N}$.
I have tried to begin by eliminating the $3n^2$ factor on the left by adding and subtracting multiples and powers of $2n-3$ but I still haven't figured out how. Can someone give me some hint?

Note if $\gcd(k,a) = 1$ then $\gcd(a, b) = \gcd(a, bk)$.  THis is because $k$ having no factors in common with $a$ then multiplying $b$ by $k$ will not add any common factors of $a$.
And as $3|3n^2$ then $3\not \mid 3n^2 + 1$.  And as $2|2n$ then $2\not \mid 2n-3$.  And as $3,2$ are prime $\gcd(3n^w+ 1, 3) = 1$ and $\gcd(2n-3, 2) = 1$.
SO $\gcd(3n^2 +1, 2n-3) = \gcd(2\cdot (3n^2 + 1), 3\cdot (2n-3))=$
$\gcd (6n^2 + 2, 6n -9)= $
$\gcd([6n^2 + 2] - n[6n-9], 6n-9) = \gcd(9n + 2, 6n - 9)=\gcd(9n+ 2, 2n-3)$
Againd $3\not \mid 9n + 2$ and $2\not \mid 2n-3$ so
$\gcd(9n + 2, 2n-3) = \gcd(2(9n+2), 9(2n-3))=\gcd(18n +4 , 18n - 27)=$
$\gcd([18n + 4] - [18n-27], 18n - 27) = \gcd(31, 18n-27)$.
Now $31$ is prime.  So either $31 \mid 18n -27$ or $31$ has no factors in common.
So either $\gcd (31, 18n-27)=\begin{cases} 31 &\text{if } 31|18n-27\\ 1&\text{if } 31 \not \mid 18n-27\end{cases}$.
And as $1|31$ and $31|31$ we have $\gcd(3n^2 + 1, 2n -3 )$ is a divisors of $31$.
....
Actually if those multiplying terms by $3$ and $2$ rub you the wrong way (they rub me the wrong way)
Consider Bezout's lemma
If we can find $M (3n^2 + 1) + N(2n-3) = 31$ where $N$ and $M$ are integers (and any polynomial with integer coefficients in terms of $n$ will be evaluated as integers for all $n$) the we have $\gcd(3n^2 + 1, 2n-3)|31$.
And we have $2(3n^2 + 1) - 3n(2n -3) = 9n +2$
$4(3n^2 + 1) - 6n(2n-3) = 18n + 4 = 9(2n-3) + 31$
$4(3n^2 + 1) - (6n+9)(2n-3) = 31$.
We are done.
We are still multiplying in extra terms but... well, its clearer to me that it is allowable
