# 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 '13 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 '13 at 21:23
@Berci Yes.${}{}$ – user17762 Mar 28 '13 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 '13 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 '13 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 '13 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 '13 at 22:31
(1) That's your opinion, (2) Those are hints ... – DonAntonio Mar 29 '13 at 3:13
If you believe it shows that $\rm\:d\mid c\:$ then please do explain how. – Math Gems Mar 29 '13 at 3:33
I think you're overlooking the word "hint"...and I never claimed it shows anything: it suggests. – DonAntonio Mar 29 '13 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 '13 at 4:11

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 '13 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 '13 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 '13 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 '13 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 '13 at 1:35