# Prove that $n^2+n+41$ is prime for $n<40$

Here's a problem that showed up on an exam I took, I'm interested in seeing if there are other ways to approach it.

Let $n\in\{0,1,...,39\}$. Prove that $n^2+n+41$ is prime.

I shall provide my own solution, though I am curious does anyone know how to do this without using PIDs?

-
For more information see e.g. this question. Not sure if I want to call this a duplicate though? – Jyrki Lahtonen Mar 10 '14 at 10:18
Yeah, I read that, but it seemed to me to be a meta question about the existence of such functions that produce long strings of primes, and the comments deal with more general questions. – Stella Biderman Mar 10 '14 at 10:20
The Maple code $$for\, n \,to\, 40 \,do\, if \,not\,isprime(n^2+n+41) \,then \,print(n)\, end\, if\, end\, do$$ outputs $40.$ – user64494 Mar 10 '14 at 10:25
Probably relevant: Is the notorious $n^2+n+41$ prime generator the last of its type?. – MJD Mar 10 '14 at 13:41

Since $4(n^2+n+41)=(2n+1)^2+163$, one way would be to methodically show that $-163$ is a quadratic non-residue mod all (odd) primes less than $41$.

Added later: The OP has asked for further details, so here goes.

If $p\mid n^2+n+41$, then $(2n+1)^2+163\equiv0$ mod $p$, which means that $-163$ is a square mod $p$. Now the values of $n^2+n+41$ for $n\lt40$ are all less than $40^2+40+41=1681$, so if any of them were composite, it would have to have a prime factor less than $\sqrt{1681}=41$. That prime factor would have to be odd, since it's clear that $n^2+n+41$ is always odd. This would require $-163$ to be a quadratic residue for some odd prime less than $41$. So it suffices to compute the Legendre symbol $({-163\over p})$ for $p=3,5,7,11,13,17,19,23,29,31$, and $37$, and show that it's $-1$ in each case.

This is a bit tedious, but less so than directly checking the primality of the $39$ numbers $(1^1+1+41), (2^2+2+41),\ldots,(39^2+39+41)$. For example,

$$\left({-163\over17}\right)=\left({7\over17}\right)=\left({17\over7}\right)=\left({3\over7}\right)=-\left({7\over3}\right)=-\left({1\over3}\right)=-1$$

where the string of equalities here makes use (twice) of the Law of Quadratic Reciprocity.

-
I can't believe my prof. marked this exercise with a 1-star (out of 3) difficulty. :( – user1511417 Nov 9 '15 at 19:46

We will prove this using the PID $R:=\mathbb{Z}[\omega]$, where $\omega=\frac{1+i\sqrt{163}}{2}$, with the norm $N(a+b\omega)=|a+b\omega|^2=a^2+ab+41b^2$.

Lemma 1: If $p$ is prime in $\mathbb{Z}$ such that $\exists n\in\mathbb{Z}$ such that $p|n^2+n+41$, then $p$ is reducible in $R$.

Proof: Let $p|n^2+n+41$ and assume $p$ is irreducible. Then $p$ is also prime, since $R$ is known to be a PID. Thus $p|(n+\omega)(n+\overline{\omega})\Rightarrow p|n+\omega$ or $p|n+\overline{\omega}$. The first is nonsense since multiples of $p$ are of the form $ap+bp\omega$ so this would force $p$ to be a unit in $\mathbb{Z}$. But the second is also impossible since $n+\overline{\omega}=n+1-\omega$.

Lemma 2: If $p$ is prime in $\mathbb{Z}$, then $p$ is reducible in $R$ iff $\exists a,b\in\mathbb{Z}$ such that $p=a^2+ab+41b^2$

Proof: Let $p$ be reducible. Then $p=\alpha\beta\Rightarrow p^2=N(p)=N(\alpha\beta)=N(\alpha) N(\beta)\Rightarrow p=N\alpha=N\beta$. For the other direction, let $p=a^2+ab+41b^2$ and assume it is irreducible, so $p=(a+b\omega)(a+b\overline{\omega})$. Since $p$ is irreducible, one of these has norm $1$. But these clearly have the same norm, so then $N(p)=1$ which is impossible.

Proof of the theorem: Let $m=n^2+n+41$ and assume $m$ is not prime. Then there exists primes $p,q\in\mathbb{N}$ such that $\frac{m}{pq}\in\mathbb{N}$. Thus by Lemma 1, $p,q$ are reducible in $\mathbb{Z}[\omega]$ and so by Lemma 2 they are of the form $p=a^2+ab+41b^2$ and $q=c^2+cd+41d^2$. Notice that $b^2d^2>0$ since if $b=0$ then $p=a^2\Rightarrow p$ is not prime. Likewise for $d$. WLOG $a>b$ so that $a^2+ab>0$, as otherwise replace $a,b$ with $-a,-b$ and likewise for $c,d$.Thus we have $$pq\leq m<41^2\leq (a^2+ab+41b^2)(c^2+cd+41d^2)=pq$$

-
The WLOG at the end doesn't work, because replacing $a,b$ with $-a,-b$ doesn't affect the value of $a^2+ab$. – m_t_ Mar 30 at 19:48
It is true that WLOG $a>0$ for the reason you say. Then either $a^2+ab>0$ and you're done as before, or $a<-b$ in which case $p=a^2+ab+41b^2 \geq a^2 + 40b^2\geq 41$ as neither $a$ nor $b$ can be zero. – m_t_ Mar 30 at 20:07

Theorem $\$ The polynomial $\rm\ f(x)\ =\ (x\!-\!\alpha)\,(x\!-\!\alpha')\ =\ x^2 + x + k\$ assumes only prime values for $\rm\ 0\ \le\ x\ \le\ k-2 \ \iff\ \mathbb Z[\alpha]\$ is a PID.

Hint $\ (\Rightarrow)\$ Show all primes $\rm\ p \le \sqrt{n},\; n = 1-4k\$ satisfy $\rm\ (n/p) = -1\$ so no primes split/ramify.

For proofs, see e.g. Cohn, Advanced Number Theory, pp. 155-156, or Ribenboim, My numbers, my friends, 5.7 p.108. Note: both proofs employ the bound $\rm\ p < \sqrt{n}\$ without explicitly mentiioning that this is a consequence of the Minkowski bound - presumably assuming that is obvious to the reader based upon earlier results. Thus you'll need to read the prior sections on the Minkowski bound. Compare Stewart and Tall, Algebraic number theory and FLT, 3ed, Theorem 10.4 p.176 where the use of the Minkowski bound is mentioned explicitly.

Alternatively see the self-contained paper [1] which proceeds a bit more simply, employing Dirichlet approximation to obtain a generalization of the Euclidean algorithm (the Dedekind-Rabinowitsch-Hasse criterion for a PID). If memory serves correct, this is close to the approach originally employed by Rabinowitsch when he first published this theorem in 1913.

[1] Daniel Fendel, Prime-Producing Polynomials and Principal Ideal Domains,
Mathematics Magazine, Vol. 58, 4, 1985, 204-210

-

Theorem. If $k^2+k+n$ is prime for all integers $k$ such that $0\le k\le \sqrt\frac{n}{3}$, then $k^2+k+n$ is prime for all integers $0\le k\le n-2$.

Proof. First observe that if $m$ is relatively prime to $b+1$, $b+2$, $\cdots$, $2b$, then $m$ is relatively prime to any number less than $2b$. Indeed if $c\leq b$, then we can choose some $i$ to make $2^ic$ lies in range $b+1,b+2,\cdots,2b$, so $2^ic$ is relatively prime to $m$. Hence $c$ is also a prime. If we also have $(2b+1)^2>m$, then we can conclude that $m$ is a prime, otherwise there must be a factor of $m$ less than $\sqrt{m}$.

Let $n=3r^2+h$ where $0\leq h<6r+3$, so $r$ is the greatest integer less than or equal to $\sqrt{n/3}$.(to see this, just let $r=\lfloor\sqrt{n/3}\rfloor$, then we can write $n=3(r+\epsilon)^2(0\leq\epsilon< 1)$, so $h=6r\epsilon+3\epsilon^2\leq 6r+3$).

Assume that $n+k(k+1)$ is prime for $k=1,2,3\cdots,r$. We show that $N=n+(r+s)(r+s+1)$ is prime for $s=0,1,2,\cdots,n-r-2$. By our observation above, it is sufficient to show that $(2s+2r+t)^2>N$ and $N$ is relatively prime to all of $r+s+1,r+s+2,\cdots,2r+2s$. We have $(2r+2s+1)^2=4r^2+4s^2+8rs+4r+4s+1$. Since $s,r\ge1$, we have $4s+1>s+2$, $4s^2>s^2$ and $6rs>3r$. Hence $[(2s+2r+1)^2>4r^2+2rs+s^2+7r+s+2=3r^2+6r+2+(r+s)(r+s+1)\ge N]$. Now if $N$ has a factor which divides $2r-i$ int the range $-2s$ to $r-s-1$, then so does $N-(i+2s+1)(2r-i)=n+(r-i-s-1)(r-i-s)$ which have the form $n+s'(s'+1)$ with $s'$ in range $0$ to $r$.

Note this is the problem B6 of IMO $1987$.

-

## protected by user26857Dec 15 '15 at 22:07

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).