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
 A: 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.
A: Cases 1.2 and 1.3
By $(**)$ in the post, I was actually right about $$d=\gcd(k,n)=\gcd(r,n) \tag{***}$$
We'll use $(***)$ and $m < \frac n d$ to derive contradictions because for both cases 1.2 and 1.3, $m < \frac n d \implies d < r$.
Proofs for Cases 1.2 and 1.3:
Case 1.2 $rm=n$
$$d=\gcd(k,n)=\gcd(r,n)=\gcd(r,rm)=r\gcd(1,m)=r(1)=r$$
Therefore, we have $d=r$ and $d<r$. ↯
Case 1.3 $rm>n$
$$d=\gcd(k,n)=\gcd(r,n)=\gcd(r,\frac{rm}{l})$$
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 we have $d=r$. This contradicts $d<r$. ↯
QED

Update: I think proofwiki's proof/s is/are similar to mine:
https://proofwiki.org/wiki/Order_of_Power_of_Group_Element
https://proofwiki.org/wiki/Order_of_Subgroup_of_Cyclic_Group
