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.

Using a spreadsheet, it can be inferred that when $n≡2[5]$, then $\gcd(n^2+1,2n+1)=5$, else $\gcd(n^2+1,2n+1)=1$.

Indeed, when $n≡2[5]$, $n^2+1$ and $2n+1$ can easily be shown to be multiples of $5$, so their gcd is at least $5$. But then, I can't see how to complete the proof.

share|improve this question
add comment

5 Answers

up vote 4 down vote accepted

As $(a,b)=(a,a-nb),$

$(2(n^2+1), 2n+1)=(2(n^2+1)-n(2n+1), 2n+1)=(2-n,2n+1)=(2-n,2n+1+2(2n-1))=(2-n,5)$

So, $(2(n^2+1), 2n+1)=5$ if $5\mid(2-n)$ i.e., if $n\equiv2\pmod 5$

$\implies (n^2+1, 2n+1)=5$ as $(2,2n+1)=1$ is as $(2n+1)$ odd.

If $n\not\equiv2\pmod 5,(2(n^2+1), 2n+1)=1\implies (n^2+1, 2n+1)=1$


Alternatively,

We know, $(a,b)\mid (ax+by)$ where $a,b,x,y$ are integers.

So, $(n^2+1, 2n+1)\mid \{n(2n+1)-2(n^2+1)\}\implies (n^2+1, 2n+1)\mid(n-2)$

Again, $(2n+1,n-2)\mid\{2n+1-2(n-2)\} \implies (2n+1,n-2)\mid 5$

If $n\equiv2\pmod 5,2n+1\equiv0 \pmod 5$ and $n^2+1\equiv2^2+1\equiv 0 \pmod 5$

hence, $(n^2+1, 2n+1)=5$

Else, $5\not\mid(n-2)\implies (2n+1,n-2)=1$ and $5\not\mid(2n+1)\implies (n^2+1, 2n+1)=1$

share|improve this answer
add comment

Note that $4(n^2+1)-(2n-1)(2n+1)=5$, Since the greatest common divisor divides any linear combination $n^2+1,2n+1$ , therefore $gcd(n^2+1,2n+1)|5$

share|improve this answer
    
+1 I was just about to add my answer, but noticed yours was identical. –  robjohn Nov 24 '12 at 0:38
add comment

Let $d=(a,b)$. Then $d| 4n^2+4n+1$ and $d|4n^2+4$ therefore $d|4n-3$. Since it also divides $4n+2$ we get $d|5$.

share|improve this answer
add comment

Let $d=\gcd(2n+1,n^2+1)$. Then since $d\mid 2n+1$ and $d\mid n^2+1$, we must also have $$d\mid(n^2+1)-(2n+1)=n(n-2)\;.$$ Clearly $\gcd(n,2n+1)=1$, and $d\mid 2n+1$, so $\gcd(n,d)=1$, and therefore $d\mid n-2$. By definition $d\mid 2n+1$, so $d\mid(2n+1)-2(n-2)=5$, and therefore $d=1$ or $d=5$.

The problem doesn’t require you to do so, but you can easily check that $d=5$ if and only if $n\equiv2\pmod 5$, so that $5\mid n-2$.

share|improve this answer
add comment

Clearly when $n=0$ the polynomials are relatively prime (gcd = 1).


notice that $2n+1$ is always odd, while $n^2 + 1$ is always even. Thus the gcd can never contain $2$ as a factor.


Let $d | n^2 + 1$ and $d | 2n + 1$, then [because $a|b$ implies $a|kb$] we have

  • $d|2n^2 + 2$
  • $d|2n^2 + n$

and [because $a|b$ and $a|c$ imply $a|c-b$] this gives us

  • $d|n-2$

we can use this (since it's degree 1) to cancel out the $n$ in our assumption $d | 2n + 1$ to get

  • $d|n + 3$

and again to get

  • $d|5$

Since $5$ is prime, we've found that the GCD of the polynomials for some $n$ must be either $1$ or $5$.


We would now like to find out exactly when the GCD is 5 (i.e. when $5|2n+1$ and $5|n^2+1$ and when it's one. For this we can use the equivalence [$a|b$ iff $b \equiv 0 \pmod a$]. So we only need to check 5 values.

n | 2n+1 | n^2+1
----------------
0 | 1    | 1
1 | 3    | 2
2 | 0    | 0     !
3 | 2    | 0
4 | 4    | 2

therefore we have proved the result:

$$\gcd(2n+1,n^2+1) = \begin{cases}5 & \text{when } n \equiv 2 \mod 5 \\ 1 & \text{otherwise}\end{cases}$$

share|improve this answer
add comment

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.