order_rigidity_arithmetic_consequences
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.
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.
uses
Nat.strong_induction_on,Nat.eq_zero_or_pos,Nat.eq_or_lt_of_le,Nat.one_le_iff_ne_zero.mprlemma 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
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.
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
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.
/-- 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
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.
uses
ZMod.orderOf_dvd_card_sub_onehave 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
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.
uses
Nat.exists_prime_and_dvd,Nat.one_le_iff_ne_zero.mprobtain ⟨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
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.
uses
Nat.not_even_iff_odd,even_iff_two_dvd.mp,Nat.prime_tworefine ⟨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
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.
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
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).
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
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.
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.
- In Lean, subtraction on ℕ truncates at zero: 0 - 1 = 0 and 1 - 1 = 0. The base cases N = 0 and N = 1 of the auxiliary lemma rely on this convention.
- To apply Fermat's Little Theorem (ZMod.orderOf_dvd_card_sub_one) to an element q mod l, Lean requires proving that q mod l ≠ 0, which is deduced from the order assumption since orderOf 0 = 0.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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