Prove that elements of x^i 0<i<n-1 are distinct

  • #1
1,456
44

Main Question or Discussion Point

Here is the statement: If x is an element of finite order ##n## in ##G##, prove that the elements ##1,x,x^2, \dots , x^{n-1}## are all distinct.

So I started by reinterpreting the question into something more tangible. Is it true that this problem is equivalent to the following? Suppose that ##|x| = n## and that ##0 \le k,m \le n-1##. Prove that ##x^k = x^m ## if and only if ##k = m##.
 

Answers and Replies

  • #2
12,696
9,242
Yes, this is the same. You want to prove:
If ##\operatorname{ord}(x)=n ## then ##x^i \neq x^j##.
and substituted this by:
If ##\operatorname{ord}(x)=n ## then ##(x^i = x^j \Leftrightarrow i=j)##
which is the same. As ##"\Leftarrow"## is trivial, the second statement reduces to:
If ##\operatorname{ord}(x)=n ## then ##(x^i = x^j \Rightarrow i=j)##
which is the same as the first statement.

You can either prove the last statement, or assume ##x^i=x^j## for ##i \neq j## and deduce a contradiction to the minimality of ##n##.
 
  • #3
1,456
44
Yes, this is the same. You want to prove:
If ##\operatorname{ord}(x)=n ## then ##x^i \neq x^j##.
and substituted this by:
If ##\operatorname{ord}(x)=n ## then ##(x^i = x^j \Leftrightarrow i=j)##
which is the same. As ##"\Leftarrow"## is trivial, the second statement reduces to:
If ##\operatorname{ord}(x)=n ## then ##(x^i = x^j \Rightarrow i=j)##
which is the same as the first statement.

You can either prove the last statement, or assume ##x^i=x^j## for ##i \neq j## and deduce a contradiction to the minimality of ##n##.
So suppose that ##1 \le i,j < n## and that ##x^i = x^j##. Then ##x^{i-j}=1##. So ##n~ |~ (i-j)## which means that ##i \equiv j \pmod n##. But since ##1 \le i,j < n## we have that ##i=j##. Does this work?

My only problem is the statement that ##i \equiv j \pmod n## and ##1 \le i,j < n## implies ##i=j##. This implication seems kind of obvious to me, but would there be a more formal way of doing it? I haven't taken much number theory so I'm not sure.
 
  • #4
12,696
9,242
So suppose that ##1 \le i,j < n## and that ##x^i = x^j##. Then ##x^{i-j}=1##. So ##n~ |~ (i-j)## which means that ##i \equiv j \pmod n##. But since ##1 \le i,j < n## we have that ##i=j##. Does this work?

My only problem is the statement that ##i \equiv j \pmod n## and ##1 \le i,j < n## implies ##i=j##. This implication seems kind of obvious to me, but would there be a more formal way of doing it? I haven't taken much number theory so I'm not sure.
No, that's fine. You could do it per pedes (by foot) if you like: Assume ## i > j## then ##0 \neq i-j = qn \geq n ~\Longrightarrow ~i \geq j+n \geq 0+n = n## contradicting ##i<n##. However, this isn't necessary. Such situations are what calculations with modulo are made for.
 

Related Threads on Prove that elements of x^i 0<i<n-1 are distinct

Replies
2
Views
2K
Replies
7
Views
4K
  • Last Post
Replies
3
Views
2K
Replies
3
Views
2K
Top