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? 

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.
