# Abstract Algebra question regarding coprimes

1. Aug 28, 2012

### srfriggen

1. The problem statement, all variables and given/known data

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

2. Relevant equations

In my book I found a definition: Define U(n) to be the set of all positive integers less than n and relatively prime to n.

3. The attempt at a solution

I think I simply just don't understand exactly what is being asked. My first instinct is to just look at an integer greater than 2, say 3. Now I think, "What are some numbers in the set U(3)?" Well, I can only think of 1 and 2, since both 1 and 2 are positive numbers and co-prime to 3. Clearly 1 is a solution, but certainly not 2. Any other number greater than 3 yields the same conclusion, i.e. 1 as the only answer.

2. Aug 28, 2012

### jmjlt88

Remember, our group operation is multiplication mod n. Thus, 22=4 mod 3 = 1. Hence, 2 is indeed a solution. As you said, the identity is clearly one solution. Create a few more examples for yourself. See what you notice. :)

3. Aug 28, 2012

### srfriggen

I see, thanks!
Would induction be the best way to proceed for a complete proof?

4. Aug 28, 2012

### micromass

Staff Emeritus
No, induction is not needed here.

Take n=2,3,4,5,6,... and each time calculate the elements x such that $x^2=1$. Do you notice something?

5. Aug 28, 2012

### srfriggen

Yes, I do notice that if I write the solutions out in rows, one under another, that the first column is all 1's, the 2nd column increases by 1, i.e. is the set {4,5,6...}, the 3rd column starts with 7 and increases by 2, i.e. {7,9,11,... } and so on.

As you move along rows of course the solutions are every 3 numbers, for 3, or every 4th Number, for 4.

So How could I use these observations to make a concise rigorous argument?

Would I be able to incorporate that 1 and n are both relatively prime to any other number in the sequence?

6. Aug 28, 2012

### micromass

Staff Emeritus
Notice that modulo 3, we have that 1=4=7. So you have just found two solutions.

When n=3, the solutions are 1 and 2.
When n=4, what are the solutions then?? Notice that 1=5=9 again.

7. Aug 28, 2012

### srfriggen

ok, I see the pattern now...

For n=4, two solutions to x2=1, are 1 and 3.

For n=5, two solutions to the equation are 1 and 4.

For n=6, two solutions to the equation are 1 and 5.

Is that enough proof to establish that the answers are always, at least, 1 and (n-1) ?

8. Aug 28, 2012

### micromass

Staff Emeritus
No, that's not enough proof. You just found the pattern! Now you need to prove that 1 and n-1 are always solutions to x2=1.

9. Aug 28, 2012

### srfriggen

ok, so proving for 1 is trivial:

12=1.

Then I plugged in (n-1) to the equation and noticed:

(n-1)2=1, (1)

n2-2n+1=1. (2)

I factored out to n(n-1)=0, but something tells me (2) is where I should be making my argument. If we "mod out" n2-2n, then we essentially have 0+1=1.

Or if we note that (n2-2n)/n = n-2, and n-2+1=1 is n-1=1.

Any of this getting closer?

10. Aug 28, 2012

### Dick

You 'noticed' what you want to prove. That's making it a little confusing. Just start with (n-1)^2=n^2-2n+1. Which terms in that expression are equal to 0 mod n?

11. Aug 28, 2012

### srfriggen

Certainly 2n mod n is equal to 0.

And n^2 mod n is equal to 0, since both 2n and n^2 are divisible by n.

So we would have (n-1)^2=0+0+1, or (n-1)^2=1, our solution?

12. Aug 28, 2012

### Dick

Sure. You've got it.

13. Aug 28, 2012

### srfriggen

Great! Thanks everyone for your help and patience, Much better understanding of these concepts now!

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook