Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 37 Ā· Cosets and Lagrange

Consequences of Lagrange's Theorem

Use Lagrange to show element orders divide |G|, that groups of prime order are cyclic, and to prove Fermat's little theorem and Euler's theorem.

Lagrange's theorem has a series of quick corollaries. Each is one or two lines once you know the theorem, yet together they cover prime-order groups, powers of elements and two of the most famous results in number theory.

Corollary 1: the order of an element divides |G|

For a ∈ G the cyclic subgroup ⟨a⟩ = {e, a, a², ..., a^{k-1}} has exactly k = |a| elements (the order of a). By Lagrange, k divides |G|. Consequently:

For every a ∈ G (finite), a^{|G|} = e.

Write |G| = km; then a^{|G|} = (aįµ)ᵐ = eᵐ = e.

Python a^|G| = e in several groups

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Corollary 2: groups of prime order are cyclic

Let |G| = p, a prime, and pick a ≠ e. The order of a divides p and is not 1, so it equals p. Thus ⟨a⟩ has p elements: ⟨a⟩ = G. Therefore G is cyclic, generated by any non-identity element, and isomorphic to ℤ_p. This explains why there is only one group of each prime order.

Corollary 3: Fermat's little theorem

Theorem. If p is prime and a is not divisible by p, then a^{p-1} ≔ 1 (mod p).

Proof. The nonzero residues form a group U(p) of order p - 1. By Corollary 1, a^{p-1} = 1 in that group. āˆŽ

Equivalently, aįµ– ≔ a (mod p) for every integer a.

Corollary 4: Euler's theorem

Theorem. If gcd(a, n) = 1 then a^{φ(n)} ≔ 1 (mod n).

Proof. U(n) is a group of order φ(n), and Corollary 1 gives a^{φ(n)} = 1. āˆŽ

Python Verify Fermat and Euler

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line shows the main practical use: reduce huge exponents modulo φ(n). Since 7⁓ ≔ 1 (mod 10), 7²²² = (7⁓)⁵⁵ Ā· 7² ≔ 7² = 49 ≔ 9.

These theorems are used in cryptography: RSA decryption relies on Euler's theorem to show that (m^e)^d ≔ m (mod n) when ed ≔ 1 (mod φ(n)). We return to it in chapter 8.

Corollary 5: subgroup orders and index tricks

  • A group of order p² (p prime) has subgroups of order p only (besides the trivial ones), because the only divisors are 1, p, p².
  • If H and K are subgroups with coprime orders, then H ∩ K = {e}, since |H ∩ K| divides both orders.
  • A subgroup of index 2 contains every square of the group. (This index-2 trick shows, for example, that A_n is normal in S_n.)
Python Intersection of coprime-order subgroups

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

flowchart TB
    L["Lagrange: |H| divides |G|"] --> A["|a| divides |G|"]
    A --> B["a^|G| = e"]
    B --> F["Fermat: a^(p-1) ≔ 1"]
    B --> E["Euler: a^φ(n) ≔ 1"]
    L --> P["prime order ⇒ cyclic"]

One counting theorem fans out into several famous results.

Check your understanding

Quick check Ā· 4 questions

of 4 answered You scored / 4 Ā· perfect!

  1. 1. A group of order 13 must be:

    13 is prime, so any non-identity element generates the whole group.
  2. 2. What is 3^6 mod 7?

    By Fermat's little theorem 3^(7-1) ≔ 1 (mod 7).
  3. 3. If gcd(a, 20) = 1, what is a^8 mod 20?

    φ(20) = 8, so Euler's theorem gives a^8 ≔ 1 (mod 20).
  4. 4. Which of these cannot be the order of an element of a group with 14 elements?

    Element orders divide 14, and 4 does not.

Summary

  • In a finite group, |a| divides |G| and a^{|G|} = e.
  • A group of prime order is cyclic and generated by any non-identity element.
  • Fermat's little theorem and Euler's theorem are special cases applied to U(p) and U(n).
  • Subgroups of coprime order intersect trivially.

Next: Group Actions, Orbits and Stabilizers