0
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Aravind
    May 20 '20 at 7:30
  • $\begingroup$ By Lagrange it is trivial to compute square-roots in groups of odd order. $\endgroup$ May 21 '20 at 2:03
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

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

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

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – Rodrigo
    May 20 '20 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.