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 currently stuck on an exercise problem from Joseph Gallian's book, "Contemporary Abstract Algebra." The question is from Chapter $2$, Exercise $12$. It says: "For $n>2$, show that there are at least two elements in $U(n)$ that satisfy $x^2=1$"

Here $U(n)$ is the set of positive integers less than $n$ and co-prime with $n$. This set is a group under multiplication mod $n$.

I see that a good way of showing this property is by induction. So I've set up my inductive hypothesis, after a couple of base cases of course (starting at $n=3$). But I'm stuck and I can't go from the hypothesis to the inductive step.

Any help would be appreciated. Thanks.

Edit: Thanks everyone, I've got it.

share|cite|improve this question
Induction is overrated. It is overemphasized in introductory courses, although as a proof method it oftentimes has the limitation of being mechanical rather than explanatory. – Yuval Filmus Jan 21 '11 at 4:35
up vote 3 down vote accepted

Induction performs poorly on factorization because the factors of $n+1$ are not well related to the factors of $n$. A better approach is to exhibit two different solutions to $x^2=1$. If you move the $1$ over and factor the equation...

share|cite|improve this answer

Hint: How do you normally (say in real numbers) solve $x^2 =1$?

share|cite|improve this answer

For any integer $n>2$, show that there are at least two elements in $U(n)$ that satisfy $x^2=1$.

Clearly $1$ is one such element. The other is $n-1$. Every $U(n)$ contains $n-1$, since $n-1$ is always relatively prime to $n$. Furthermore

$$(n-1)^2 = n^2 -2n +1 = 1\ (\text{mod }n)$$

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.