Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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$


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

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|cite|improve this answer
+1 I was just about to add my answer, but noticed yours was identical. – robjohn Nov 24 '12 at 0:38

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

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

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

Your Answer


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.