Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$?

share|improve this question
    
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

4 Answers 4

up vote 2 down vote accepted

\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}

share|improve this answer
    
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]

share|improve this answer
    
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$$

share|improve this answer
    
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} $$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.