# Abstract Algebra exercise

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.

-
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

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

-

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

-

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

-