# 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).

And different from this one:

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.

Therefore, we have that $$d 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.

Therefore, we have, again, that $$d 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

• I admire your energy with the proof, but it appears to be to long. What do you think about the standard proofs in algebra books, or lecture notes? – Dietrich Burde Aug 27 '18 at 10:54
• I am sorry, but this does not sound interesting to me. I think it is up to you now to compare with the text book proofs (not the ones frorm this site necessarily) I find the existing proofs pretty nice, and do not see why to invest so much time for (perhaps new) proofs. But I am sure someone here is better than me. – Dietrich Burde Aug 27 '18 at 11:01
• I really don't see the point of this post. Glad to see you decided to start a first course in group theory. But the post looks more like study diary as opposed to an actual question to me. – Jyrki Lahtonen Aug 28 '18 at 5:39
• But I can't bring myself to dv this. After all the trouble you went thru in producing it. I'm skeptical about it being a useful addition, but that should be discussed in meta. – Jyrki Lahtonen Aug 28 '18 at 5:42
• Critics on your treatment of case 1.2: you conclude that $1/m$ is an integer because else $\gcd(n(q+\frac1m),n)$ should not "exist". Why not? Likewise we could reason that e.g.$1/3$ must be an integer because else $\gcd(3(1+\frac13),3)$ does not exist (which makes no sense of course). Shortcut: if $m<\frac{n}{\gcd(r,n)}$ then $mr<\frac{nr}{\gcd(r,n)}=lcm(r,n)$ This tells us that $mr$ (which is a multiple of $r$) cannot also be a multiple of $n$. – drhab Aug 28 '18 at 9:08

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.

• LOL thanks drhab. I won't accept for now to allow for other answers or comments ;) – BCLC Aug 28 '18 at 12:10
• Of course. That is the best strategy. – drhab Aug 28 '18 at 12:14
• Oh DRAT!!! I thought gcd(k,n)=gcd (r,n) was wrong. Ok I'll analyse further. – BCLC Aug 28 '18 at 14:49
• drhab, posted answer – BCLC Aug 28 '18 at 15:15
• @BCLC Deals with special case of $n$ being prime and consequently $\gcd(n,r)=1$. – drhab Aug 31 '18 at 19:56

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