AFTD Auto-Formalizing Theoretical Domains

order_rigidity_arithmetic_consequences

theoremverifiedformalization

If 2 <= k <= n - 2 and ord_d(q) = k for every divisor d > 1 of n, then every prime l dividing n satisfies ord_l(q) = k and k | (l - 1), n is odd, gcd(n, q-1) = gcd(n, k) = 1, and n = mk + 1 for some integer m >= 2.

Statement

theorem order_rigidity_arithmetic_consequences (q n k : ℕ) (hk : 2 ≤ k) (hkn : k ≤ n - 2) (hord : ∀ d : ℕ, d ∣ n → 1 < d → orderOf (q : ZMod d) = k) : (∀ l : ℕ, Nat.Prime l → l ∣ n → orderOf (q : ZMod l) = k ∧ k ∣ l - 1) ∧ Odd n ∧ Nat.gcd n (q - 1) = 1 ∧ Nat.gcd n k = 1 ∧ ∃ m ≥ 2, n = m * k + 1
Formalizes
arXiv:2610.28047 Theorem 3.1
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • cyclic_mds_subgroup_rigidityTheorem 3.1 of arXiv:2610.28047: Let F be a finite field of cardinality q and L a field extension of F of degree k. Let H be a cyclic…

Read back from the Lean

For all natural numbers $q$, $n$, and $k$, assuming that: 1. $2 \le k$, 2. $k \le n - 2$, and 3. for every natural divisor $d$ of $n$ satisfying $d > 1$, the multiplicative order of $(q \pmod d)$ in $\mathbb{Z}/d\mathbb{Z}$ is equal to $k$, it holds that: 1. For every prime number $l$ dividing $n$, the multiplicative order of $(q \pmod l)$ in $\mathbb{Z}/l\mathbb{Z}$ is $k$, and $k$ divides $l - 1$; 2. $n$ is odd; 3. $\gcd(n, q - 1) = 1$; 4. $\gcd(n, k) = 1$; and 5. There exists a natural number $m \ge 2$ such that $n = m \cdot k + 1$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem establishes five arithmetic consequences of the divisor order rigidity condition that ord_d(q) = k for every divisor d > 1 of n. By Fermat's Little Theorem, every prime factor l of n satisfies k | (l - 1), which immediately rules out l = 2 since k ≥ 2, forcing n to be odd. A non-trivial common divisor with q - 1 would make q ≡ 1 and force k = 1, while a prime factor dividing both n and k would divide p - 1 and hence 1, both contradicting k ≥ 2. Finally, a strong induction shows that if k divides p - 1 for all prime factors, it divides n - 1, yielding n = mk + 1 with m ≥ 2 via the bound k ≤ n - 2.

  1. For N = 0 and N = 1, the condition that k divides p - 1 for all prime factors p of N vacuously implies k divides N - 1.

    We proceed by strong induction on N and split on whether N = 0 or N > 0, and then whether N = 1 or N > 1. When N = 0 or N = 1, truncated natural subtraction gives N - 1 = 0, and k divides 0 vacuously.

    lines 1–10

    uses Nat.strong_induction_on, Nat.eq_zero_or_pos, Nat.eq_or_lt_of_le, Nat.one_le_iff_ne_zero.mpr

    lemma order_rigidity_arithmetic_consequences.k_dvd_sub_one_of_forall_prime_dvd (k : ℕ) :
        ∀ N : ℕ, (∀ p, Nat.Prime p → p ∣ N → k ∣ p - 1) → k ∣ N - 1 := by
      intro N
      induction N using Nat.strong_induction_on with
      | _ N ih =>
        intro h
        rcases Nat.eq_zero_or_pos N with h0 | hpos
        · subst h0; simp
        rcases Nat.eq_or_lt_of_le (Nat.one_le_iff_ne_zero.mpr hpos.ne') with h1 | hgt
        · rw [← h1]; simp
  2. If every prime factor p of N satisfies k divides p - 1, then k divides N - 1.

    For N > 1, there is a prime factor p dividing N. The quotient N / p is strictly smaller than N, so the induction hypothesis gives N / p ≡ 1 (mod k). Since p is also a prime factor of N, p ≡ 1 (mod k). Multiplying these congruences yields (N / p) * p ≡ 1 (mod k). Because p divides N, the product (N / p) * p equals N, so N ≡ 1 (mod k), which means k divides N - 1.

    lines 11–25

    uses Nat.exists_prime_and_dvd, Nat.le_of_dvd, Nat.div_pos, Nat.div_lt_self, Nat.div_dvd_of_dvd, dvd_trans, Nat.modEq_iff_dvd', Nat.mul_pos, Nat.div_mul_cancel

        · obtain ⟨p, hp, hpdvd⟩ := Nat.exists_prime_and_dvd hgt.ne'
          have hpn : p ≤ N := Nat.le_of_dvd hpos hpdvd
          have hm1 : 1 ≤ N / p := Nat.div_pos hpn hp.pos
          have hmlt : N / p < N := Nat.div_lt_self hpos hp.one_lt
          have hmdvd : N / p ∣ N := Nat.div_dvd_of_dvd hpdvd
          have hk1 : k ∣ N / p - 1 := ih (N / p) hmlt (fun r hr hrd => h r hr (dvd_trans hrd hmdvd))
          have hk2 : k ∣ p - 1 := h p hp hpdvd
          have ha : 1 ≡ N / p [MOD k] := (Nat.modEq_iff_dvd' hm1).mpr hk1
          have hb : 1 ≡ p [MOD k] := (Nat.modEq_iff_dvd' hp.one_lt.le).mpr hk2
          have hab : 1 ≡ N / p * p [MOD k] := by simpa using ha.mul hb
          have hprod : 1 ≤ N / p * p := by
            have := Nat.mul_pos (by omega : 0 < N / p) hp.pos
            omega
          have hres : k ∣ N / p * p - 1 := (Nat.modEq_iff_dvd' hprod).mp hab
          rwa [Nat.div_mul_cancel hpdvd] at hres
  3. n ≥ 4, n > 1, and n > 0.

    The inequalities 2 ≤ k and k ≤ n - 2 directly imply n ≥ k + 2 ≥ 4 via linear integer arithmetic, from which n > 1 and n > 0 follow.

    lines 26–31

    /-- Arithmetic consequences of the divisor order rigidity condition. -/
    theorem order_rigidity_arithmetic_consequences (q n k : ℕ) (hk : 2 ≤ k) (hkn : k ≤ n - 2) (hord : ∀ d : ℕ, d ∣ n → 1 < d → orderOf (q : ZMod d) = k) : (∀ l : ℕ, Nat.Prime l → l ∣ n → orderOf (q : ZMod l) = k ∧ k ∣ l - 1) ∧ Odd n ∧ Nat.gcd n (q - 1) = 1 ∧ Nat.gcd n k = 1 ∧ ∃ m ≥ 2, n = m * k + 1 := by
      have hn4 : 4 ≤ n := by omega
      have hn1 : 1 < n := by omega
      have hnpos : 0 < n := by omega
  4. Every prime factor l of n satisfies ord_l(q) = k and k divides l - 1.

    Since l is prime and divides n, l > 1, so the divisor rigidity hypothesis gives ord_l(q) = k. If q ≡ 0 (mod l), its order would be 0, contradicting k ≥ 2; hence q mod l ≠ 0. In the field ℤ/lℤ, the order of any nonzero element divides the order of the multiplicative group, which is l - 1. Since the order is k, k divides l - 1.

    lines 32–43

    uses ZMod.orderOf_dvd_card_sub_one

      have hprime : ∀ l : ℕ, Nat.Prime l → l ∣ n → orderOf (q : ZMod l) = k ∧ k ∣ l - 1 := by
        intro l hl hldvd
        have hordl : orderOf (q : ZMod l) = k := hord l hldvd hl.one_lt
        refine ⟨hordl, ?_⟩
        have : Fact l.Prime := ⟨hl⟩
        have hne : (q : ZMod l) ≠ 0 := by
          intro hzero
          rw [hzero] at hordl
          simp at hordl
          omega
        have hdvd := ZMod.orderOf_dvd_card_sub_one hne
        rwa [hordl] at hdvd
  5. q ≠ 0 and therefore 1 ≤ q.

    Since n > 1, n has a prime factor p₀. If q were 0, its order modulo p₀ would be 0, contradicting ord_{p₀}(q) = k ≥ 2. Hence q ≠ 0, which means 1 ≤ q.

    lines 44–52

    uses Nat.exists_prime_and_dvd, Nat.one_le_iff_ne_zero.mpr

      obtain ⟨p0, hp0, hp0dvd⟩ := Nat.exists_prime_and_dvd (by omega : n ≠ 1)
      have hq0 : q ≠ 0 := by
        have : Fact p0.Prime := ⟨hp0⟩
        intro hq
        have h := (hprime p0 hp0 hp0dvd).1
        rw [hq] at h
        simp at h
        omega
      have hq1 : 1 ≤ q := Nat.one_le_iff_ne_zero.mpr hq0
  6. n is odd.

    We provide the prime divisor property and split the remaining goals. If n were even, 2 would divide n. But then k would divide 2 - 1 = 1, forcing k = 1, which contradicts k ≥ 2. Therefore n is odd.

    lines 53–59

    uses Nat.not_even_iff_odd, even_iff_two_dvd.mp, Nat.prime_two

      refine ⟨hprime, ?_, ?_, ?_, ?_⟩
      · rw [← Nat.not_even_iff_odd]
        intro heven
        have h2 : 2 ∣ n := even_iff_two_dvd.mp heven
        have hkk := (hprime 2 Nat.prime_two h2).2
        simp at hkk
        omega
  7. gcd(n, q - 1) = 1.

    Suppose for contradiction that gcd(n, q - 1) ≠ 1. Because n > 0, the gcd is strictly greater than 1, so it has a prime factor p. Then p divides n, which gives ord_p(q) = k, and p divides q - 1, which means q ≡ 1 (mod p). But the order of 1 is 1, forcing k = 1, contradicting k ≥ 2.

    lines 60–77

    uses Nat.gcd_pos_of_pos_left, Nat.exists_prime_and_dvd, dvd_trans, Nat.gcd_dvd_left, Nat.gcd_dvd_right, CharP.cast_eq_zero_iff, Nat.cast_sub, Nat.cast_one, zero_add, orderOf_one

      · by_contra hg
        have hgt : 1 < Nat.gcd n (q - 1) := by
          have h1 : 0 < Nat.gcd n (q - 1) := Nat.gcd_pos_of_pos_left (q - 1) hnpos
          omega
        obtain ⟨p, hp, hpdvd⟩ := Nat.exists_prime_and_dvd hgt.ne'
        have hpn : p ∣ n := dvd_trans hpdvd (Nat.gcd_dvd_left n (q - 1))
        have hpq : p ∣ q - 1 := dvd_trans hpdvd (Nat.gcd_dvd_right n (q - 1))
        have hordp : orderOf (q : ZMod p) = k := (hprime p hp hpn).1
        have : Fact p.Prime := ⟨hp⟩
        have hqmod : (q : ZMod p) = 1 := by
          have hzero : ((q - 1 : ℕ) : ZMod p) = 0 := by
            rw [CharP.cast_eq_zero_iff (ZMod p) p]
            exact hpq
          calc (q : ZMod p) = ((q - 1 : ℕ) : ZMod p) + 1 := by
                  rw [Nat.cast_sub hq1, Nat.cast_one]; ring
            _ = 1 := by rw [hzero, zero_add]
        rw [hqmod, orderOf_one] at hordp
        omega
  8. gcd(n, k) = 1.

    Suppose for contradiction that gcd(n, k) ≠ 1. Because n > 0, the gcd exceeds 1 and has a prime factor p. Then p divides n, so k divides p - 1. Since p also divides k, by transitivity p divides p - 1. Thus p divides p - (p - 1) = 1, which implies p = 1, contradicting that p is prime (p ≥ 2).

    lines 78–92

    uses Nat.gcd_pos_of_pos_left, Nat.exists_prime_and_dvd, dvd_trans, Nat.gcd_dvd_left, Nat.gcd_dvd_right, Nat.dvd_sub, dvd_refl, Nat.sub_sub_self, Nat.dvd_one

      · by_contra hg
        have hgt : 1 < Nat.gcd n k := by
          have h1 : 0 < Nat.gcd n k := Nat.gcd_pos_of_pos_left k hnpos
          omega
        obtain ⟨p, hp, hpdvd⟩ := Nat.exists_prime_and_dvd hgt.ne'
        have hp2 : 2 ≤ p := hp.two_le
        have hpn : p ∣ n := dvd_trans hpdvd (Nat.gcd_dvd_left n k)
        have hpk : p ∣ k := dvd_trans hpdvd (Nat.gcd_dvd_right n k)
        have hkp : k ∣ p - 1 := (hprime p hp hpn).2
        have hpp : p ∣ p - 1 := dvd_trans hpk hkp
        have h1 : p ∣ 1 := by
          have h := Nat.dvd_sub (dvd_refl p) hpp
          rwa [Nat.sub_sub_self hp.one_le] at h
        rw [Nat.dvd_one] at h1
        omega
  9. There exists an integer m ≥ 2 such that n = mk + 1.

    Because k divides p - 1 for every prime factor p of n, the auxiliary induction lemma implies k divides n - 1, so n - 1 = mk for some integer m. Using k ≤ n - 2, we have k * 1 = k < n - 1 = k * m, so cancelling k > 0 gives m > 1, meaning m ≥ 2. Finally, n = mk + 1 follows by adding 1.

    lines 93–103

    uses order_rigidity_arithmetic_consequences.k_dvd_sub_one_of_forall_prime_dvd, Nat.mul_comm, mul_one, Nat.lt_of_mul_lt_mul_left

      · have hkdiv : k ∣ n - 1 :=
          order_rigidity_arithmetic_consequences.k_dvd_sub_one_of_forall_prime_dvd k n (fun p hp hpd => (hprime p hp hpd).2)
        obtain ⟨m, hm⟩ := hkdiv
        have hm' : n - 1 = m * k := by rw [hm, Nat.mul_comm]
        refine ⟨m, ?_, ?_⟩
        · have hkey : k * 1 < k * m := by
            rw [mul_one, Nat.mul_comm k m, ← hm']
            omega
          have := Nat.lt_of_mul_lt_mul_left hkey
          omega
        · omega
order_rigidity_arithmetic_consequences.k_dvd_sub_one_of_forall_prime_dvd
If k divides p - 1 for every prime factor p of N, then k divides N - 1.
Nat.strong_induction_on
The principle of strong induction: to prove a property for all natural numbers, it suffices to prove it for n assuming it holds for all strictly smaller values.
Nat.eq_zero_or_pos
Every natural number is either zero or strictly positive.
Nat.eq_or_lt_of_le
If a ≤ b for natural numbers, then either a = b or a < b.
Nat.one_le_iff_ne_zero.mpr
A nonzero natural number is at least 1.
Nat.exists_prime_and_dvd
Every natural number other than 1 has at least one prime divisor.
Nat.le_of_dvd
A divisor of a strictly positive natural number is less than or equal to that number.
Nat.div_pos
If 0 < b ≤ a, then the quotient a / b is strictly positive.
Nat.div_lt_self
Dividing a positive natural number by an integer greater than 1 yields a strictly smaller quotient.
Nat.div_dvd_of_dvd
If d divides n, then the quotient n / d also divides n.
dvd_trans
Divisibility is transitive: if a divides b and b divides c, then a divides c.
Nat.modEq_iff_dvd'
For natural numbers with a ≤ b, a ≡ b (mod n) if and only if n divides b - a.
Nat.mul_pos
The product of two strictly positive natural numbers is strictly positive.
Nat.div_mul_cancel
If d divides n, then (n / d) * d = n.
ZMod.orderOf_dvd_card_sub_one
In the finite field ℤ/pℤ for prime p, the multiplicative order of any nonzero element divides p - 1.
Nat.not_even_iff_odd
A natural number is odd if and only if it is not even.
even_iff_two_dvd.mp
If a natural number is even, then it is divisible by 2.
Nat.prime_two
The number 2 is prime.
Nat.gcd_pos_of_pos_left
The greatest common divisor gcd(m, n) is positive whenever m > 0.
Nat.gcd_dvd_left
The greatest common divisor gcd(m, n) divides m.
Nat.gcd_dvd_right
The greatest common divisor gcd(m, n) divides n.
CharP.cast_eq_zero_iff
In a ring of characteristic p, the cast of a natural number x is zero if and only if p divides x.
Nat.cast_sub
The cast of a difference n - m (with m ≤ n) into an additive group with one equals the difference of the casts.
Nat.cast_one
The cast of the natural number 1 into a semiring is 1.
zero_add
Adding zero on the left leaves an element unchanged: 0 + a = a.
orderOf_one
The order of the identity element in any monoid is 1.
Nat.dvd_sub
If k divides m and k divides n, then k divides their difference m - n.
dvd_refl
Divisibility is reflexive: any element divides itself.
Nat.sub_sub_self
For natural numbers with m ≤ n, n - (n - m) = m.
Nat.dvd_one
The only natural number that divides 1 is 1.
Nat.mul_comm
Multiplication of natural numbers is commutative: n * m = m * n.
mul_one
Multiplying by 1 on the right leaves an element unchanged: a * 1 = a.
Nat.lt_of_mul_lt_mul_left
If a * b < a * c for natural numbers, then b < c.

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

lemma order_rigidity_arithmetic_consequences.k_dvd_sub_one_of_forall_prime_dvd (k : ℕ) :    ∀ N : ℕ, (∀ p, Nat.Prime p → p ∣ N → k ∣ p - 1) → k ∣ N - 1 := by  intro N  induction N using Nat.strong_induction_on with  | _ N ih =>    intro h    rcases Nat.eq_zero_or_pos N with h0 | hpos    · subst h0; simp    rcases Nat.eq_or_lt_of_le (Nat.one_le_iff_ne_zero.mpr hpos.ne') with h1 | hgt    · rw [← h1]; simp    · obtain ⟨p, hp, hpdvd⟩ := Nat.exists_prime_and_dvd hgt.ne'      have hpn : p ≤ N := Nat.le_of_dvd hpos hpdvd      have hm1 : 1 ≤ N / p := Nat.div_pos hpn hp.pos      have hmlt : N / p < N := Nat.div_lt_self hpos hp.one_lt      have hmdvd : N / p ∣ N := Nat.div_dvd_of_dvd hpdvd      have hk1 : k ∣ N / p - 1 := ih (N / p) hmlt (fun r hr hrd => h r hr (dvd_trans hrd hmdvd))      have hk2 : k ∣ p - 1 := h p hp hpdvd      have ha : 1 ≡ N / p [MOD k] := (Nat.modEq_iff_dvd' hm1).mpr hk1      have hb : 1 ≡ p [MOD k] := (Nat.modEq_iff_dvd' hp.one_lt.le).mpr hk2      have hab : 1 ≡ N / p * p [MOD k] := by simpa using ha.mul hb      have hprod : 1 ≤ N / p * p := by        have := Nat.mul_pos (by omega : 0 < N / p) hp.pos        omega      have hres : k ∣ N / p * p - 1 := (Nat.modEq_iff_dvd' hprod).mp hab      rwa [Nat.div_mul_cancel hpdvd] at hres/-- Arithmetic consequences of the divisor order rigidity condition. -/theorem order_rigidity_arithmetic_consequences (q n k : ℕ) (hk : 2 ≤ k) (hkn : k ≤ n - 2) (hord : ∀ d : ℕ, d ∣ n → 1 < d → orderOf (q : ZMod d) = k) : (∀ l : ℕ, Nat.Prime l → l ∣ n → orderOf (q : ZMod l) = k ∧ k ∣ l - 1) ∧ Odd n ∧ Nat.gcd n (q - 1) = 1 ∧ Nat.gcd n k = 1 ∧ ∃ m ≥ 2, n = m * k + 1 := by  have hn4 : 4 ≤ n := by omega  have hn1 : 1 < n := by omega  have hnpos : 0 < n := by omega  have hprime : ∀ l : ℕ, Nat.Prime l → l ∣ n → orderOf (q : ZMod l) = k ∧ k ∣ l - 1 := by    intro l hl hldvd    have hordl : orderOf (q : ZMod l) = k := hord l hldvd hl.one_lt    refine ⟨hordl, ?_⟩    have : Fact l.Prime := ⟨hl⟩    have hne : (q : ZMod l) ≠ 0 := by      intro hzero      rw [hzero] at hordl      simp at hordl      omega    have hdvd := ZMod.orderOf_dvd_card_sub_one hne    rwa [hordl] at hdvd  obtain ⟨p0, hp0, hp0dvd⟩ := Nat.exists_prime_and_dvd (by omega : n ≠ 1)  have hq0 : q ≠ 0 := by    have : Fact p0.Prime := ⟨hp0⟩    intro hq    have h := (hprime p0 hp0 hp0dvd).1    rw [hq] at h    simp at h    omega  have hq1 : 1 ≤ q := Nat.one_le_iff_ne_zero.mpr hq0  refine ⟨hprime, ?_, ?_, ?_, ?_⟩  · rw [← Nat.not_even_iff_odd]    intro heven    have h2 : 2 ∣ n := even_iff_two_dvd.mp heven    have hkk := (hprime 2 Nat.prime_two h2).2    simp at hkk    omega  · by_contra hg    have hgt : 1 < Nat.gcd n (q - 1) := by      have h1 : 0 < Nat.gcd n (q - 1) := Nat.gcd_pos_of_pos_left (q - 1) hnpos      omega    obtain ⟨p, hp, hpdvd⟩ := Nat.exists_prime_and_dvd hgt.ne'    have hpn : p ∣ n := dvd_trans hpdvd (Nat.gcd_dvd_left n (q - 1))    have hpq : p ∣ q - 1 := dvd_trans hpdvd (Nat.gcd_dvd_right n (q - 1))    have hordp : orderOf (q : ZMod p) = k := (hprime p hp hpn).1    have : Fact p.Prime := ⟨hp⟩    have hqmod : (q : ZMod p) = 1 := by      have hzero : ((q - 1 : ℕ) : ZMod p) = 0 := by        rw [CharP.cast_eq_zero_iff (ZMod p) p]        exact hpq      calc (q : ZMod p) = ((q - 1 : ℕ) : ZMod p) + 1 := by              rw [Nat.cast_sub hq1, Nat.cast_one]; ring        _ = 1 := by rw [hzero, zero_add]    rw [hqmod, orderOf_one] at hordp    omega  · by_contra hg    have hgt : 1 < Nat.gcd n k := by      have h1 : 0 < Nat.gcd n k := Nat.gcd_pos_of_pos_left k hnpos      omega    obtain ⟨p, hp, hpdvd⟩ := Nat.exists_prime_and_dvd hgt.ne'    have hp2 : 2 ≤ p := hp.two_le    have hpn : p ∣ n := dvd_trans hpdvd (Nat.gcd_dvd_left n k)    have hpk : p ∣ k := dvd_trans hpdvd (Nat.gcd_dvd_right n k)    have hkp : k ∣ p - 1 := (hprime p hp hpn).2    have hpp : p ∣ p - 1 := dvd_trans hpk hkp    have h1 : p ∣ 1 := by      have h := Nat.dvd_sub (dvd_refl p) hpp      rwa [Nat.sub_sub_self hp.one_le] at h    rw [Nat.dvd_one] at h1    omega  · have hkdiv : k ∣ n - 1 :=      order_rigidity_arithmetic_consequences.k_dvd_sub_one_of_forall_prime_dvd k n (fun p hp hpd => (hprime p hp hpd).2)    obtain ⟨m, hm⟩ := hkdiv    have hm' : n - 1 = m * k := by rw [hm, Nat.mul_comm]    refine ⟨m, ?_, ?_⟩    · have hkey : k * 1 < k * m := by        rw [mul_one, Nat.mul_comm k m, ← hm']        omega      have := Nat.lt_of_mul_lt_mul_left hkey      omega    · omega
See it in the graphDiscuss this resultChallenge it