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

[Mr Davis 97]

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

 

[fresh_42]

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

 

[Mr Davis 97]

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.

 

[fresh_42]

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.