I have found by a numerical experiment that first such primes are: $2,5,13,17,29,37,41$. But I cannot work out the general formula for it.
Please share any your ideas on the subject.
Find all prime $p$ such that $x^2=-1$ has a solution in $\mathbb{Z}/p\mathbb{Z}$
-
0@Joel: i mean integers modulo $p$. – 2011-06-28
4 Answers
If you know a little group theory it's not too hard. It holds for $p = 2$ so assume $p > 2$. Under multiplication ${\mathbb Z}_p$ is a cyclic group of order $p - 1$. To say an $x$ in ${\mathbb Z}_p$ satisfies $x^2 = -1$ is the same as saying that $x$ is an element of order $4$ in this group. To see why, first note that clearly such an $x$ is of order $4$; $x \neq 1$ and $x^2 = - 1 \neq 1$, while $x^4 = 1$. For the converse, if an element $y$ is of order $4$ then $y^2$ is of order $2$. So $y^4 - 1 = (y^2 - 1)(y^2 + 1) = 0$ in ${\mathbb Z}_p$. Since $y^2$ is not $1$ it has to be $-1$.
So the question is when does the cyclic group ${\mathbb Z}_p$ have an element of order 4. The orders of the elements of a cyclic group are exactly the divisors of the order. So this happens when $4$ divides $p - 1$ or equivalently when $p = 1 \pmod 4$.
-
0And the fact that the group is cyclic implies that there is an element of order $4$, if $p = 1 \mod 4$. – 2011-06-29
As the ideal $(p)$ is maximal in $\mathbb{Z}.$ The ring $\mathbb{Z}/pZ$ is a field. It follows that the nonzero elements form a group (the group of units $(\mathbb{Z}/p\mathbb{Z})^{\times})$ and this group is cyclic. Note $-1\in(\mathbb{Z}/p\mathbb{Z})^{\times}$ and for $p>2$ the order of $-1$ in this group is 2. As cyclic groups have one and only one subgroup of order $n$ for each positive integer $n$ dividing the order of the group, we observe for $p>2,$ the element $-1$ has a square root if and only if $(\mathbb{Z}/p\mathbb{Z})^{\times}$ contains a subgroup of order $4$ which occurs if and only if $4$ divides $|(\mathbb{Z}/p\mathbb{Z})^{\times}| = p-1,$ i.e. if and only if $p\equiv 1\mod 4.$
Examining case where $p =2,$ trivially reveals that $-1$ has square root.
-
0there is a simiral answer from Zarrax. But your answer deals with commutative algebra in somewhat higher level than Zarrax's answer. Thank you for providing higher level of abstraction on the matter. – 2011-06-28
The following argument depends on knowing (or separately proving) Wilson's Theorem.
Theorem Let $p$ be prime. Then $(p-1)! \equiv -1 \pmod{p}$.
Now we use Wilson's Theorem to prove the result. For the sake of concreteness, I will use $p=17$, but the same idea exactly works for all primes congruent to $1$ modulo $4$. All congruences will be modulo $17$, so $17$ will mostly not be mentioned explicitly.
Note that $16!= (1)(2)(3)(4)(5)(6)(7)(8)(16)(15)(14)(13)(12)(11)(10)(9).$ (Didn't really do anything.)
Note that $16\equiv -1$, $15\equiv -2$, $14\equiv -3$, and so on until $9 \equiv -8$. It follows that $(15)(14)(13)(12)(11)(10)(9)\equiv (-1)(-2)(-3)(-4)(-5)(-6)(-7)(-8).$ But the right-hand side is congruent to $(-1)^8(1)(2)(3)(4)(5)(6)(7)(8)$, and of course $(-1)^8=1$.
It follows that $16! \equiv (8!)^2 \pmod{17}$. But by Wilson's Theorem, $16!\equiv -1 \pmod{17}$, and therefore $(8!)^2 \equiv -1 \pmod{17}.$
We have found an explicit expression for an $x$ such that $x^2\equiv - \pmod{17}$.
If $p \equiv 3 \pmod{4}$, the argument breaks down, because we end up with an odd number of minus signs. (Anyway, the result does not hold when $p\equiv 3\pmod 4$.)
In general, if $p\equiv 1 \pmod 4$, and $q=(p-1)/2$, then $(q!)^2 \equiv -1 \pmod{p}.$
Other primes: It remains to show that the congruence is not solvable if $p \equiv 3\pmod{4}$. So suppose to the contrary that $b^2\equiv -1\pmod{p}$. Look at the numbers $b, 2b, 3b, \dots, (p-1)b$. It is easy to verify they are pairwise incongruent modulo $p$, so their product is congruent to $(p-1)!$ modulo $p$. Thus $b^{p-1}(p-1)! \equiv (p-1)! \pmod p,$ giving $b^{p-1}\equiv 1 \pmod p$. Let $q=(p-1)/2$. Then $b^{p-1} \equiv (-1)^q \pmod p$. But if $p \equiv 3 \pmod 4$, then $q$ is odd, and we obtain the absurd $-1 \equiv 1 \pmod{p}$.
-
0thank you for useful reply. Wilson's theorem is used further in my exercise list. – 2011-06-29
In a number theory course, you would probably come to the Legendre symbol after a while... http://en.wikipedia.org/wiki/Legendre_symbol
-
0it's interesting. Thank you for pointing that. – 2011-06-28