Are there infinite many positive integers $n$ such that $n^2+n+41$ is composite, but not divisible by $41$?

Question

Let $S=n^2+n+41$. If you try with $n=1, 2, 3, \dots, 39$, $S$ is always prime. But if $n=40, 41$, $S$ is composite. Hence, there are infinite many positive integers $n$, such that $S$ is composite.

My question is: Are there infinite many positive integer $n$, such that $S$ is composite, but not divisible by 41?

Answer 1

Sketch:

Suppose that $p$ is a factor of $n^2+n+41$ for some $n$. Then $p$ is also a factor of $(n+p)^2+(n+p)+41$ since these expressions are equal modulo $p$.

Therefore, if you can find some $p\not=41$ which divides $n^2+n+41$ for some $n$, then the question is true. For instance, use $n=1$ and $p=43$.

Answer 2

Let $f(n)=n^2+n+41$. Then $f(1)\equiv0\pmod{43}$. If $n\equiv1\pmod{43}$ then $f(n)\equiv0\pmod{43}$. There are infinitely many such $n$ not divisible by $41$.

Answer 3

Now $S(1)=43$ and $$S(1+43)=(1+43)^2+(1+43)+41=S(1)+2\times 43 +43^2+43=47\times 43$$This is divisible by $43$ by design, and also not by $41$. I am sure you can adapt this (and analysis modulo $41$) to show what you need.

Answer 4

A quick perusal of factordb.com will point you in the right direction.

Notice the 44th number is 2021, the product of 43 and 47.

Notice the 84th number is 7181, the product of 43 and 167.

Notice the 87th number is 7697, the product of 43 and 179.

Notice the 127th number is 16297, the product of 43 and 379.

Notice the 130th number is 17071... what I'm getting at, is that there are multiples of 43 all throughout this sequence, each pair fairly close to each other and separated from the next pair by roughly forty numbers.

I see the faster guns also chose 43. But there are similar patterns to be found with primes like 47, 61, 71, etc.

Answer 5

Pulling a rabbit out of a hat, note (or check) that

$$8652\equiv \begin{cases} 1\mod41\\ 163\mod653 \end{cases}$$

and

$$163^2+163+41=163\cdot164+41=163\cdot4\cdot41+41=653\cdot41\equiv0\mod653$$

so if we let $n=(41\cdot653)k+8652=26773k+8652$, then for any $k$ we have

$$S=n^2+n+41\equiv\begin{cases}1+1+0\not\equiv0\mod41\\ 163^2+163+41\equiv0\mod653 \end{cases}$$

so all these values of $S$ are composite, since they're divisible by (and strictly greater than) $653$, but not divisible by $41$.