What is the relation between 'the order of $x^k = n/{\gcd(k,n)}$' and Lagrange's Theorem?

Question

Algebra by Michael Artin Cor 2.8.11 to Lagrange's Theorem (Theorem 2.8.9).

Question: What is the relation between Cor 2.8.11 and the order of $x^k$ given by $n/{\gcd(k,n)}$ (in the text, this is in the 3rd bullet point of Prop 2.4.3)? (*)

• I was thinking something like $1=\gcd(k,p)$ for all $1 \le k < p$, so somehow the order of the non-identity elements of a group of prime order would be shown to be $p/{\gcd(k,p)} = p/1 = p$. I think this would be a way to show Cor 2.8.11 without Cor 2.8.10 to Lagrange's Theorem (Theorem 2.8.9), Lagrange's Theorem itself (Theorem 2.8.9) or even the Counting Formula (Formula 2.8.8).

• Or perhaps it's more the converse: that Cor 2.8.11 implies 3rd bullet of Prop 2.4.3 in the case that $n$ is prime?

---

(*) 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$.

Answer 1

To answer your question directly w.r.t. the direction Artin takes regarding order and Lagrange.

Well Prop.2.4.2 sets up cyclic groups, so we know, for some element $x$ in a group $G$, that taking powers of $x$ generates a cyclic subgroup of $G$, and that it is of order $n$:
$$\langle x\rangle=\{1,x,x^2,\dotsc,x^{n-1}\}\le G$$ We can say no more at this point about the relationship between $|\langle x\rangle|$ and $|G|$.

Let $x$ be an element of order $n$. Then the next proposition from Artin gives the recipe for the order of an arbitrary power of $x$, say $x^k$:

Proposition 2.4.3

Let $x$ be an element of finite order $n$ in a group $G$, and $k,q,r\in\mathbb{Z}$ s.t. $k=nq+r$, $0\le r<n$. Now

$(1)$ $x^k=x^r$

$(2)$ $x^k=1$ iff $r=0$

$(3)$ Let $d=\gcd(k,n)$. Then $\operatorname{ord}(x^k)=n/d$

Now lets see where we are immediately after Prop.2.4.3. A particular case of $(3)$ of Prop.2.4.3 in the case that $n$ is prime is immediate, even though Artin does not explicitly state it here as a corollary. For convenience let us define it as $(3a)$:

$(3a)$ Let $n=p$ be a prime. Then for $k=pq+r$, $1\le r<p$, $\gcd(k,p)=1$. Then $\operatorname{ord}(x^k)=p/1=p$

So let's see what Prop.2.4.3 gets us with this particular case of having $n=p$, i.e., when our element $x$ has the order of a prime $p$.

Well $(2)$ tells us the only power of $x$ that gives the identity is $x^0=1$, so for the set of powers $$X=\{x^0,x^1,x^2,\dotsc,x^{p-1}\}$$ we know none of $x^1$, $x^2,\dotsc,x^{p-1}$ equal $1$.

The next question is then what of the orders of $x^1$, $x^2,\dotsc,x^{p-1}$? Well $(3)$ tells us this: we know, for $1\le k\le p-1$, that $\gcd(k,p)=1$. This then gives the order of each nonidentity element $x^k$ as $\operatorname{ord}(x^k)=p/\gcd(k,p)=p/1=p$, and so each of the $p-1$ number of nonidentity elements $x^k$ generate a cyclic subgroup of order $p$, $$\langle x^k\rangle\le G$$

Now Prop.2.4.3 does not mention the actual relationship between the order of the group $G$ and the cyclic subgroups of order $p$ formed by the $p-1$ nonidentity elements of order $p$, just that they exist within it.

Upto this point Artin has not mentioned homomorphisms, isomorphisms, equivalence relations or partitions.

Now in section 2.2 Artin defines the order of a group $G$ as $$|G|=\text{ the number of elements $G$ contains.}$$ So for us $|G|=p$. Again Artin has not mentioned isomorphisms by Prop.2.4.3 so we can't talk of isomorphism classes, but again that is not what is needed for Corollary 2.8.11.

Now we must ask: can Corollary 2.8.11 be a corollary to Prop.2.4.3? Let's look at it:

Corollary 2.8.11 Suppose that $G$ has prime order $p$. Let $a\neq1$. Then $G$ is the cyclic group $\langle a\rangle$ generated by $a$.

Artin proves this by Lagrange; he states if $a\neq1$, then, by Lagrange, its order divides $|G|=p$ and so must be of order $p$ itself, since $p$ is prime, and so its cyclic subgroup generates $G$. QED.

We are coming from the other angle using what we know from Prop.2.4.3. Well we know about order, this means the number of elements in a group. We are told $G$ has order $p$, so now the question is: if $G$ has order $p$ does this mean that every nonidentity element $a$ in $G$ also has order $p$, which would then imply, without mentioning isomorphism as such, that $\langle a\rangle=G$? Remember Prop.2.4.3 only works if we know the order of the element in question, and thus far this could be anything in relation to $G$. We can't use division as Artin does as this uses Lagrange.

But what we do know is all about cyclic groups. So now we work backwards. Consider $G$, it has $p$ elements, $$G=\{a_1,a_2,\dotsc,a_p\}$$ Now let $a_1=1$, which, since $G$ is a group, the identity is unique and so no other elements are $1$. So what of the $p-1$ elements $a_2,\dotsc,a_p$? We know, by Section 2.4, that each element forms a cyclic subgroup of $G$ with order equal to the smallest integer s.t. $a_i^n=1$. So take some arbitrary nonidentity element $x$ in $G$ and consider its order $n$, with the powers of $x$ given in the set, $$X=\{x^1,x^2,\dotsc,x^{n-1},x^n=1\}$$ All we can say at the moment is that $n\leq p$. If we can deduce $n=p$ then from Prop.2.4.3 it quickly follows all nonidentity elements $a$ have order $p$, since $a$ was an arbitrary nonidentity element, and this in turn implies $\langle a\rangle=G$ since both have $p$ distinct elements, easy enough to set up a bijection here.

Now Prop.2.4.3 $(1)$ states $x^k=x^r$. So let $k=nq+r$, which by virtue of the cyclic group regenerating itself cyclically, we can take $q=0$, $1$, $2,\dotsc$, etc., to give $k=r$, $k=n+r$, $k=2n+r,\dotsc$, and so on. This generates sets of powers, each of size $n$ thus: \begin{align*} \langle x\rangle&=\{x^1,x^2,\dotsc,x^n=1\}=\{x^{n+1},x^{n+2},\dotsc,x^{2n}=1\}\\ &=\{x^{2n+1},x^{2n+2},\dotsc,x^{3n}=1\} =\dots\{x^{(j-1)n+1},x^{(j-1)n+2},\dotsc,x^{jn}=1\}=\dots\tag{1} \end{align*}

To complete the proof we look at the order of $G$ in relation to the order of the cyclic group and the repeating sets in $(1)$. Since there are $p$ elements in $G$ take an arbitrary nonidentity element $y$, then we know $y^0=y^{p}=1$, since $0\equiv p\pmod{p}$, that is the powers in the set $$Y=\{y^1,y^2,\dotsc,y^{p-1},y^p=y^0=1\}$$ cycle after every $p$th power is taken. Now the powers in $Y$ need not be distinct, so let us look at the sets in $(1)$ and assume that $n<p$. Then say it takes $j$ sets of $n$ elements to cycle through $p$ amount of elements: Note these sets only cycle through the $n$ elements in the subgroup $\langle x\rangle$ repeatedly, and not the whole of $G$, since we have assumed $n<p$. This means $jn=p$. If not, then we should have $x^p\neq1$, which implies $x^0=x^k$ for some $1\leq k< n$. But this contradicts the uniqueness of the identity, so $jn=p$ has to have $n=p$, $j=1$ and $\langle x\rangle=G$.

Therefore technically Prop.2.4.3 $(3a)$ only works if we know the order of a nonidentity element is $p$, but what we have to do first is consider the structure of the cyclic group itself, since we cannot assume that just because a group $G$ has order $p$ that any element in it actually has order $p$.

So to finish Prop.2.4.3 isn't enough on its own to imply Cor.2.11.8. Something like I have said above has to be explained first, and only then can we have Cor.2.11.8 as an actual corollary to Prop.2.4.3.

---

To quickly address the converse: whether Cor.2.8.11 implies $3$rd bullet of Prop.2.4.3 in the case that $n$ is prime. Cor.2.8.11 tells us every element $x\neq1$ of a group of order $p$ also has order $p$, and so they all generate $G$. We already know the order of $x^k$, for $k\ne p$, is equal to $p$ from Cor.2.11.8, and that this satisfies a particular case of the $3$rd bullet of Prop.2.4.3.

We can certainly note $\gcd(k,p)=1$, for $k\ne p$, and that the order of $x^k$ is $p$ by Cor.2.11.8, since these are precisely the nonidentity elements mentioned in Cor.2.11.8. So we can write the $3$rd bullet point in the case $|G|=p$, in the form $p/\gcd(k,p)=p$, but it doesn't imply, on its own, the actual $3$rd bullet point

Let $d$ be the greatest common divisor of $k$ and $n$. The order of $x^k$ is equal to $n/d$

so it would be more like just an observation at this stage.

Answer 2

Pf that Prop 2.4.3 implies Cor 2.8.11 without Counting Formula (Formula 2.8.8) or Lagrange's Theorem (Thm 2.8.9): Let $G$ be a group with prime order $p$. Then $|G|=p$. We must show that for any $x$ that is not the identity of $G$, we have that $\langle x \rangle = G$.

Consider $x \in G$ that is not the identity of $G$. Consider $x^k \in G$, where $k$ is an integer. By Euclidean algorithm, we can write $k=pq+r$ where $q$ and $r$ are integers s.t. $r=0,1,...p-1$.

By applying Prop 2.4.3 to G, we have, by the first and third bullet points, that order of $x^r =$ order of $x^k = p/{\gcd(k,p)} = p/\gcd(r,p)$, where the last equality is by a property of $\gcd$. Now for $r \ne 0$, i.e. $r=1,...,p-1$, we have that order of $x^r = p/{\gcd(r,p)}=p/1=p$ because $p$ is prime. Therefore, the $p-1$ elements $x^1,x^2,...,x^{p-1}$ each have order $p$, including $x^1$.

Since $x^1=x$ has order $p$, the $p-1$ elements $x^1,x^2,...,x^{p-1}$ are distinct from, not only each other, but also the identity. (Alternatively, we can argue using the second bullet point of Prop 2.4.3.)

Hence, we have distinct non-identity $p-1$ elements of $G$, namely $x^1,x^2,...,x^{p-1}$. Therefore, since $G$ has $p$ elements, $G = \langle x \rangle$. QED

Answer 3

Pf that Prop 2.4.3 implies Cor 2.8.11 without Counting Formula (Formula 2.8.8) or Lagrange's Theorem (Thm 2.8.9): Let $G$ be a group with prime order $p$. Then $|G|=p$. We must show that for any $x$ that is not the identity of $G$, we have that $\langle x \rangle = G$.

Consider $x \in G$ that is not the identity of $G$. Consider $x^k \in G$, where $k$ is an integer. By Euclidean algorithm, we can write $k=pq+r$ where $q$ and $r$ are integers s.t. $r=0,1,...p-1$.

By applying Prop 2.4.3 to G, we have, by the first and third bullet points, that order of $x^r =$ order of $x^k = p/{\gcd(k,p)} = p/\gcd(r,p)$, where the last equality is by a property of $\gcd$. Now for $r \ne 0$, i.e. $r=1,...,p-1$, we have that order of $x^r = p/{\gcd(r,p)}=p/1=p$ because $p$ is prime, including $x^1$.

We can show that the $p-1$ elements $x^1,x^2,...,x^{p-1}$ each have order $p$ and are distinct from, not only each other, but also the identity using the second bullet point of Prop 2.4.3. (Alternatively, we can deduce immediately from $x$'s having order $p$.)

• To show they are distinct from each other: If there are two that are the same say $x^{r_1} = x^{r_2}$ where $r_1, r_2 \in \{0,1,...,n-1=p-1\}$, then $x^{|r_1-r_2|} = 1$. Now, observe that $|r_1-r_2|$ is also in the set of exponents $\{0,1,...,n-1=p-1\}$, so by the second bullet point, $|r_1-r_2|=0$, i.e. $r_1=r_2$.

• To show they are distinct from identity: All of the exponents are in $0,1,...n-1=p-1$, so since none of the exponents are $0$ and $x=x^1$ has order $p=n$, by the second bullet point, none of the powers of $x$ are the identity.

Hence, we have distinct non-identity $p-1$ elements of $G$, namely $x^1,x^2,...,x^{p-1}$. Therefore, since $G$ has $p$ elements, $G = \langle x \rangle$. QED

Answer 4

Pf that Prop 2.4.3 implies Cor 2.8.11 without Counting Formula (Formula 2.8.8) or Lagrange's Theorem (Thm 2.8.9): Let $G$ be a group with prime order $p$. Then $|G|=p$. We must show that for any $x$ that is not the identity of $G$, we have that $\langle x \rangle = G$.

Consider $x \in G$ that is not the identity of $G$. Consider $x^k \in G$, where $k$ is an integer. By Euclidean algorithm, we can write $k=pq_p+r_p$ where $q_p$ and $r_p$ are integers s.t. $r_p=0,1,...p-1$.

By applying Prop 2.4.3 to G, we have, by the first and third bullet points, that order of $x^r =$ order of $x^k = p/{\gcd(k,p)} = p/\gcd(r_p,p)$, where the last equality is by a property of $\gcd$.

Now because $p$ is prime and $r_p=0,1,...p-1$, we have that order of $x^r =$ order of $x^k = p$ if $r_p \ne 0$ and $1$ if $r_p=0$.

Next, view $x$ as an element of $\langle x \rangle$. Observe that $\langle x \rangle$ is not only a subgroup of $G$ but also a group (this is probably why subgroups are so-called). Thus, $x$ is not identity in $\langle x \rangle$ because $x$ is not the identity of $G$. Consider $x^k \in \langle x \rangle$, where $k$ is the same integer as above. By Euclidean algorithm, we can write $k=nq_n+r_n$ where $n$ is the order of $x$ (in $G$ or $\langle x \rangle$) and $q_n$ and $r_n$ are integers s.t. $r_n=0,1,...n-1$. Observe that the order of $x$, which is $n$, cannot exceed the elements of $G$, which is $p$, we must have $n \le p$. (Of course we know by Lagrange's Theorem (Thm 2.8.9) or Counting Formula (Formula 2.8.8) that $n=p$, but the point is to not use either of those.)

By applying Prop 2.4.3 to $\langle x \rangle$, we have, by the first and third bullet points, that order of $x^r =$ order of $x^k = n/{\gcd(k,n)} = n/\gcd(r_n,n)$, where the last equality is by a property of $\gcd$.

Therefore, $n/\gcd(r_n,n)=p$ if $r_p \ne 0$ and $1$ if $r_p=0$.

Case 1: For $r_p \ne 0$, we have that $n/\gcd(r_n,n)=p$, i.e. $n$ is a positive multiple of $p$. This implies $n \ge p$. Therefore, $n=p$.

Case 2: For $r_p = 0$, we have that $n/\gcd(r_n,n)=1$, i.e. $r_n$ is a multiple of $n$. Since $r_n=0,1,...n-1$, $r_n=0$. Therefore, $pq_p=k=nq_n$. Hence, we can write $p$ as a product of 2 integers, each greater than or equal to 1: $p=n\frac{q_n}{q_p}$, where $\frac{q_n}{q_p} \ge 1$ because $n \le p$. Now, since $p$ is prime, we must have $p=n$ or $p=\frac{q_n}{q_p}$. In the latter case, we will have $n=1$ which contradicts our assumption that $x$ is not identity. Therefore, $n=p$.

Therefore, in either case, we have deduced $n=p$. We can finally proceed as in here or here to say $G = \langle x \rangle$. QED

Answer 5

Pf that Prop 2.4.3 implies Cor 2.8.11 without Counting Formula (Formula 2.8.8) or Lagrange's Theorem (Thm 2.8.9): Let $G$ be a group with prime order $p$. Then $|G|=p$. We must show that for any $x$ that is not the identity of $G$, we have that $\langle x \rangle = G$.

Consider $x \in G$ that is not the identity of $G$. Consider $x^k \in G$, where $k$ is an integer. By Euclidean algorithm, we can write $k=pq_p+r_p$ where $q_p$ and $r_p$ are integers s.t. $r_p=0,1,...p-1$.

By applying Prop 2.4.3 to G, we have, by the first and third bullet points, that order of $x^r =$ order of $x^k = p/{\gcd(k,p)} = p/\gcd(r_p,p)$, where the last equality is by a property of $\gcd$.

Now because $p$ is prime and $r_p=0,1,...p-1$, we have that order of $x^r =$ order of $x^k = p$ if $r_p \ne 0$ and $1$ if $r_p=0$.

Next, view $x$ as an element of $\langle x \rangle$. Observe that $\langle x \rangle$ is not only a subgroup of $G$ but also a group (this is probably why subgroups are so-called). Thus, $x$ is not identity in $\langle x \rangle$ because $x$ is not the identity of $G$. Consider $x^k \in \langle x \rangle$, where $k$ is the same integer as above. By Euclidean algorithm, we can write $k=nq_n+r_n$ where $n$ is the order of $x$ (in $G$ or $\langle x \rangle$) and $q_n$ and $r_n$ are integers s.t. $r_n=0,1,...n-1$. Observe that the order of $x$, which is $n$, cannot exceed the elements of $G$, which is $p$, we must have $n \le p$. (Of course we know by Lagrange's Theorem (Thm 2.8.9) or Counting Formula (Formula 2.8.8) that $n=p$, but the point is to not use either of those.)

By applying Prop 2.4.3 to $\langle x \rangle$, we have, by the first and third bullet points, that order of $x^r =$ order of $x^k = n/{\gcd(k,n)} = n/\gcd(r_n,n)$, where the last equality is by a property of $\gcd$.

Therefore, $n/\gcd(r_n,n)=p$ if $r_p \ne 0$ and $1$ if $r_p=0$.

Case 1: For $r_p \ne 0$, we have that $n/\gcd(r_n,n)=p$, i.e. $n$ is a positive multiple of $p$. This implies $n \ge p$. Therefore, $n=p$.

Case 2: For $r_p = 0$, we have that $n/\gcd(r_n,n)=1$, i.e. $r_n$ is a multiple of $n$. Since $r_n=0,1,...n-1$, $r_n=0$. Therefore, $pq_p=k=nq_n$. Hence, we can write $p$ as a product of 2 integers. $p=n\frac{q_n}{q_p}$. By Euclid's lemma, we have that either $n$ or $q_n$ is a multiple of $p$.

Case 2.1: $q_n$ is a multiple of $q_p$.

Then $$\gcd(p,n)=\gcd(n\frac{q_n}{q_p},n)=n\gcd(\frac{q_n}{q_p},1)=n(1)=n$$

Thus, $p$ is a multiple of $n$, so $n=1$ because $p$ is prime. That $n=1$ contradicts our assumption that $x$ is not identity. Therefore, $n=p$ vacuously in Case 2.1

Case 2.2: $n$ is a multiple of $q_p$.

Define $n=:q_p\rho$ for $\rho \in \mathbb Z$. Then $k=\gcd(k,k)=\gcd(nq_n,pq_p)=\gcd(\rho q_p q_n,pq_p)=q_p\gcd(\rho q_n,q_p)$. Therefore, $pq_p=k=q_p\gcd(\rho q_n,q_p) \implies p=\gcd(\rho q_n,q_p)=\gcd(\frac{n}{q_p}q_n,q_p)=\gcd(p,q_p)$. Therefore, $q_p$ is a multiple of $p$. Since $n$ is a multiple of $q_p$ and $q_p$ is a multiple of $p$, $n$ is a multiple of $p$. Since $n$ is an order, $n$ is a positive multiple of $p$. Then, $n \ge p$. Therefore, $n=p$.

Therefore, in either case, we have deduced $n=p$. We can finally proceed as in here or here to say $G = \langle x \rangle$. QED

Answer 6

Let $x$ be an element of finite order $n$ in a group, and $k,q,r\in\mathbb{Z}$ s.t. $k=nq+r$, $0\le r<n$. Now Prop.2.4.3 from Artin gives, (with $(4)$ added on)

$(1)$ $x^k=x^r$

$(2)$ $x^k=1$ iff $r=0$

$(3)$ Let $d=\gcd(k,n)$. Then $\operatorname{ord}(x^k)=n/d$

$(4)$ Let $n=p$ be a prime. Then for $k=pq+r$, $1\le r<p$, $\gcd(k,p)=1$. Then $\operatorname{ord}(x^k)=p/1=p$

---

Let $G$ be a group containing $p$ elements, where $p$ is a prime. Now consider the set $$S=\{0,1,2,\dotsc,p-1\}$$ These are $p$ numbers that are pairwise incongruent modulo $p$, and so form a complete set of residues modulo $p$. Equivalently each number in $S$ belongs to a different equivalence class, and since there are $p$ of them, with $p$ prime, then if $a$ and $b$ are in $S$ and we have $a\equiv b\pmod{p}$ this means $a=b$, i.e. they are both in the same residue class, and so for the rest.

Now for $a$, $b\in S$, we shall use addition of the integers modulo $p$ as our elements. So modulo $5$, $x$ can be one of $0$, $1$, $2$, $3$, $4$. Group composition is given by $+$ with the result taken modulo $p$, so if $x=3$, $x^2=3+3\equiv1\pmod{5}$, or in general $x^a=ax=\underbrace{x+\dotsb+x}_{\text{$a$ times}}$. Now $a\equiv b\pmod{p}$ implies $a=b$. (At this point all we can say is $x^0=x^0$, $x^1=x^1$, $x^2=x^2,\dotsc,x^{p-1}=x^{p-1}$.)

The problem now is that we cannot immediately say that if $a\not\equiv b\pmod{p}$ then $x^a\neq x^b$. So assume this does hold for some $a$, $b\in S$ and derive a contradiction. WLOG, let $0\le b<a<p$, where $a-b=c\in S$ also with $c\neq0$. Let $x$ be a nonidentity element. We can write $x^a$ and $x^b$ as multiples in the congruence thus: $ax\equiv bx\pmod{p}$, and so $ax-bx=(a-b)x\equiv cx\equiv0\pmod{p}$. Now $a$, $b$, $c\in S$, with only $b$ having the possibility of being zero, since we took $a>b$. But since $x\neq0$ we must have $c=0$ and $a=b$, contrary to what was assumed.

Hence if $a\not\equiv b\pmod{p}$ then $x^a\neq x^b$, and so the powers in the set $$X=\{x^0,\ x^1,\ x^2,\dotsc,x^{p-1}\}$$ are all distinct from each other.

Since the number of distinct elements in $G$ is $p$, this gives us $p-1$ nonidentity elements $x_i$ all forming sets of $p$ distinct elements, as in the set $X$, thus, $$X_i=\{x_i^0,x_i^1,x_i^2,\dotsc,x_i^{p-1}\},\quad 1\le i\le p-1$$

Let $y$ be some nonidentity element of $G$. Consider the cyclic subgroup $\langle y^c\rangle$, where $c$ is some number in the range $0<c\le p-1$. The multiples of $c$ are taken modulo $p$ to ensure a bijection with $S$, which then implies the set of elements thus formed in $\langle y^c\rangle$ can be put into a bijection with $X$.

Hence $\langle y^c\rangle$ and the whole group $G$ exhaust all elements and we have $$\langle y^c\rangle\cong G$$ Hence we have $p-1$ cyclic subgroups, $\langle y^c\rangle$, generating $G$.

Answer 7

Intuitive answer:

Cor 2.8.11 is about prime orders while Prop 2.4.3 is about relatively prime orders.

Observe Exer 2.4.6b (below) is answered by Prop 2.4.3.

Describe the number of elements that generate a cyclic group of arbitrary order n.