Back to the on-screen lesson ·
Element orders divide the group order, every group of prime order is cyclic, and Fermat's and Euler's theorems are the same counting argument inside the group of units.
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 list the possible element orders in a group of given size, reduce a large exponent using the order of the group, state and use Fermat's and Euler's theorems as instances of Lagrange, explain why every group of prime order is cyclic, and separate what the corollaries forbid from what they would have to produce and cannot.
Lagrange says a subgroup's order divides the group's. On its own that is a statement about subgroups, and subgroups are not what most questions are about. The corollaries come from choosing the subgroup cleverly: the cyclic subgroup an element generates, or the group of units modulo $n$. Each choice turns the theorem into something that looks like a different subject.
The order of an element is the size of the cyclic subgroup it generates. Euler's function $\phi(n)$ counts the residues coprime to $n$, and is the order of the group $U(n)$ of units modulo $n$. Euler's theorem says $a^{\phi(n)} \equiv 1 \pmod n$ for $a$ coprime to $n$; Fermat's little theorem is the case $n = p$ prime, giving $a^{p-1} \equiv 1 \pmod p$.
Take $H = \langle g \rangle$. Its order is the order of $g$, so:
Take $G = U(n)$, the units modulo $n$ under multiplication. Its order is $\phi(n)$, so corollary 2 reads
$$a^{\phi(n)} \equiv 1 \pmod n \quad \text{for } \gcd(a, n) = 1,$$
which is Euler's theorem; with $n = p$ prime it is Fermat's little theorem, $a^{p-1} \equiv 1 \pmod p$.
That is the whole content of the lesson: two choices of subgroup, four famous statements. It is worth noticing what has happened — a theorem about tiling a finite set has become the tool that makes modular exponentiation cheap, and cheap modular exponentiation is what public-key cryptography runs on.
What none of them does is produce anything. Lagrange forbids; it never supplies an element of a given order or a subgroup of a given size. That there is an element of order $p$ whenever $p$ divides $|G|$ is Cauchy's theorem, which is true and is proved differently.
Another way: picture
Picture a clock whose face has $|G|$ marks, and an element $g$ that advances the hand by a fixed step. The hand visits a ring of evenly spaced marks and returns to the top after $|g|$ steps. Because the ring has to fit the face exactly, the number of marks in the ring divides the number on the face — and going round $|G|$ times must land on the top, whatever the step was. That is corollary 2, with no algebra in it.
Another way: steps
To use the corollaries: 1. To rule out an element order: check divisibility against $|G|$. 2. To reduce a large power in a group: divide the exponent by $|G|$ and keep the remainder. 3. Modulo $n$: the group is $U(n)$ and its order is $\phi(n)$, so reduce the exponent modulo $\phi(n)$. 4. For a group of prime order: conclude cyclic immediately, and stop.
The pattern is always the same. To find $a^{k} \bmod n$ with $a$ coprime to $n$:
So an exponent of any size collapses to one below $\phi(n)$. Computing $7^{1000} \bmod 11$ becomes computing $7^{0} = 1$, because $\phi(11) = 10$ divides $1000$.
Two cautions. First, $a$ must be coprime to $n$: $2^{k} \bmod 4$ does not reduce this way, because $2$ is not a unit. Second, $\phi(n)$ is an exponent that works, not necessarily the smallest one that does. The least exponent returning every unit to $1$ is called the Carmichael function and can be smaller — modulo $8$ every unit squares to $1$, although $\phi(8) = 4$.
The same reduction is the reason RSA works. There the modulus is a product of two large primes, $\phi(n) = (p-1)(q-1)$, and encryption raises to a power $e$ while decryption raises to a power $d$ chosen so that $ed \equiv 1 \pmod{\phi(n)}$. Then $(a^{e})^{d} = a^{ed} = a^{1 + m\phi(n)} \equiv a$, by exactly the corollary above. Someone who knows $\phi(n)$ can find $d$; someone who knows only $n$ apparently cannot, because finding $\phi(n)$ is as hard as factoring. The security rests on a counting theorem about cosets.
*Reading divides as occurs.* That every element order divides $|G|$ does not mean every divisor is an element order. A group of order $4$ may have no element of order $4$.
Using Euler's theorem on a non-unit. $a^{\phi(n)} \equiv 1$ needs $\gcd(a, n) = 1$. Without it the statement is simply false.
Reducing the exponent modulo $n$ instead of modulo $\phi(n)$. The base lives modulo $n$; the exponent lives modulo the order of the group, which is $\phi(n)$.
Thinking $\phi(n)$ is the order of every element. It is the order of the group, and individual elements may return sooner.
Claiming Cauchy's theorem as a corollary of Lagrange. It is a real theorem with a real proof, and it goes in the direction Lagrange does not.
Possible element orders: divisors of $15$, so $1, 3, 5$ or $15$.
Lagrange, applied to cyclic subgroups.
So no element has order $2$, and in particular no element is its own inverse except the identity.
Forbidding.
Pairing each element with its inverse then leaves the identity alone and pairs up the other fourteen, which is consistent — and it is why a group of even order must have an element of order two.
The same count, run the other way.
Find $7^{2024} \bmod 15$. First $\phi(15) = \phi(3)\phi(5) = 2 \times 4 = 8$, and $\gcd(7, 15) = 1$.
The order of the group of units.
$2024 = 8 \times 253 + 0$, so $7^{2024} \equiv (7^{8})^{253} \equiv 1$.
The exponent reduces to zero.
Check the machinery on a smaller case: $7^{2} = 49 \equiv 4$, $7^{4} \equiv 16 \equiv 1$. So $7$ has order $4$, which divides $8$ as it must.
The element returned sooner than the group forced it to.
$\phi(9) = 6$ and $\gcd(2, 9) = 1$, so $2^{6} \equiv 1 \pmod 9$.
The order of the group of units.
$100 = 6 \times 16 + 4$, so $2^{100} \equiv 2^{4} = 16$.
Divide and keep the remainder.
$16 \equiv 7 \pmod 9$. Note $2$ in fact has order $6$ here, so no smaller exponent than $6$ would have done.
A group has $14$ elements. List the four orders an element of it could possibly have, smallest first; the smallest is given.
| A possible order | |
|---|---|
| Smallest | 1 |
| Second smallest | |
| Third smallest | |
| Largest |
Put the steps of computing $3^{100}$ modulo $7$ into order.
Number the steps in order (write the number in the box):
A group has $7$ elements. Could it have a subgroup with $3$?
Each of these follows from Lagrange applied to one particular subgroup. Match the statement to that subgroup.
| the cyclic subgroup generated by $g$ | the group of units modulo a prime | the subgroup generated by any non-identity element of a group of prime order | the group of units modulo $n$ | the trivial subgroup | |
|---|---|---|---|---|---|
| The order of $g$ divides the order of the group | |||||
| Raising a unit modulo a prime $p$ to the power $p - 1$ gives $1$ | |||||
| A group of prime order is cyclic | |||||
| Raising a unit modulo $n$ to the power $\phi(n)$ gives $1$ |
What exponent does Lagrange guarantee returns every unit modulo $15$ to $1$?
Answer:
Select every conclusion that the corollaries of Lagrange's theorem support.
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.
A group has $14$ elements. List the four orders an element of it could possibly have, smallest first; the smallest is given.
| A possible order | |
|---|---|
| Smallest | 1 |
| Second smallest | |
| Third smallest | |
| Largest |
You can list possible element orders, reduce a large power modulo $n$, and say which famous theorems are Lagrange in disguise. Say in your own words why $a^{\phi(n)} \equiv 1$ needs $a$ to be coprime to $n$. Next: normal subgroups, the ones whose left and right cosets agree.
9. Your turn: find $2^{100} \bmod 9$., step 3