AFTD Auto-Formalizing Theoretical Domains

consecutive_sum_ne_mul_prime_of_two_mul_lt

theoremverifiedoriginal

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
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.

  1. 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.

    lines 4–5

    uses Nat.exists_eq_add_of_le

      intro hS
      obtain ⟨m, rfl⟩ := Nat.exists_eq_add_of_le hij
  2. 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).

    lines 6–15

    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
  3. 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.

    lines 16–22

    uses Finset.sum_le_card_nsmul, le_trans, Nat.card_Icc, smul_eq_mul

      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
  4. 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.

    lines 23–27

    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))
  5. 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.

    lines 28–45

    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
  6. 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`).

    lines 46–49

    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.

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

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
See it in the graphDiscuss this resultChallenge it