Abstract Algebra question regarding coprimes

[srfriggen]

Homework Statement

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

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

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.

 

[jmjlt88]

Remember, our group operation is multiplication mod n. Thus, 2²=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. :)

 

[srfriggen]

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

 

[micromass]

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

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?

 

[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?

 

[micromass]

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.

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.

 

[srfriggen]

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.

ok, I see the pattern now...

For n=4, two solutions to x²=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) ?

 

[micromass]

ok, I see the pattern now...

For n=4, two solutions to x²=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) ?

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 x²=1.

 

[srfriggen]

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 x²=1.

ok, so proving for 1 is trivial:

1²=1.

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

(n-1)²=1, (1)

n²-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" n²-2n, then we essentially have 0+1=1.

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

Any of this getting closer?

 

[Dick]

ok, so proving for 1 is trivial:

1²=1.

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

(n-1)²=1, (1)

n²-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" n²-2n, then we essentially have 0+1=1.

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

Any of this getting closer?

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?

 

[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?

 

[Dick]

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?

Sure. You've got it.

 

[srfriggen]

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