Prove Order of $x^k = n/{\gcd(k,n)}$ by taking cases

Algebra by Michael Artin Prop 2.4.3

Proposition 2.4.3 Let $x$ be an element of finite order $n$ in a group, and let $k$ be an integer that is written as $k = nq + r$ where $q$ and $r$ are integers and $r$ is in the range $0 \leq r < n$.

• $x^k = x^r$.
• $x^k = 1$ if and only if $r = 0$.
• Let $d$ be the greatest common divisor of $k$ and $n$. The order of $x^k$ is equal to $n/d$.

The book gives no proof. I have a proof to the 3rd bullet point, and I believe my proof is different from all the proofs in the following questions (and is less elegant than all of them LOL).

• Proof for showing the order of $a^k$ is $\frac{d}{gcd(k,d)}$.

• Show that $y=x^{k}$ with $gcd(k,n)=1$ is a generator of $G$.

• How to prove $|a^k|=n/\gcd(n,k)$ whenever $|a|=n$?

• Prove that the order of the cyclic subgroup $\langle g^k\rangle $ is $n/{\operatorname{gcd}(n,k)}$

• If $g$ is the generator of a group $G$, order $n$, when is $g^k$ a generator?

• If $G$ is cyclic with order $N$ then $g^n$ has order $\frac{N}{\gcd(n,N)}$

And different from this one:

• A First Course in Group Theory Aditi Kar April 10, 2017 Thm 12

Question: Is my proof below correct, and why/why not? Please verify.

BCLC's inelegant un-intuitive low-number-theory-background proof by exhaustion:

Let the order of $x^k$ be $m$. We have 3 cases to check:

• Case 1: $m<\frac{n}{d}$ (Hope assuming $m \ge 0$ is okay!)

• Case 2: $m=\frac{n}{d}$

• Case 3: $m>\frac{n}{d}$

We must rule out Cases 1 and 3.

• Case 3: $m>\frac{n}{d}$

We can rule out Case 3, i.e. we can rule out integers greater than $\frac{n}{d}$ as orders of $x^k$ if $(x^k)^m=1$ holds for $m=\frac{n}{d}$. Thus, Case 2 will be the case if we can rule out Case 1 and if $(x^k)^m=1$ holds for $m=\frac{n}{d}$.

Now, we will show $(x^k)^m=1$ holds for $m=\frac{n}{d}$, so we will rule out Case 3 and will make Case 2 the case if we can rule out Case 1.

• Case 2:

This will be the case if $(x^k)^m=1$ holds for $m=\frac{n}{d}$ and we rule out Case 1. Let's show the former:

For $m=\frac{n}{d}$, $(x^k)^m=(x^k)^{n/d}$. Now if $\frac{k}{d}$ is an integer, then $(x^k)^{n/d}=1$. I think the converse is true as well. Anyhoo, because $d:=\gcd(k,n)$, we have that $d$ divides $k$, so there's an integer, that we'll denote $d_k$, s.t. $d_kd=k$. Thus, $\frac{k}{d}=d_k$,is an integer. Therefore, $(x^k)^m=1$ for $m=\frac{n}{d}$, and hence, Case 3 is ruled out.

Now let's rule out Case 1 to make Case 2 the case.

• Case 1: $m<\frac{n}{d}$

Now, I'll use $x^k=x^r$, though we might be able to do without (I probably should've done that earlier, otherwise $d_k$ could be negative, but I think proof would still be the same).

Thus, $$x^{rm}=x^{km}=(x^{k})^m.$$

Now suppose on the contrary that $x^{rm}=1$. Then $rm$ is a nonnegative multiple of $n$: We have 3 subcases, all of which we must rule out.

• Case 1.1: $rm < n$

The only nonnegative multiple of $n$ less than $n$ is $rm=0$. Hence, $m=0$ or $r=0$. $m$ cannot be $0$ because elements of groups (in this case $x^r$) cannot have order $0$. However, $r=0$ implies that $$ d = \gcd(k,n) = \gcd(nq+r,n) = \gcd(nq,n) \stackrel{(*)}{=} n. $$ Recall that Case 1 assumes $m<\frac{n}{d}$, so we have $m < \frac{n}{d} = \frac{n}{n} = 1$, which implies that $m = 0$. But, $m$ cannot be $0$, as we just established. ↯

• Case 1.2: $rm = n$ and

We have that $$ d = \gcd(k,n) = \gcd(nq+r,n) = \gcd\left( nq+\frac{m}{n}, n \right) = \gcd\left( n \left( q+\frac{1}{m} \right), n \right). $$

Observe that we cannot have that $q+\frac{1}{m}$ is an integer while $n(q+\frac{1}{m})$ is not an integer.

• If $q+\frac{1}{m}$ is an integer, then $d=n$. As in Case 1.1, this implies that $m = 0$. ↯

• If $n(q+\frac{1}{m})$ is not an integer, then $d$ does not exist. ↯

• If $q+\frac{1}{m}$ is not an integer but $n(q+\frac{1}{m})$ is an integer, then write $q+\frac{1}{m} = \frac {\rho_u}{\rho_d}$, a rational number in canonical form, i.e. $\rho_u$ and $\rho_d$ are coprime positive integers, i.e. $\gcd(\rho_u,\rho_d)=1$. Then since we must have a cancellation to arrive at an integer and $\rho_d$ has no reason to cancel out with $\rho_u$, it must be that some of the the factors in $\rho_d$ cancel out with some of the factors in $n$. The thing is we're not going to have an integer if only some factors in $\rho_d$ cancel. We need all of $\rho_d$'s factors to cancel out. (The preceding folklore is Euclid's lemma (****).) Thus, $n$ is a multiple of $\rho_d$. Let's write $n=\rho_n\rho_d$. Hence,

$$ d = \gcd\left( n \left( q+\frac{1}{m} \right), n \right) = \gcd\left( n \left( \frac{\rho_u}{\rho_d} \right), n \right) = \gcd\left( \rho_n\rho_d \left( \frac{\rho_u}{\rho_d} \right), \rho_n\rho_d \right) = \gcd\left( \rho_n \left( \frac{\rho_u}{1} \right), \rho_n\rho_d \right) = \rho_n \gcd\left( \left( \frac{\rho_u}{1} \right), \rho_d \right) = \rho_n \gcd\left( \left( \rho_u \right), \rho_d \right) = \rho_n (1) = \rho_n $$

Observe that $\gcd(qm+1,m)=1$ by (**). Therefore, $qm+1=\rho_u$ and $m=\rho_d$ because canonical forms of rational numbers are unique. Thus, $n=\rho_n\rho_d=\rho_n m$. But $n=rm$ and $d=\rho_n$. Hence, $d=\rho_n=r$.

Finally, observe that $n < rm < \frac{nr}{d}$ implies $d<r$.

Therefore, we have that $d<r$ and $d=r$. ↯

• Case 1.3: $rm > n$

Firstly, $rm$ is a nonnegative multiple of $n$ that is not $n$ or $0$ because $rm > n$. So, we have a positive integer $l$ s.t. $rm=ln$. Thus, \begin{align*} d &= \gcd(k,n) = \gcd(nq+r,n) = \gcd\left( \frac{rmq}{l}+r, \frac{rm}{l} \right) \\ &= \gcd\left( (r)\left( \frac{m}{l} q + 1 \right), (r)\left( \frac{m}{l} \right) \right) = r \gcd\left( \frac{m}{l} q + 1, \frac{m}{l} \right), \end{align*} where the last equality holds if and only if $\frac{m}{l}$ is an integer.

If $\frac{m}{l}$ is not an integer:

RM/L must be an integer so if M/L is not an integer then by Euclid's lemma, we must have that L divides R. Define R=SL. Then D=gcd(R,RM/L) =gcd(SL,SM)=Sgcd(L,M)=S, where the last equality holds for the same reason we're in this subcase in the first place unless M/L isn't in lowest terms, but when reduced to lowest terms M/L still isn't an integer, in which case just replace M and L with the canonical M' and L' and define R=S'L. Then D= S'.

Hence, D=S or D=S'.

Soooo NL=RM=S'LM -> N=S'M=DM but by assumption DM < N.

↯

If $\frac{m}{l}$ is an integer, then $$ d \stackrel{(**)}{=} r \gcd\left(1,\frac{m}{l}\right) = r(1) = r. $$

Again finally, as in Case 1.2, observe that $n < rm < \frac{nr}{d}$ implies $d<r$.

Therefore, we have, again, that $d<r$ and $d=r$. ↯

Since Cases 1.1, 1.3 and 1.2 have been ruled out, Case 1 has been ruled out. Therefore, Case 2 is the case. QED

(*) Pf that $\gcd(nq,n) = n$

Let $\gamma:=\gcd(nq,n)$. Then we have integers $\gamma_1, \gamma_2$ s.t. $\gamma=nq\gamma_1+n\gamma_2 \implies \frac{\gamma}{n}=q\gamma_1+\gamma_2$. Now converse to Bézout's identity is false, so we can't just say $1=\gcd(q,1)=\frac{\gamma}{n} \implies \gamma=n$. However, because $\frac{\gamma}{n}$ is of the form $qd_q+1d_1$ where $d_q, d_1$ are integers, we have that $1=\gcd(q,1)=\frac{\gamma}{n}$ if $\frac{\gamma}{n}$ divides both $q$ and $1$ (See here). Now $\gamma$, by its definition, divides both $nq$ and $n$, i.e. we have integers $\delta_1, \delta_2$ s.t. $\gamma\delta_1=nq, \gamma\delta_2=n$. Hence, $\frac{\gamma}{n}\delta_1=q, \frac{\gamma}{n}\delta_2=1$, i.e. $\frac{\gamma}{n}$ divides both $q$ and $1$. Therefore, $1=\gcd(q,1)=\frac{\gamma}{n} \implies \gamma=n$ QED

Alternatively, we can show $\gcd(nq,n) = n$ by using the GCD Properties, $\gcd(a+cb,b)=\gcd(a,b)$ and $\gcd(a,0)=a$ for any positive integers $a,b,c$.

Pf: By the first property, $\gcd(nq,n)=\gcd(n,0)$. By the second property $\gcd(n,0)=n$. Therefore, $\gcd(nq,n)=\gcd(n,0)=n$. QED

(**) GCD Property: $\gcd(a+cb,b)=\gcd(a,b)$ for any positive integers $a,b,c$.

(****) Euclid's lemma:

Let $\frac{bc}{a}$ be an integer and $\gcd(a,b)=1$. Then $\frac c a$ is an integer.

Pf: First, Bézout's identity's converse is true for $\gcd(a,b)=1$ (see here), so we have integers $a_1, b_1$ s.t. $1=aa_1+bb_1$. (Alternatively, we can use Integer Combination of Coprime Integers, which is Cor 2.3.6 in the textbook.) Then $$1=aa_1+bb_1 \implies \frac c a = ca_1+\frac{bc}{a}b_1$$

By assumption $\frac{bc}{a}$ is an integer, so $\frac c a$ is an integer because we have written $\frac c a$ as a sum of products of integers. QED

It is healthy to observe first that $x^k=x^r$.

Next to that we have $d:=\gcd(k,n)=\gcd(nq+r,n)=\gcd(r,n)$ so it is enough to prove that the order of $x^r$ equals $n/d=n/\gcd(r,n)$ under the suitable extra condition that $r\in\{0,\dots,n-1\}$.

You proved that $(x^k)^{n/d}=(x^n)^{k/d}=1$ by showing that $k/d$ is an integer. This is of course the same as $(x^r)^{n/d}=1$ and - denoting $m$ as order of $x^r$ - this excludes that $m>n/d$. So from here it remains to prove that it cannot be that $m<n/d$.

I noticed for this the following possibility:

If $m<n/d$ then $rm<rn/d=rn/\gcd(r,n)=\text{lcm}(r,n)$.

That excludes the possibility that $rm$ (which is a multiple of $r$) is also a multiple of $n$ (and you are ready: we cannot have $x^{rm}=1$ if $rm$ is not a multiple of $n$).

Of course this discovery makes me as a mathematician reluctant to go through the rest of the proof.

I have no doubt that you have understanding for that.

If there are things that are not clear then I advice you to formulate that in a new question with a link to this question.