Vtyjkyuk

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

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 xrangle=1,x,x^2,dotsc,x^n-1le G$$
We can say no more at this point about the relationship between $|langle xrangle|$ 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,rinmathbbZ$ s.t. $k=nq+r$, $0le r<n$. Now

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

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

$(3)$ Let $d=gcd(k,n)$. Then $operatornameord(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$, $1le r<p$, $gcd(k,p)=1$. Then $operatornameord(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 $1le kle p-1$, that $gcd(k,p)=1$. This then gives the order of each nonidentity element $x^k$ as $operatornameord(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^kranglele 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 $aneq1$. Then $G$ is the cyclic group $langle arangle$ generated by $a$.

Artin proves this by Lagrange; he states if $aneq1$, 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 arangle=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 $nleq 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 arangle=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:
beginalign*
langle xrangle&=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 =dotsx^(j-1)n+1,x^(j-1)n+2,dotsc,x^jn=1=dotstag1
endalign*

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 $0equiv ppmodp$, 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 xrangle$ repeatedly, and not the whole of $G$, since we have assumed $n<p$. This means $jn=p$. If not, then we should have $x^pneq1$, which implies $x^0=x^k$ for some $1leq k< n$. But this contradicts the uniqueness of the identity, so $jn=p$ has to have $n=p$, $j=1$ and $langle xrangle=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 $xneq1$ 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 $kne 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 $kne 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.

Let $x$ be an element of finite order $n$ in a group, and $k,q,rinmathbbZ$ s.t. $k=nq+r$, $0le 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 $operatornameord(x^k)=n/d$

$(4)$ Let $n=p$ be a prime. Then for $k=pq+r$, $1le r<p$, $gcd(k,p)=1$. Then $operatornameord(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 $aequiv bpmodp$ this means $a=b$, i.e. they are both in the same residue class, and so for the rest.

Now for $a$, $bin 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+3equiv1pmod5$, or in general $x^a=ax=underbracex+dotsb+x_text$a$ times$. Now $aequiv bpmodp$ 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 $anotequiv bpmodp$ then $x^aneq x^b$. So assume this does hold for some $a$, $bin S$ and derive a contradiction. WLOG, let $0le b<a<p$, where $a-b=cin S$ also with $cneq0$. Let $x$ be a nonidentity element. We can write $x^a$ and $x^b$ as multiples in the congruence thus: $axequiv bxpmodp$, and so $ax-bx=(a-b)xequiv cxequiv0pmodp$. Now $a$, $b$, $cin S$, with only $b$ having the possibility of being zero, since we took $a>b$. But since $xneq0$ we must have $c=0$ and $a=b$, contrary to what was assumed.

Hence if $anotequiv bpmodp$ then $x^aneq 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 1le ile p-1$$

Let $y$ be some nonidentity element of $G$. Consider the cyclic subgroup $langle y^crangle$, where $c$ is some number in the range $0<cle 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^crangle$ can be put into a bijection with $X$.

Hence $langle y^crangle$ and the whole group $G$ exhaust all elements and we have
$$langle y^cranglecong G$$
Hence we have $p-1$ cyclic subgroups, $langle y^crangle$, generating $G$.

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

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=nfracq_nq_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(nfracq_nq_p,n)=ngcd(fracq_nq_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_prho$ for $rho in mathbb Z$. Then $k=gcd(k,k)=gcd(nq_n,pq_p)=gcd(rho q_p q_n,pq_p)=q_pgcd(rho q_n,q_p)$. Therefore, $pq_p=k=q_pgcd(rho q_n,q_p) implies p=gcd(rho q_n,q_p)=gcd(fracnq_pq_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