-1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Dietrich Burde Aug 27 '18 at 10:54
  • 3
    $\begingroup$ 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. $\endgroup$ – Dietrich Burde Aug 27 '18 at 11:01
  • 6
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Aug 28 '18 at 5:39
  • 2
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Aug 28 '18 at 5:42
  • 2
    $\begingroup$ 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$. $\endgroup$ – drhab Aug 28 '18 at 9:08
3
+100
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.