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?

Solution 1:

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.

Solution 2:

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>0$. Then either $a^2+ab>0$, in which case we have $$pq\leq m<41^2\leq (a^2+ab+41b^2)(c^2+cd+41d^2)=pq$$ or $a<-b$, in which case we have $$41\leq a^2+40b^2\leq a^2+ab+41b^2=p$$ as neither $a$ nor $b$ can be zero.

Solution 3:

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\,$ have $\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 mentioning 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

Solution 4:

Below is problem $\rm 6\ (B3)$ from IMO $1987$ and its solution (from AoPS, or Scholes)

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