Back to the on-screen lesson ·
The least power that returns the identity, why it is the size of the subgroup the element generates, and the formula $n/\gcd(n, k)$ that gives it in one step.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to compute the order of an element by taking powers, use $n/\gcd(n, a)$ for a residue modulo $n$ and $n/\gcd(n, k)$ for a power of an element of known order, explain why the order is the size of the cyclic subgroup generated, tell the two groups of order four apart by their element orders, and prove that every exponent returning the identity is a multiple of the order.
The Cayley table showed a whole group at once. This lesson looks at one element and does the simplest thing possible with it: apply it again and again. In a finite group that has to repeat eventually, and the number of steps before it comes back to the identity turns out to carry most of the information about where that element sits.
For $n > 0$, $g^{n}$ means $g$ combined with itself $n$ times; $g^{0} = e$ and $g^{-n} = (g^{n})^{-1}$. The order of $g$, written $|g|$ or $\operatorname{ord}(g)$, is the least $n > 0$ with $g^{n} = e$, and is infinite if no such $n$ exists. $\langle g \rangle$ is the set of all powers of $g$, the cyclic subgroup generated by $g$. An element whose powers give the whole group is a generator. In additive notation, $g^{n}$ is written $ng$.
The order of an element $g$ is the least $n > 0$ with $g^{n} = e$; if there is none, the order is infinite. Three facts do all the work.
The order is the size of $\langle g \rangle$. If $|g| = n$ then $e, g, g^{2}, \ldots, g^{n-1}$ are distinct — two equal ones would give a smaller positive exponent returning the identity — and every power is one of them, because exponents may be reduced modulo $n$. So $|\langle g \rangle| = n$.
The exponents that give the identity are exactly the multiples of the order. $g^{k} = e$ if and only if $n \mid k$. This is the division algorithm, and it is proved in this lesson's last item.
The order of a power. If $|g| = n$ then
$$|g^{k}| = \frac{n}{\gcd(n, k)}.$$
In the integers modulo $n$ under addition, $g = 1$ has order $n$ and the element $a$ is $1$ added $a$ times, so
$$|a| = \frac{n}{\gcd(n, a)}$$
and the elements of order exactly $n$ — the generators — are precisely those coprime to $n$.
Most of the theorems in this course are counting arguments wearing algebraic clothes. Cosets all have the same size, so a subgroup's order divides the group's; the remainders below a degree are a finite list, so a quotient by an irreducible polynomial is a finite field.
Another way: picture
Stand on a clock face with $n$ hours and step forward $a$ hours at a time. You visit the multiples of $\gcd(a, n)$ and nothing else, and you are back where you started after $n/\gcd(a, n)$ steps. Step by $1$ and you visit every hour; step by a number sharing a factor with $n$ and you visit only some of them, returning sooner.
Another way: steps
To find the order of an element: 1. In the integers modulo $n$, use $n/\gcd(n, a)$ directly. 2. In a multiplicative group, compute $g, g^{2}, g^{3}, \ldots$ until the identity appears; the exponent that first reaches it is the order. 3. For a power $g^{k}$ of an element of known order $n$, use $n/\gcd(n, k)$ rather than recomputing. 4. Sanity check: the order always divides the order of the group.
Once every element's order is known, a surprising amount is settled without any further computation.
| Group | Orders that occur | What that shows |
|---|---|---|
| integers modulo $4$ | $1, 2, 4, 4$ | an element of order $4$: cyclic |
| units modulo $8$ | $1, 2, 2, 2$ | nothing of order $4$: the Klein four-group |
| units modulo $9$ | $1, 2, 3, 3, 6, 6$ | an element of order $6$: cyclic |
| symmetries of a triangle | $1, 3, 3, 2, 2, 2$ | three self-inverse elements: not cyclic |
Two groups with different lists of orders cannot be isomorphic, because an isomorphism preserves order — if $\phi$ is a bijection respecting the operation and $g^{n} = e$, then $\phi(g)^{n} = e$, and the same argument backwards. That is the cheapest test there is for telling two groups apart, and it settles the order-four case completely.
It does not always succeed. There are pairs of non-isomorphic groups with identical lists of element orders, the smallest having order $16$. But for everything in this course, counting orders is enough.
One more consequence, used constantly later: in a finite group every element has finite order. The powers $g, g^{2}, g^{3}, \ldots$ cannot all be different in a finite set, so $g^{i} = g^{j}$ for some $i < j$, and cancelling gives $g^{j-i} = e$ with $j - i > 0$.
Confusing the order of an element with the order of the group. They are different numbers, written the same way. $|g|$ is about one element; $|G|$ is how many elements there are.
Taking the first exponent that looks promising. The order is the least positive exponent giving the identity. $g^{6} = e$ does not make the order $6$ if $g^{3} = e$ as well.
Thinking a bigger element has a bigger order. In the integers modulo $12$, the element $1$ has order $12$ and the element $6$ has order $2$.
Multiplying the order by $k$ to get the order of $g^{k}$. The formula divides: $|g^{k}| = n/\gcd(n, k)$, and taking bigger steps returns you sooner, not later.
Assuming an infinite group has elements of infinite order. The identity always has order $1$, and in the non-zero rationals under multiplication $-1$ has order $2$.
$U(9) = \{1, 2, 4, 5, 7, 8\}$. Powers of $2$: $2, 4, 8, 7, 5, 1$ — six steps to reach $1$.
So $|2| = 6$, and $2$ generates.
Then $|2^{2}| = |4| = 6/\gcd(6, 2) = 3$, and $|2^{3}| = |8| = 6/\gcd(6, 3) = 2$.
The formula, instead of recomputing.
Check the last one: $8^{2} = 64 = 63 + 1 \equiv 1$. Correct, and $8 \equiv -1$, which had to be self-inverse.
A check that costs one line.
In the integers under addition, take $g = 3$. Its powers are $3, 6, 9, \ldots$ and $-3, -6, \ldots$
Additive notation: $g^{n}$ is $3n$.
No positive multiple of $3$ is $0$, so the order is infinite and $\langle 3 \rangle$ is infinite too.
No exponent returns the identity.
Every element except $0$ has infinite order here, and $\langle g \rangle$ is still the whole of $g\mathbb{Z}$ — infinite order and generating are different things.
Order infinite, subgroup still proper.
Use $|g^{k}| = n/\gcd(n, k)$ with $n = 30$ and $k = 12$. The highest common factor of $30$ and $12$ is $6$.
The formula, not a recomputation.
So the order is $30/6 = 5$.
Check: $(g^{12})^{5} = g^{60} = (g^{30})^{2} = e$.
And $5$ divides $30$, as every order of a power must. Note that $g^{12}$ and $g^{18}$ have the same order and generate the same subgroup.
In the integers modulo $24$ under addition, write down the order of each element.
| Its order | |
|---|---|
| 4 | |
| 6 | |
| 0 |
In the integers modulo $20$ under addition, what is the order of $16$?
Answer:
In the integers modulo $12$ under addition, match each element to its order.
| order $2$ | order $3$ | order $4$ | order $6$ | order $12$ | |
|---|---|---|---|---|---|
| $2$ | |||||
| $3$ | |||||
| $4$ | |||||
| $6$ |
Put these elements of the integers modulo $12$ in increasing order of their order.
Number the steps in order (write the number in the box):
An element $g$ has order $15$. What is the order of $g^{5}$?
Answer:
Build the proof that if $g^{k} = e$ then the order of $g$ divides $k$.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
In the integers modulo $18$ under addition, write down the order of each element.
| Its order | |
|---|---|
| 3 | |
| 6 | |
| 0 |
You can compute the order of an element and of one of its powers, and you know the order is the size of the subgroup it generates. Say in your own words why the exponents that give the identity are exactly the multiples of the order. Next: subgroups in general, and the one-line test for them.
9. Your turn: an element $g$ has order $30$. What is the order of $g^{12}$?, step 3