Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm reading "Elementary Number Theory by Kenneth H.Rosen", and in the book, there is one problem that I couldn't understand the solution.

Problem 9 (Chapter 9.2 - 6th edition)

Show that if $p$ is a prime and $p \equiv 1 \pmod{4}$, then there is an integer $x$ such that $x^2 \equiv -1 \pmod{p}$.

Solution from Textbook
By Larange's theorem, there are at most two solutions $x^2 \equiv 1 \pmod{p}$, and we know $x \equiv \pm1$ are the two solution.
Since $p \equiv 1 \pmod{4} \implies 4 | (p - 1) = \phi(p)$ so there is an element $x$ of order $4$ modulo p.
Then $x^4 = (x^2)^2 \equiv 1 \pmod{p}$, so $x^2 \equiv \pm1 \pmod{p}$. If $x^2 \equiv 1 \pmod{p}$ then $x$ does not have order $4$. Therefore $x^2 \equiv -1 \pmod{p}$.

What I did not understand is, "If $x^2 \equiv 1 \pmod{p}$ then $x$ does not have order $4$." I really don't see how the author came up with this one? Any idea?


share|cite|improve this question
if x^2 = 1 then x has order 2. (unless x = 1 then it has order 1) – quanta Apr 1 '11 at 6:10
@quanta: Many thanks! I must be blind :(. – Chan Apr 1 '11 at 6:12
For group-theoretic views of this see – Bill Dubuque Apr 1 '11 at 7:23
@quanta Please consider converting your comment into an answer, so that this question gets removed from the unanswered tab. If you do so, it is helpful to post it to this chat room to make people aware of it (and attract some upvotes). For further reading upon the issue of too many unanswered questions, see here, here or here. – Julian Kuelshammer Jun 15 '13 at 7:58

As quanta notes above, if $x^2 = 1$ then $x$ has order at most $2$.

As an aside, that happened to be the book I first learned elementary number theory from as well, and I enjoyed it very much. I still teach from it, even.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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