Problem 3

Since $p\mid x^2+1$, also $p\mid 4(x^2+1)$. Substituting $x=\frac{p+1}2+t$ gives $4x^2+4=(p+1+2t)^2+4$, and since $p+1+2t\equiv1+2t\pmod p$, we get $4(x^2+1)\equiv(2t+1)^2+4\pmod p$. This congruence will let us bound $t$ from below.