Abstract Algebra exercise

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

A fast way to solve this one would be to notice that for every integer $n$ where $n>2$, $n$ is coprime with $n-1$ and $1$. $1^2 = 1\mod n$ for any positive integer $n$ and $(n-1)^2\mod n = n^2-2n+1\mod n = 1\mod n$ for any positive integer $n$. Therefore, for every $n>2$ two solutions exist for $x^2=1$ given multiplication mod $n$.