Confusion about order of elements

Question

Suppose, for cyclic group $\mathbb Z_n$, that $x$ is the generator. Then if $x$ and $x^a$ have the same order, then $\gcd(a, n) = 1$. I do not understand how $x$ and $x^a$ having the same order implies $\gcd(a, n) = 1$. Please help

Answer 1

If $a$ and $n$ had a nontrivial common divisor, say $d$, then we could take $x^a$ to the power of $n/d$ and get the identity element, so $x^a$ would have order at most $n/d$ which is less than $n$.

Answer 2

Ok lets say that $gcd(a,n)=b$ and $b>1$. Then $b|a$ and $b|n$. We also see that $(n/b)*a = kn$ for some integer $k$. But that implies $(x^a)^{n/b} = x^{kn}=1$ so $x^a$ has order $\leq n/b$.

Answer 3

$\ \color{#c00}{D\mid A,N} \,\Rightarrow\, (X^{\large A})^{\Large \color{#c00}{\frac{N}D}} = (X^{\large N})^{\Large \color{#c00}{\frac{A}D}} = 1^{\Large \frac{A}D} = 1,\ $ so $\,X^{\large A}\,$ has order $\,\le { \dfrac{N}D}\,\ {\large[}< N\ $ if $\ D>1\,{\large]}$

Remark $\ $ Generally $\ {\rm ord}\,X = N\,\Rightarrow\, {\rm ord}(X^{\large A}) = N/\gcd(N,A).\ $ See here for proofs.

Answer 4

Consider the list of elements $$x^a,\ x^{2a},\ \ldots,\ x^{(n-1)a}$$ None of these is the identity since the order of $x^a$ is $n$. Also they are all distinct, for if $x^{ia}=x^{ja}$ for some $1\le i\le j\le n-1$ then $x^{(j-i)a}=e$ $\implies$ $i=j$. Hence all these elements together with the identity $e$ form the whole group, and so one of them must be the (non-identity) element $x$, i.e. $\exists\,r$ such that $$x^{ra}\ =\ x$$ Hence $x^{ra-1}\ =\ e$, i.e. $n$ (the order of $x$) divides $ra-1$. Hence there exists $s$ such that $$ra+sn\ =\ 1$$ that is to say, $\gcd(a,n)=1$.

Answer 5

Intuitively, this is because if gcd(a,n) = 1, then $(a)(n) = j$ where $j$ is the lowest common multiple between them. If you investigate the order, you know that generally, $$x^a(x^a) = x^n(x^{2a-n}) = x^{2a-n}$$ (Note that 2 is assumed to be the smallest element such that $2a - n > 0$. You need to successively traverse the mod cycles of $a$ and $n$, until you reach that $$\underbrace{x^ax^ax^ax^ax^ax^ax^a....}_{\text{i times}} =x^{ia-n}$$ Such that $ia - n \equiv 0 \mod n$, And by definition of gcd, $i = n$.