weakly_consecutive_ends_coprime
theoremverified
In a weakly consecutive sequence, the first and last terms are coprime.
Statement
theorem weakly_consecutive_ends_coprime {k : ℕ} (σ : Equiv.Perm (Fin k)) (hσ : is_weakly_consecutive σ) (hk : 0 < k) : Nat.Coprime ((σ ⟨0, hk⟩ : ℕ) + 1) ((σ ⟨k - 1, by omega⟩ : ℕ) + 1)
- Source
- step towards weakly_consecutive_one_at_end_of_isPrimePow (Weakly Consecutive Sequences (2024), arXiv:2401.09497, Conjecture 5.2, prime-power case)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- is_weakly_consecutiveA permutation s of {1, ..., k} is weakly consecutive if for all positions i, j and every m, whenever m divides s(i) and m divides i - j, m…
- weakly_consecutive_first_dvdIn a weakly consecutive sequence of length k, the first term divides k.
- fin_card_filter_dvdFor m > 0, exactly (k + m - 1)/m of the positions 0, ..., k-1 are multiples of m.
- perm_card_filter_dvd_succFor any permutation s of {0, ..., k-1} and any m, exactly floor(k/m) positions j have m dividing s(j) + 1 (the values s(j) + 1 run over 1,…
- Used by 1
- weakly_consecutive_one_at_end_of_isPrimePowConjecture 5.2 of arXiv:2401.09497 holds when the length k is a prime power: a weakly consecutive sequence of length p^n begins or ends…
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 weakly_consecutive_ends_coprime {k : ℕ} (σ : Equiv.Perm (Fin k)) (hσ : is_weakly_consecutive σ) (hk : 0 < k) : Nat.Coprime ((σ ⟨0, hk⟩ : ℕ) + 1) ((σ ⟨k - 1, by omega⟩ : ℕ) + 1) := by apply Nat.coprime_of_dvd intro p hp ha hb have hp2 := hp.two_le have hpk : p ∣ k := ha.trans (weakly_consecutive_first_dvd σ hσ hk) have hk2 : 2 ≤ k := by rcases Nat.lt_or_ge k 2 with h | h · exfalso have : k = 1 := by omega subst this have h0 : (σ ⟨0, hk⟩ : ℕ) = 0 := by omega rw [h0] at ha exact hp.one_lt.ne' (Nat.dvd_one.1 ha) · exact h -- the class of position 0, plus the last position, all hold multiples of p set last : Fin k := ⟨k - 1, by omega⟩ with hlast have hsub : insert last (Finset.univ.filter fun j : Fin k => p ∣ (j : ℕ)) ⊆ Finset.univ.filter fun j : Fin k => p ∣ (σ j : ℕ) + 1 := by intro j simp only [Finset.mem_insert, Finset.mem_filter, Finset.mem_univ, true_and] rintro (rfl | hj) · exact hb · apply hσ p ⟨0, hk⟩ j ha simp only [Nat.cast_zero, zero_sub] exact (dvd_neg).2 (Int.natCast_dvd_natCast.2 hj) have hnot : last ∉ (Finset.univ.filter fun j : Fin k => p ∣ (j : ℕ)) := by simp only [Finset.mem_filter, Finset.mem_univ, true_and, hlast] intro h have h1 : p ∣ k - (k - 1) := Nat.dvd_sub hpk h have : k - (k - 1) = 1 := by omega rw [this] at h1 exact hp.one_lt.ne' (Nat.dvd_one.1 h1) have hc := Finset.card_le_card hsub rw [Finset.card_insert_of_notMem hnot, fin_card_filter_dvd p k (by omega), perm_card_filter_dvd_succ σ p] at hc have : k / p ≤ (k + p - 1) / p := Nat.div_le_div_right (by omega) omega