AFTD Auto-Formalizing Theoretical Domains

subgroup_units_pow_card_dvd

theoremverified

For a subgroup H of Lˣ where [L:F] = k and |F| = q, any divisor d of |H| satisfies q^k ≡ 1 (mod d).

Statement

theorem subgroup_units_pow_card_dvd {F L : Type*} [Field F] [Fintype F] [Field L] [Algebra F L] (q n k : ℕ) (H : Subgroup Lˣ) [Fintype H] (hH_card : Fintype.card H = n) (hq : Fintype.card F = q) (hdim : Module.finrank F L = k) (hk : 2 ≤ k) (d : ℕ) (hdn : d ∣ n) (hd : 1 < d) : (q : ZMod d) ^ k = 1
Source
step towards subgroup_rigidity_order_of_mds
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • subgroup_rigidity_order_of_mdsLet H be a cyclic subgroup of order n in the multiplicative group of a degree-k field extension L of F_q with 2 <= k <= n - 2. If every…

The proof, explained

As a degree-k extension of a finite field of size q, the field L has cardinality q^k, so its unit group Lˣ has order q^k - 1. By Lagrange's theorem, the order n of any subgroup H ≤ Lˣ divides q^k - 1. Since d divides n, d divides q^k - 1 as well, which yields q^k ≡ 1 (mod d).

  1. L is finite-dimensional over F, and consequently L is a finite field.

    Since the extension degree satisfies k = [L:F] ≥ 2 > 0, L is finite-dimensional over F by `Module.finite_of_finrank_pos`. Because the base field F is finite, L is also finite by `Module.finite_of_finite`.

    lines 3–7

    uses Module.finite_of_finrank_pos, Module.finite_of_finite

      have _ := hd
      have : Module.Finite F L := by
        have : 0 < Module.finrank F L := by omega
        exact Module.finite_of_finrank_pos this
      have : Finite L := Module.finite_of_finite F
  2. The cardinality of L is q^k.

    Equipping L with a `Fintype` instance via `nonempty_fintype`, the cardinality of L as a vector space of dimension k over a field of order q is q^k by `Module.card_eq_pow_finrank` and `Nat.card_eq_fintype_card`.

    lines 8–10

    uses nonempty_fintype, Nat.card_eq_fintype_card, Module.card_eq_pow_finrank

      have hL_card : Nat.card L = q ^ k := by
        cases nonempty_fintype L
        rw [Nat.card_eq_fintype_card, Module.card_eq_pow_finrank (K := F) (V := L), hq, hdim]
  3. d divides q^k - 1.

    By Lagrange's theorem (`Subgroup.card_subgroup_dvd_card`), the order of H divides |Lˣ|. The group of units Lˣ has order |L| - 1 = q^k - 1 by `Nat.card_units`. Since |H| = n and d ∣ n, transitivity of divisibility (`dvd_trans`) gives d ∣ (q^k - 1).

    lines 11–14

    uses Subgroup.card_subgroup_dvd_card, Nat.card_units, Nat.card_eq_fintype_card, dvd_trans

      have hH_dvd : Nat.card H ∣ Nat.card Lˣ := Subgroup.card_subgroup_dvd_card H
      rw [Nat.card_units, hL_card] at hH_dvd
      rw [Nat.card_eq_fintype_card, hH_card] at hH_dvd
      have hd_dvd : d ∣ q ^ k - 1 := dvd_trans hdn hH_dvd
  4. There exists an integer m such that q^k = d * m + 1 in ℕ.

    Since F is a field, its cardinality q is strictly positive by `Fintype.card_pos`, which implies q^k > 0 by `pow_pos`. From d ∣ (q^k - 1), we obtain an integer m such that q^k - 1 = d * m. Since q^k > 0, linear arithmetic over ℕ shows q^k = d * m + 1.

    lines 15–20

    uses Fintype.card_pos, pow_pos

      have hq_pos : 0 < q := by
        have : 0 < Fintype.card F := Fintype.card_pos
        omega
      have hqk_pos : 0 < q ^ k := pow_pos hq_pos k
      obtain ⟨m, hm⟩ := hd_dvd
      have h : q ^ k = d * m + 1 := by omega
  5. In ZMod d, q^k = 1.

    Casting the equality q^k = d * m + 1 to ZMod d, the multiple of d reduces to 0, which leaves q^k = 1.

    lines 21–24

      have h' : ((q ^ k : ℕ) : ZMod d) = ((d * m + 1 : ℕ) : ZMod d) := by rw [h]
      push_cast at h'
      simp at h'
      exact h'
Module.finite_of_finrank_pos
A module with strictly positive finite rank is finitely generated (finite-dimensional).
Module.finite_of_finite
A finitely generated module over a finite ring is finite.
nonempty_fintype
Any finite type can be noncomputably equipped with a `Fintype` instance.
Nat.card_eq_fintype_card
For a type equipped with a `Fintype` instance, its generic cardinality `Nat.card` equals `Fintype.card`.
Module.card_eq_pow_finrank
The cardinality of a finite-dimensional vector space over a finite division ring is the base field's cardinality raised to the dimension.
Subgroup.card_subgroup_dvd_card
Lagrange's theorem: the order of a subgroup divides the order of the ambient group.
Nat.card_units
In a group with zero (such as a field), the number of units is the total cardinality minus one.
dvd_trans
Divisibility is transitive: if a divides b and b divides c, then a divides c.
Fintype.card_pos
A nonempty finite type has strictly positive cardinality.
pow_pos
Any power of a strictly positive element is strictly positive.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- In a degree-k extension L/F of a size-q field, any divisor d of the order of a subgroup of Lˣ satisfies q^k = 1 in ZMod d. -/theorem subgroup_units_pow_card_dvd {F L : Type*} [Field F] [Fintype F] [Field L] [Algebra F L] (q n k : ℕ) (H : Subgroup Lˣ) [Fintype H] (hH_card : Fintype.card H = n) (hq : Fintype.card F = q) (hdim : Module.finrank F L = k) (hk : 2 ≤ k) (d : ℕ) (hdn : d ∣ n) (hd : 1 < d) : (q : ZMod d) ^ k = 1 := by  have _ := hd  have : Module.Finite F L := by    have : 0 < Module.finrank F L := by omega    exact Module.finite_of_finrank_pos this  have : Finite L := Module.finite_of_finite F  have hL_card : Nat.card L = q ^ k := by    cases nonempty_fintype L    rw [Nat.card_eq_fintype_card, Module.card_eq_pow_finrank (K := F) (V := L), hq, hdim]  have hH_dvd : Nat.card H ∣ Nat.card Lˣ := Subgroup.card_subgroup_dvd_card H  rw [Nat.card_units, hL_card] at hH_dvd  rw [Nat.card_eq_fintype_card, hH_card] at hH_dvd  have hd_dvd : d ∣ q ^ k - 1 := dvd_trans hdn hH_dvd  have hq_pos : 0 < q := by    have : 0 < Fintype.card F := Fintype.card_pos    omega  have hqk_pos : 0 < q ^ k := pow_pos hq_pos k  obtain ⟨m, hm⟩ := hd_dvd  have h : q ^ k = d * m + 1 := by omega  have h' : ((q ^ k : ℕ) : ZMod d) = ((d * m + 1 : ℕ) : ZMod d) := by rw [h]  push_cast at h'  simp at h'  exact h'
See it in the graphDiscuss this resultChallenge it