How can we prove $\gcd(3n^2+1, 2n-3)\mid 31$

Question

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?

Answer 1

Hint: Remember that you can multiply $2n-3$ by any expression involving $n$ (something like $1.5n$ would be nice...).

Answer:

We have $$2(3n^2+1)-3n(2n-3) = 6n^2+2 - 6n^2 + 9n = 9n+2$$ and $$2(9n+2) - 9(2n-3) = 18n+4-18n+27=31$$ so the $\gcd$ of $3n^2+1$ and $2n-3$ must be a factor of $31$ regardless of the value of $n$.

Answer 2

This gcd is computable mechanically by a slight generalization of the Euclidean algorithm which allows us to scale by integers $\,\color{#c00}c\,$ coprime to the gcd in a GMR = GCD Modular Reduction step i.e.

$$\bbox[8px,border:2px solid #c00]{(a,b)\, = \,(a,\,\color{#c00}c\:\!b)\ \ \ {\rm if}\ \ \ (a,c) = 1}\quad\ {\rm GMR}'\ \, $$

$$\begin{align} {\rm thus}\ \ \ (2n\!-\!3,\, 3n^2\!+\!1) &= (2n\!-\!3,\, \color{#c00}4(3n^2\:\!+\,1))\ \ {\rm by}\ \ \color{#c00}{c=4}\ \ \rm above\\[.2em] &= (\color{#0a0}{2n\!-\!3},\, 3(\color{#0a0}{2n})^2\!+4)\\[.2em] &= (2n\!-\!3,\, 3\,(\,\color{#0a0}3\,)^2\!+4)\ \ \rm{divides}\,\ 31 = 3(\color{#0a0}3)^2\!+4 \end{align}\qquad\quad $$

where the final equality uses $\,(a,b) = (a,b')\ $ if $\color{#0a0}{\bmod a\!:\ b\equiv b'},\,$ i.e. $\rm GMR,\,$ which here is $\bmod\, \color{#0a0}{2n\!-\!3}\!:\,\ \color{#0a0}{2n\equiv 3}\Rightarrow f(\color{#0a0}{2n})\equiv f(\color{#0a0}3)$ for any polynomial $f(x)$ with integer coefficients, by PCR= Polynomial Congruence Rule (= composition of Sum & Product rules).

So the gcd $ = (31,2n\!-\!3)>1\!\iff\!$ $31\mid 2n\!-\!3\iff n\equiv 17\pmod{\!34}\,$ by

$\!\bmod 31\!:\ 2n\!-\!3\equiv 0\iff n\equiv \dfrac{3}2\equiv \dfrac{34}2\equiv 17\,$ via a twiddle (see here or here)

Remark $ $ Generally, if $\,(a,b)\!=\!1\,$ then $\,{\rm GMR}\Rightarrow (a,an\!+\!b)\!=\!1\,$ so $\,(\color{#c00}{a^k},an\!+\!b)\!=\!1\,$ by Euclid's Lemma, so, as above, if $\,p(x)\,$ is a polynomial of degree $\,k\,$ with integer coefficients then $$\qquad\begin{align} \bmod\!\!\!\! &\ \ \ an+b\!:\,\ p(n)\,\equiv\, p(-b/a),\,\ {\rm by}\,\ n\equiv -b/a\,\ \&\,\ \rm PCR\\[.5em] \overset{\small\rm GMR'}\Longrightarrow\,\ &\bbox[8px,border:2px solid #c00]{(an+b,\,p(n)) \,=\, (an+b,\,\color{#c00}{a^k}p(-b/a))}\end{align}\qquad$$ We can compute $\,a^kp(-b/a)\,$ in the gcd by a fraction-free method via scaling - as we did above.

Answer 3

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