# Show that there are infinitely many integers $n$ such that $43 \mid(n^2+n+41)$.

Show that there are infinitely many integers $$n$$ such that $$43 \mid(n^2+n+41)$$.

Assume $$f(n) = (n^2+n+41)$$. Then $$f(1)=1^2+1+41 = 43$$. So $$f(1) \equiv 0 \pmod{43}$$. If $$n \equiv 1 \pmod{43}$$ then $$f(n)=0 \pmod{43}$$.

Is this proof correct? I'm just starting to learn some number theory and I'm not as confident in this as, say, real analysis or linear algebra.

Any help is appreciated.

• This shows that there are infinitely many $n$ where $43\mid n^2+n+41$, but doesn't immediately say anything about $42$. – hmakholm left over Monica Sep 26 '18 at 4:05
• typo...fixing it. – Idle Math Guy Sep 26 '18 at 4:06
• Yes, your proof is correct. Note that for any $f(x) \in \mathbb{Z}[x]$ and $a \neq b \in \mathbb{Z}$, we have $a-b | f(a) - f(b)$, and setting $a = 43k+1, b = 1$ yields the conclusion :) – katana_0 Sep 26 '18 at 4:20
• Looks good. Also note that $n^2+n+41\equiv n^2+n-2\pmod{43}$. $n^2+n-2=(n+2)(n-1)$, so $n=43k-2$ should be a solution too. – Mike Sep 26 '18 at 5:11

Yes, it looks correct. Just for the record, this technique is covered in Hardy's "An Introduction To The Theory Of Numbers" (more details here), if $$f(x)$$ is a polynomial then: $$f(k)=m \Rightarrow m \mid f(m\cdot n + k), \forall n$$