Intereting Posts

What are some strong algebraic number theory PhD programs?
Clarification regarding little n-discs operads
homomorphism $f: \mathbb{C}^* \rightarrow \mathbb{R}^*$ with multiplicative groups, prove that kernel of $f$ is infinite.
Volume of first cohomology of arithmetic complex
Joint moments of Brownian motion
Symbols for Quantifiers Other Than $\forall$ and $\exists$
Show that $\frac{xy}{z} + \frac{xz}{y} + \frac{yz}{x} \geq x+y+z $ by considering homogeneity
Proving the Schwarz Inequality for Complex Numbers using Induction
Where to start learning Linear Algebra?
Proving that if one person in any group of four knows three, then someone knows everyone.
Residue at infinity (complex analysis)
Big List of Erdős' elementary proofs
How do I calculate the intersection(s) of a straight line and a circle?
Random variable independent of itself
Upper bound number of distinct prime factors

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?

- Prove that an infinite ring with finite quotient rings is an integral domain
- Prove that $\langle a^n \rangle \bigcap \langle a^k \rangle = \langle a^{lcm (n,k)} \rangle$
- Is this an equivalent statement to the Fundamental Theorem of Algebra?
- Deduction of usual Cayley-Hamilton Theorem from “Determinant Trick”
- continuous map on $\mathbb{R}$ which is the identity on $\mathbb{Q}$ is the identity map, hence Aut$(\mathbb{R}/\mathbb{Q})= 1.$
- Is $A \times B$ the same as $A \oplus B$?

- If a field $F$ is an algebraic extension of a field $K$ then $(F:K)=(F(x):K(x))$
- Prove 24 divides $u^3-u$ for all odd natural numbers $u$
- How to prove a number system is a fraction field of another?
- Why is the localization at a prime ideal a local ring?
- associative and commutative F-algebra with basis
- Algebraic structure cheat sheet anyone?
- Basic question on primitive roots
- What's the order of growth of the 'double-and-rearrange' numbers?
- Help in understanding the proof of Mersenne Prime
- Easy way to show that $\mathbb{Z}{2}]$ is the ring of integers of $\mathbb{Q}{2}]$

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.

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

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

- Simple group of order $660$ is isomorphic to a subgroup of $A_{12}$
- $C(M)=\{A\in M_n(\mathbb{C}) \mid AM=MA\}$ is a subspace of dimension at least $n$.
- Are proofs by contradiction really logical?
- No simple group of order $96$
- Pointwise convergent and total variation
- Why is the number of possible subsequences $2^n$?
- How to draw that graph?
- Proving that $\int_0^1 \frac{\log \left(\frac{1}{t}\right) \log (t+2)}{t+1} \, dt=\frac{13}{24} \zeta (3)$
- Sobolev meets Wiener
- A samurai cuts a piece of bamboo
- An example of a group, a subgroup and an element, satisfying a given condition.
- Does $n \mid 2^{2^n+1}+1$ imply $n \mid 2^{2^{2^n+1}+1}+1$?
- How to prove that $\frac{\zeta(2) }{2}+\frac{\zeta (4)}{2^3}+\frac{\zeta (6)}{2^5}+\frac{\zeta (8)}{2^7}+\cdots=1$?
- Symbol of a (non linear) differential operator
- Hausdorff Dimension Calculation