consecutive_sum_ne_mul_prime_of_two_mul_lt
If p is a prime with p > 2n and a ≥ 1, then a·p is not a sum of one or more consecutive integers from {1, …, n}.
Statement
theorem consecutive_sum_ne_mul_prime_of_two_mul_lt (n a p i j : ℕ) (hp : p.Prime)
(hpn : 2 * n < p) (ha : 0 < a) (hi : 1 ≤ i) (hij : i ≤ j) (hjn : j ≤ n) :
∑ x ∈ Finset.Icc i j, x ≠ a * p- Related work
- arXiv:2610.08889 (Consecutive Cycle Sums), Lemma 2, which assumes in addition 2an − T_{2a−1} < ap; that hypothesis is not needed: divisibility forces a run of k consecutive integers with sum ap to have k ≤ 2a, and such a run sums to at most 2an < ap. Serves Theorem 1 (not_cycle_labeling_complete_range_of_ge_eight).
- Verified
- 09 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- Used by 1
- consecutive_sum_ne_mul_primeLet a ≥ 1 and p a prime with p > 2n and 2an − T_{2a−1} < ap, where T_m = m(m+1)/2. Then a·p is not a sum of consecutive integers from {1,…
The proof, explained
Suppose for contradiction that the sum of k = m + 1 consecutive integers starting at i ≤ n equals a · p. By the formula for the sum of an arithmetic progression, 2ap = k(2i + k - 1), and bounding each term by n yields ap ≤ kn. Because p > 2n ≥ k, the prime p cannot divide k, which forces either k (if odd) or k/2 (if even) to divide a, implying k ≤ 2a. But then ap ≤ kn ≤ 2an < ap (since 2n < p), an impossibility.
Assume for contradiction that the sum equals a · p, and express the upper limit as j = i + m.
We assume for contradiction that ∑ x ∈ Finset.Icc i j, x = a · p. Since i ≤ j, by `Nat.exists_eq_add_of_le` we can write j = i + m for some m ∈ ℕ, so the interval consists of m + 1 consecutive terms starting at i.
uses
Nat.exists_eq_add_of_leintro hS obtain ⟨m, rfl⟩ := Nat.exists_eq_add_of_le hij
The sum identity 2 · (a · p) = (m + 1) · (2 · i + m) holds.
By induction on m, we establish the general arithmetic progression sum identity 2 · ∑ x ∈ Finset.Icc i (i + m), x = (m + 1) · (2 · i + m). The base case m = 0 reduces to 2 · i = 1 · 2 · i. For the successor step, `Finset.sum_Icc_succ_top` extracts the top term i + m + 1, and distributivity (`mul_add`) together with the induction hypothesis completes the step via ring arithmetic. Substituting the assumed sum a · p yields 2 · (a · p) = (m + 1) · (2 · i + m).
uses
Finset.sum_Icc_succ_top,mul_add-- `2 S = k (2i + k - 1)` with `k = m + 1` terms have hsum : ∀ m : ℕ, 2 * ∑ x ∈ Finset.Icc i (i + m), x = (m + 1) * (2 * i + m) := by intro m induction m with | zero => simp | succ m ih => rw [show i + (m + 1) = (i + m) + 1 by ring, Finset.sum_Icc_succ_top (by omega), mul_add, ih] ring have h2 := hsum m rw [hS] at h2
The sum is at most (m + 1) · n, and the number of terms satisfies m + 1 ≤ n.
Each element in the interval [i, i + m] is at most j ≤ n. By `Finset.sum_le_card_nsmul`, the sum is at most the cardinality of the interval times n. The cardinality formula `Nat.card_Icc` gives (i + m + 1) - i = m + 1, so the sum is at most (m + 1) · n; replacing the sum by a · p gives a · p ≤ (m + 1) · n. Moreover, because 1 ≤ i and i + m ≤ n, linear arithmetic yields m + 1 ≤ n.
uses
Finset.sum_le_card_nsmul,le_trans,Nat.card_Icc,smul_eq_mulhave hsize : ∑ x ∈ Finset.Icc i (i + m), x ≤ (m + 1) * n := by have := Finset.sum_le_card_nsmul (Finset.Icc i (i + m)) (fun x => x) n (fun x hx => le_trans (Finset.mem_Icc.1 hx).2 hjn) rw [Nat.card_Icc, smul_eq_mul] at this rwa [show i + m + 1 - i = m + 1 by omega] at this rw [hS] at hsize have hkn : m + 1 ≤ n := by omega
Any positive integer t ≤ n is coprime to p.
If p divided such an integer t, then by `Nat.le_of_dvd` we would have p ≤ t ≤ n, contradicting 2 · n < p. Because p is prime, not dividing t implies p and t are coprime (`Nat.Prime.coprime_iff_not_dvd`), and symmetry (`Nat.Coprime.symm`) gives that t is coprime to p.
uses
Nat.Coprime.symm,Nat.Prime.coprime_iff_not_dvd,Nat.le_of_dvd-- a positive number below `p` is coprime to `p` have hcop : ∀ t, 0 < t → t ≤ n → Nat.Coprime t p := by intro t ht htn exact Nat.Coprime.symm ((Nat.Prime.coprime_iff_not_dvd hp).2 fun h => absurd (Nat.le_of_dvd ht h) (by omega))
The number of terms satisfies m + 1 ≤ 2 · a.
We split into cases based on the parity of m + 1 using `Nat.even_or_odd`: - If m + 1 is even, say m + 1 = 2 · t, then 2 · (a · p) = 2 · (t · (2 · i + m)) implies a · p = t · (2 · i + m). Since 0 < t ≤ n, t is coprime to p, so t divides a. Since a > 0, `Nat.le_of_dvd` gives t ≤ a, which implies m + 1 = 2 · t ≤ 2 · a. - If m + 1 is odd, then m + 1 divides 2 · (a · p). Since 2 is prime (`Nat.prime_two`) and m + 1 is odd, m + 1 is coprime to 2, so m + 1 divides a · p. Since 0 < m + 1 ≤ n, m + 1 is coprime to p, hence m + 1 divides a. By `Nat.le_of_dvd`, m + 1 ≤ a ≤ 2 · a. In both cases, m + 1 ≤ 2 · a.
uses
Nat.even_or_odd,Nat.Coprime.symm,Nat.Prime.coprime_iff_not_dvd,Nat.prime_two,Nat.le_of_dvd-- the number of terms is at most `2a` have hk : m + 1 ≤ 2 * a := by rcases Nat.even_or_odd (m + 1) with ⟨t, ht⟩ | hodd · have hS' : a * p = t * (2 * i + m) := by have : 2 * (a * p) = 2 * (t * (2 * i + m)) := by rw [h2, ht]; ring omega have ht0 : 0 < t := by omega have htd : t ∣ a := (hcop t ht0 (by omega)).dvd_of_dvd_mul_right ⟨_, hS'⟩ have := Nat.le_of_dvd ha htd omega · have hdvd : m + 1 ∣ 2 * (a * p) := ⟨2 * i + m, h2⟩ have hc2 : Nat.Coprime (m + 1) 2 := Nat.Coprime.symm ((Nat.Prime.coprime_iff_not_dvd Nat.prime_two).2 (Nat.odd_iff.1 hodd ▸ by omega)) have h1 : m + 1 ∣ a * p := hc2.dvd_of_dvd_mul_left hdvd have h3 : m + 1 ∣ a := (hcop (m + 1) (by omega) hkn).dvd_of_dvd_mul_right h1 have := Nat.le_of_dvd ha h3 omega
Contradiction: (m + 1) · n ≤ 2 · a · n < a · p ≤ (m + 1) · n.
Multiplying m + 1 ≤ 2 · a by n gives (m + 1) · n ≤ 2 · a · n (`Nat.mul_le_mul_right`). Since 2 · n < p and a > 0, we have 2 · a · n < a · p (`nlinarith`). Combining this with a · p ≤ (m + 1) · n gives a · p < a · p, a contradiction closed by linear arithmetic (`omega`).
uses
Nat.mul_le_mul_right-- then the sum is at most `2an < ap` have : (m + 1) * n ≤ 2 * a * n := Nat.mul_le_mul_right n hk have : 2 * a * n < a * p := by nlinarith omega
Nat.exists_eq_add_of_le- If m ≤ n, there exists k such that n = m + k.
Finset.sum_Icc_succ_top- The sum of a function over the integer interval [a, b + 1] equals the sum over [a, b] plus the term at b + 1, provided a ≤ b + 1.
mul_add- Left-distributivity of multiplication over addition: a * (b + c) = a * b + a * c.
Finset.sum_le_card_nsmul- If every element of a finite set s maps to a value bounded by n, the sum over s is bounded by the cardinality of s times n.
le_trans- Inequality on preorders is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Nat.card_Icc- The number of integers in the closed interval [a, b] is b + 1 - a.
smul_eq_mul- Natural number scalar multiplication coincides with standard multiplication: a • b = a * b.
Nat.Coprime.symm- Coprimality is symmetric: if n is coprime to m, then m is coprime to n.
Nat.Prime.coprime_iff_not_dvd- A prime p is coprime to n if and only if p does not divide n.
Nat.le_of_dvd- If m divides a strictly positive natural number n, then m ≤ n.
Nat.even_or_odd- Every natural number is either even or odd.
Nat.prime_two- The natural number 2 is prime.
Nat.mul_le_mul_right- Multiplying an inequality n ≤ m on the right by k preserves the inequality: n * k ≤ m * k.
- The identity for the sum of consecutive integers is verified by induction over ℕ and ring arithmetic rather than division by 2, avoiding rational or real arithmetic.
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.
theorem consecutive_sum_ne_mul_prime_of_two_mul_lt (n a p i j : ℕ) (hp : p.Prime) (hpn : 2 * n < p) (ha : 0 < a) (hi : 1 ≤ i) (hij : i ≤ j) (hjn : j ≤ n) : ∑ x ∈ Finset.Icc i j, x ≠ a * p := by intro hS obtain ⟨m, rfl⟩ := Nat.exists_eq_add_of_le hij -- `2 S = k (2i + k - 1)` with `k = m + 1` terms have hsum : ∀ m : ℕ, 2 * ∑ x ∈ Finset.Icc i (i + m), x = (m + 1) * (2 * i + m) := by intro m induction m with | zero => simp | succ m ih => rw [show i + (m + 1) = (i + m) + 1 by ring, Finset.sum_Icc_succ_top (by omega), mul_add, ih] ring have h2 := hsum m rw [hS] at h2 have hsize : ∑ x ∈ Finset.Icc i (i + m), x ≤ (m + 1) * n := by have := Finset.sum_le_card_nsmul (Finset.Icc i (i + m)) (fun x => x) n (fun x hx => le_trans (Finset.mem_Icc.1 hx).2 hjn) rw [Nat.card_Icc, smul_eq_mul] at this rwa [show i + m + 1 - i = m + 1 by omega] at this rw [hS] at hsize have hkn : m + 1 ≤ n := by omega -- a positive number below `p` is coprime to `p` have hcop : ∀ t, 0 < t → t ≤ n → Nat.Coprime t p := by intro t ht htn exact Nat.Coprime.symm ((Nat.Prime.coprime_iff_not_dvd hp).2 fun h => absurd (Nat.le_of_dvd ht h) (by omega)) -- the number of terms is at most `2a` have hk : m + 1 ≤ 2 * a := by rcases Nat.even_or_odd (m + 1) with ⟨t, ht⟩ | hodd · have hS' : a * p = t * (2 * i + m) := by have : 2 * (a * p) = 2 * (t * (2 * i + m)) := by rw [h2, ht]; ring omega have ht0 : 0 < t := by omega have htd : t ∣ a := (hcop t ht0 (by omega)).dvd_of_dvd_mul_right ⟨_, hS'⟩ have := Nat.le_of_dvd ha htd omega · have hdvd : m + 1 ∣ 2 * (a * p) := ⟨2 * i + m, h2⟩ have hc2 : Nat.Coprime (m + 1) 2 := Nat.Coprime.symm ((Nat.Prime.coprime_iff_not_dvd Nat.prime_two).2 (Nat.odd_iff.1 hodd ▸ by omega)) have h1 : m + 1 ∣ a * p := hc2.dvd_of_dvd_mul_left hdvd have h3 : m + 1 ∣ a := (hcop (m + 1) (by omega) hkn).dvd_of_dvd_mul_right h1 have := Nat.le_of_dvd ha h3 omega -- then the sum is at most `2an < ap` have : (m + 1) * n ≤ 2 * a * n := Nat.mul_le_mul_right n hk have : 2 * a * n < a * p := by nlinarith omega