# Proving $\gcd(n^2(n^2+1),2n+1)=\gcd(2n+1,5)$

We suppose $\forall n \in \mathbb {N}\setminus{0}$.

How can I prove that $\gcd(n^2(n^2+1),2n+1)=\gcd(2n+1,5)$?

-
Since $n^2$ and $2n+1$ are coprime, the $n^2$ on the lhs can be dropped. –  Lior B-S Mar 28 at 21:51

\begin{align} (2n+1)^4 - 16n^2(n^2+1) & = 32n^3 + 8n^2 + 8n+1\\ 4(2n+1)^3 - (32n^3 + 8n^2 + 8n+1) & = 40n^2+16n+3\\ 10(2n+1)^2 - (40n^2+16n+3) & = 24n+7\\ 12(2n+1) - (24n+7) &= 5 \end{align} Hence, \begin{align} \gcd(n^2(n^2+1),2n+1) & = \gcd(32n^3 + 8n^2 + 8n+1,2n+1)\\ & = \gcd(40n^2+16n+3,2n+1)\\ & = \gcd(24n+7,2n+1)\\ & = \gcd(2n+1,5) \end{align}

-
You mean Euclid's algorithm: divide them and carry on with the remainder.. –  Berci Mar 28 at 21:23
@Berci Yes.${}{}$ –  ShikariShambu Mar 28 at 21:26
The gcd is unchanged if we multiply $n^2(n^2+1)$ by any power of $2$. Now division by $2n+1$ is straightforward. –  André Nicolas Mar 28 at 21:28
@Marvis Could you please show the quotient and remainder and can the power of 2 wouldn't change anything. –  pourjour Mar 28 at 22:44

$\rm mod\,\ {2n\!+\!1}\!:\ \color{#C00}{2n\equiv-1}\,\Rightarrow\,16(n^4\!+\!n^2)\equiv (\color{#C00}{2n})^4\!\!+4(\color{#C00}{2n})^2\!\equiv (\color{#C00}{-1})^4\!\!+4(\color{#C00}{-1})^2\!\equiv\, \color{#0A0}5,\$ therefore

$\rm\qquad (\color{#C00}{2n\!+\!1},\color{#0A0}5)=(2n\!+\!1,16(n^4\!+\!n^2)) = (2n\!+\!1,n^4\!+\!n^2)\,\$ by $\rm\ (2n\!+\!1,16)=1\$ and Euclid, and

since $\rm\quad\,\ (\color{#C00}a,\,\color{#0A0}b) =\, (a,\,c) \ \ if\ \ b\equiv c\:\ (mod\ a)\ \$ [modular gcd law, heart of Euclidean algorithm]

-
nice observation (+1) –  robjohn Mar 28 at 22:44

Hints:

(1) For any $\,n\in\Bbb N\;,\;\;(2n+1,5)=1\,\,\vee\; 5\,$ ;

(2) We have

$$2n+1=0\pmod 5\,\implies n=2\pmod 5\implies n^2(n^2+1)=4\cdot 5= 0\pmod 5\ldots$$

-
That shows only the easy part: $\rm\:c=(2n\!+\!1,5)\mid (2n\!+\!1,n^4\!+\!n^2)=d.\:$ The less trivial opposite direction, that $\rm\:d\mid c,\:$ also requires proof. –  Math Gems Mar 28 at 22:31
(1) That's your opinion, (2) Those are hints ... –  DonAntonio Mar 29 at 3:13
If you believe it shows that $\rm\:d\mid c\:$ then please do explain how. –  Math Gems Mar 29 at 3:33
I think you're overlooking the word "hint"...and I never claimed it shows anything: it suggests. –  DonAntonio Mar 29 at 3:35
Imo, if one is giving a hint to only part of the answer, esp. an easier part, then one should explicitly mention that. Else it could mislead the OP into thinking that nothing more needs to be done. –  Math Gems Mar 29 at 4:11
show 1 more comment

Using the Euclidean Algorithm, we get $$16n^2(n^2+1)-(8n^3-4n^2+10n-5)(2n+1)=5\tag{1}$$ Therefore, $(n^2(n^2+1),2n+1)\mid5$.

Furthermore, since $(5,16)=1$, we have $5\mid2n+1\Longleftrightarrow5\mid n^2(n^2+1)$. Thus, $$(n^2(n^2+1),2n+1)=(2n+1,5)\tag{2}$$

-
Where's the Euclid-Wallis table? Under the table calculations, eh? –  Math Gems Mar 28 at 22:37
@MathGems: I did use it, but I kept it on paper. It did not need to be copied to the answer. Things get a bit unwieldy with polynomials. –  robjohn Mar 28 at 22:40
Yes, of course I was joking. In this case Gauss trumps Euclid and Bezout, since the modular approach is a one liner, but the extended gcd calculation is an order of magnitude more work (too big apparently to fit into MSE margins!) Did you ever do a polynomial example on MSE? –  Math Gems Mar 28 at 22:46
I have done one or two (to get Padé approximations if I remember), but I forget if it was on sci.math or MSE. It was probably on sci.math. I found this, but it is standard Euclidean Algorithm. –  robjohn Mar 29 at 1:26
It would be nice to have one protoypical example to refer to, but perhaps this one is too unwieldly. Do you see how the Bezout relation is related to the calculation that I did, and why the cubic cofactor of $\,2n+1\,$ is not really needed? I hope to find some time soon to explain further how the method in my answer works in general (non-monic factor theorem, localization, etc). –  Math Gems Mar 29 at 1:35