Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Where 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 got it.

share|improve this question
1  
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

2 Answers 2

up vote 2 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|improve this answer

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

share|improve this answer

Your Answer

 
discard

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.