En $\Bbb Z/p\Bbb Z=F$ tienes el pequeño teorema de Fermat que dice que
$$x^p-x=x(x-1)\ldots (x-(p-1)).$$
Esto significa que debe haber $1\le i\le p-1$ tal que $i^2\equiv -1\mod p$ desde $F[x]$ es un UFD. Pero entonces sabemos de los cuadrados basados en el símbolo de Legendre para que $p\equiv 1\mod 4$ si $(-1)^{(p-1)/2}\equiv 1\mod p$ es decir, existe un $i$ si $p\equiv 1\mod 4$ .
Adenda basada en los comentarios: La razón por la que el UFD es tan esencial es porque tener un polinomio que divide al otro significa que debe ser el producto de un subconjunto de componentes irreducibles del mayor. Como $x^{p-1}-1=(x-1)(x-2)\ldots (x-(p-1))$ si $(x^2+1)|(x^{p-1}-1)$ debe ser que es el producto de dos de los factores lineales de la RHS, pero entonces como $(x-a)(x-b)=x^2+1$ tenemos $a=-b$ y $a^2=-1$ .
Como alternativa, ya que $|F^\times|=p-1$ es cíclico, hay un elemento de orden $4$ si $p\equiv 1\mod 4$ que es un poco más conveniente si se conoce esa parte del álgebra.