Abstract Algebra question regarding coprimes

  • Thread starter srfriggen
  • Start date
  • #1
301
4

Homework Statement



For any integer n>2, show that there are at least two elements in U(n) that satisfy x2=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.
 

Answers and Replies

  • #2
96
0
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
301
4
I see, thanks!
Would induction be the best way to proceed for a complete proof?
 
  • #4
22,089
3,297
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 [itex]x^2=1[/itex]. Do you notice something?
 
  • #5
301
4
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
22,089
3,297
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.
 
  • #7
301
4
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 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
22,089
3,297
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) ?

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

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
Dick
Science Advisor
Homework Helper
26,260
619
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?

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
301
4
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
Dick
Science Advisor
Homework Helper
26,260
619
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.
 
  • #13
301
4
Great! Thanks everyone for your help and patience, Much better understanding of these concepts now!
 

Related Threads on Abstract Algebra question regarding coprimes

  • Last Post
Replies
5
Views
5K
  • Last Post
Replies
7
Views
5K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
12
Views
2K
  • Last Post
Replies
0
Views
961
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
1
Views
2K
Top