Show that the prime must be $13$ if $p\mid n^2+3$ and $p\mid (n+1)^2+3$ Let $p$ be a prime for which it exists a $n\in \mathbb{Z}$ with $p\mid n^2+3$ and $p\mid (n+1)^2+3$. I want to show that it must hold that $p=13$ and that there are infinitely many integers $n$ so that the above relations hold. 
$$$$ 
We have that $p\mid n^2+3$ and $p\mid (n+1)^2+3 \Rightarrow p\mid n^2+2n+1+3$, so we get $p\mid (n^2+2n+1+3)-(n^2+3) \Rightarrow p\mid 2n+1$, right?  
How could we continue? 
 A: Since $p \mid 2n+1$ we have $p\mid(2n+1)^2=4n^2+4n+1$.
We also have $p\mid2(n^2+3)+2((n+1)^2+3)=4n^2+4n+14$. Thus we have $p\mid13$ and $p=13$.
Also, any $n=13k+6, k\in \mathbb{Z}$ satisfies the condition.
A: Keep using all the expressions you know that $p$ divides the same way you have to make more and simpler numbers you know that $p$ divides until you end up somewhere.
Next is that $p$ divides $n(2n+1) - 2(n^2 + 3) = n-6$. Finally, $p$ must divide $2n+1 - 2(n-6) = 13$.
Then it remains to show that there are infinitely many $n$ that actually make $13$ divide both $n^2 + 3$ and $(n+1)^2 + 3$. First, find some $n<13$ which works. We find $n = 6$, since $3\cdot 13 = 6^2 + 3$ and $4\cdot 13 = 7^2 + 3$. Then note that if $n$ works, so does $n+13$:
$$
(n+13)^2 + 3 = n^2 + 26n + 169 + 3 = 13(2n + 13) + n^2 + 3
$$
and
$$
(n+13 + 1)^2 + 3 = n^2 + 26n+2n + 169 + 26 + 1 + 3\\
= 13(2n + 13 + 2) + n^2 + 2n + 1 + 3 = 13(2n + 13 + 2) + (n+1)^2 + 3
$$
PS: Using modular arithmetic, this final $n+13$-statement is trivial. Modular arithmetic also helps speed up the search for the initial $n = 6$: We want $n^2\equiv (n+1)^2$ ($\equiv -3$, but that's irrelevant here). This becomes $0\equiv 2n+1$, which immediately tells us that $n \equiv 6$ is the answer.
A: We have $p\mid n^2+3$ and $p\mid (n+1)^2+3$. So in particular $p$ divides the difference $2n{+}1$ (and $p$ is odd), as you say.
This gives us $2n\equiv p{-}1$ and thus $n \equiv 2^{-1}(p-1) \bmod p$.
Then working all $ \bmod p$
$\begin{align}
n^2 &\equiv (2^{-1}(p-1))^2 \\
&\equiv 4^{-1}(p^2-2p+1) \\
&\equiv 4^{-1} \\
\text{ and since }\quad n^2+3&\equiv 0 \\
4^{-1}&\equiv -3 \\
1&\equiv -12 \\
13&\equiv 0 \\
\end{align}$
This gives $p \mid 13 $ and thus $p=13$ is the only answer.
