# 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. –  Joshua 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.

-

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

-

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$.

-