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

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$$.

• If you use Fermat's little theorem, you get the result not only for 11, but also for all primes of the form $4k+3$, so using it is the better way. – Aravind May 20 '20 at 7:30
• By Lagrange it is trivial to compute square-roots in groups of odd order. – Bill Dubuque May 21 '20 at 2:03

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.

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}$$.

• Is that Lagrange's Theorem? – Rodrigo May 20 '20 at 8:15
• @Rodrigo Yes!! that is Lagrange's theorem or a simpler version that the order of an element divides the order of the group. – Anurag A May 20 '20 at 8:16
• Thanks for pointing that out! (I'm not very familiar with the theorem, yet. But I don't think I'd spot that anyhow.) – Rodrigo May 20 '20 at 8:17
• @Rodrigo Perhaps making you future proof :-) – Anurag A May 20 '20 at 8:19
• Why a down vote? Down voting without specifying the reason doesn't serve any purpose for the OP, the person answering or the community. – Anurag A May 24 '20 at 22:10

$$\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.

• Well, yes that's obvious. But, I was looking for a way of doing it without testing all cases. Should have said that above. Thanks! – Rodrigo May 20 '20 at 8:15