Squared Plus Two Can't Be Divided By You

The prime $p$ that we seek is the one for which $-2$ is not a quadratic residue modulo $p$ .

Now since $15^{2} = 225 \equiv -2 \pmod{227}$ we know that $227$ is not the correct option. For the other three primes, we will make use of Euler's criterion with $a = -2$ .

For $p = 113$ we are looking to evaluate

$(-2)^{\frac{113 - 1}{2}} \pmod{113} \equiv (-2)^{56} \pmod{113} \equiv 2^{56} \pmod{113}$ .

Now $2^{7} = 128 \equiv 15 \pmod{113} \Longrightarrow 2^{14} \equiv 225 \pmod{113} \equiv -1 \pmod{113}$

$\Longrightarrow 2^{56} = (2^{14})^{4} \equiv (-1)^{4} \equiv 1 \pmod{113}$ .

Thus by Euler's criterion $-2$ is a quadratic residue modulo $113$ , and so this prime is not the correct option.

For $p = 131$ we are looking to evaluate $(-2)^{\frac{131 - 1}{2}} \pmod{131} \equiv (-2)^{65} \pmod{131}$ .

Now $(-2)^{8} = 256 \equiv -6 \pmod{131} \Longrightarrow (-2)^{16} \equiv 36 \pmod{131}$

$\Longrightarrow (-2)^{32} \equiv 1296 \equiv -14 \pmod{131} \Longrightarrow (-2)^{64} \equiv 196 \equiv 65 \pmod{131}$

$\Longrightarrow (-2)^{65} \equiv -2*65 \pmod{131} \equiv 1 \pmod{131}$ .

So by Euler's criterion $131$ is not the correct option. This leaves us with just $311$ , which we now need to confirm is the correct option.

We are looking to evaluate $(-2)^{\frac{311 - 1}{2}} \pmod{311} \equiv (-2)^{155} \pmod{311}$ .

Now $(-2)^{12} = 4096 \equiv 53 \pmod{311} \Longrightarrow (-2)^{24} \equiv 2809 \pmod{311} \equiv 10 \pmod{311}$

$\Longrightarrow (-2)^{96} \equiv 10000 \pmod{311} \equiv 48 \pmod{311}$

$\Longrightarrow (-2)^{144} = (-2)^{96}*(-2)^{48} \equiv 48*100 \pmod{311} \equiv 135 \pmod{311}$

$\Longrightarrow (-2)^{154} = (-2)^{144}*(-2)^{10} \equiv 135*91 \pmod{311} \equiv 156 \pmod{311}$

$\Longrightarrow (-2)^{155} = (-2)^{154}*(-2) \equiv 156*(-2) \pmod{311} \equiv -312 \pmod{311} \equiv -1 \pmod{311}$ .

By Euler's criterion we have thus confirmed that $\boxed{311}$ cannot be a divisor of $n^{2} + 2$ for any integer $n$ .