Showing that $x^2+1\equiv 0 \mod 11$ doesn't have any solutions.

Question

I'd like to solve this questions without using Fermat's theorem and such. I'm stuck, since $x^2+1$ can't be factored and couldn't see how to proceed after converting $x^2 + 1 \equiv 0 \mod 11$ to $x^2 + 1 = 11k$.

Answer 1

In $\pmod{11}$ there is $11$ possibility for $x$ to be the root of $x^2+1=0$ namely $$\{0,\pm1,\pm2,\pm3,\pm4,\pm5\}$$ Substitute them in $x^2+1$ and you will see none of them satisfy the equation.

In fact for any prime $p$ with $p\equiv 3\pmod{4}$, the equation $x^2+1$ has no solution.

Answer 2

$\mathbb Z _{11}$ is relatively small and this is a simple polynomial. You can just check if it doesn't have a root by going over all members of the field and checking if they give $0$ with the polynomial.

Answer 3

Perhaps this is not what you might be looking for as a solution but it could be another way to solve this problem with some background in algebra.

Suppose there is a solution $x=a$ to this congruence. Then $a^2 \equiv -1 \implies a^4 \equiv 1 \pmod{11}$. This would mean the order of $a$ in the group $\mathbb{Z}_{11}^{\times}$ is $4$ but $4$ does not divide $10$ (the order of the group). Thus no such $a$ can exist.

Note this proof will work for any prime $p \equiv 3 \pmod{4}$ because $4$ does not divide the order ($p-1=4k+2$) of the multiplicative group $\mathbb{Z}_p^{\times}$.