In 1772 Euler discovered the curious fact that $n^2 +n+41$ is prime when $n$ is any of $0,1,2, \cdots, 39$. Show that there exist $40$ consecutive integer values of $n$ for which this polynomial is not prime.
Problem
Source:
Tags: Euler, algebra, polynomial, modular arithmetic
25.05.2007 03:24
Let $p_{1},p_{2},\dots,p_{40}$ be distinct odd primes such that -163 is a square modulo every $p_{i}.$ Our goal is to find such $m$ that $(m+i)^{2}+(m+i)+41$ is divisible by $p_{i}$ for every $i=1,2,\dots,40.$ We have \[4((m+i)^{2}+(m+i)+41)\equiv (2(m+i)+1)^{2}+163\pmod{p_{i}}\] Since -163 is a square modulo every $p_{i}$ and $p_{i}$ is odd, the congruence $(2(m+i)+1)^{2}\equiv-163\pmod{p_{i}}$ have a solution $m\equiv a_{i}\pmod{p_{i}}.$ Using CRT, we can combine these solutions into \[m\equiv m_{0}\pmod{\prod_{i=1}^{40}p_{i}}.\] Taking large enough $m$ satisfying this congruence completes the proof.
31.08.2009 01:37
we'll solve this in another way by using the fact mentioned: Let $ p_0,p_1,...,p_{39}$ be the primes that we get when we put $ 0,1,...,39$ in the polynomial $ f(n) = n^2 + n + 41$,respectively(I mean that $ p_0 = 41,...,p_{39} = 1601$).By using CRT we can find an integer $ k$ that satisfies these congruences: $ k \equiv - (2j + 1) \mod{p_{j}},0\leq{j}\leq39$. then we'll have $ k(k + 2j + 1) \equiv 0 \mod{p_{j}}$ but it's known that $ j^2 + j + 41 = p_{j}$,or $ j^2 + j + 41 \equiv 0 \mod{p_{j}}$ by adding up these two congruences we get $ (k + j)^2 + (k + j) + 41 \equiv 0 \mod{p_{j}}$.It means that when we put the numbers $ k,k + 1,...,k + 39$ in $ f(n)$ we get composite numbers.DONE.