four_point_set_coprime_inverse_odd
For any integer n, setting a = 2n - 1 and b = 2n + 1, there exists an odd integer gamma such that (a * gamma) % (2 * b) = 1 % (2 * b). Explicitly, gamma = n if n is odd, and gamma = 3n + 1 if n is even.
Statement
theorem four_point_set_coprime_inverse_odd (n : ℤ) : let a : ℤ := 2 * n - 1 let b : ℤ := 2 * n + 1 ∃ gamma : ℤ, Odd gamma ∧ (a * gamma) % (2 * b) = 1 % (2 * b)
- Source
- step towards four_point_set_quadratic_packing_interval
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof proceeds by case analysis on the parity of n. When n is odd, taking the explicit candidate γ = n provides an odd integer, and algebraic expansion shows that a * γ - 1 is an exact multiple of 2b, namely 2b * k where n = 2k + 1. When n is even, taking γ = 3n + 1 provides an odd candidate whose product with a satisfies a * γ - 1 = 2b * (3k - 1) where n = 2k, confirming the desired congruence modulo 2b in both cases.
It suffices to prove the statement separately when n is odd and when n is even.
We split into two cases based on whether n is odd (Odd n). This reduces the goal to finding an odd modular inverse γ when n is odd and when n is not odd.
by_cases h : Odd nWhen n is odd, the integer γ = n is odd and satisfies (a * γ) % (2 * b) = 1 % (2 * b).
Since n is odd, we can write n = 2k + 1 for some integer k. We take γ = 2k + 1 = n, which is manifestly odd. By Int.emod_eq_emod_iff_emod_sub_eq_zero, the congruence (a * γ) % (2 * b) = 1 % (2 * b) is equivalent to (a * γ - 1) % (2 * b) = 0. By Int.emod_eq_zero_of_dvd, it suffices to show that 2b divides a * γ - 1. Expanding the terms yields (2(2k + 1) - 1)(2k + 1) - 1 = (4k + 1)(2k + 1) - 1 = 8k² + 6k = 2(4k + 3)k = 2b * k, so 2b divides a * γ - 1 with quotient k.
uses
Int.emod_eq_emod_iff_emod_sub_eq_zero,Int.emod_eq_zero_of_dvd· obtain ⟨k, rfl⟩ := h refine ⟨2 * k + 1, ⟨k, by ring⟩, ?_⟩ rw [Int.emod_eq_emod_iff_emod_sub_eq_zero] exact Int.emod_eq_zero_of_dvd ⟨k, by ring⟩
When n is even, the integer γ = 3n + 1 is odd and satisfies (a * γ) % (2 * b) = 1 % (2 * b).
Since n is not odd, Int.not_odd_iff_even.mp implies that n is even, so n = 2k for some integer k. We choose γ = 3(2k) + 1 = 6k + 1 = 3n + 1, which is odd because γ = 2(3k) + 1. Applying Int.emod_eq_emod_iff_emod_sub_eq_zero and Int.emod_eq_zero_of_dvd reduces the modular congruence to showing that 2b divides a * γ - 1. Expanding the algebraic expression gives (2(2k) - 1)(3(2k) + 1) - 1 = (4k - 1)(6k + 1) - 1 = 24k² - 2k - 2 = 2(4k + 1)(3k - 1) = 2b * (3k - 1), confirming divisibility with quotient 3k - 1.
uses
Int.not_odd_iff_even.mp,Int.emod_eq_emod_iff_emod_sub_eq_zero,Int.emod_eq_zero_of_dvd· have he : Even n := Int.not_odd_iff_even.mp h obtain ⟨k, rfl⟩ := he refine ⟨3 * (2 * k) + 1, ⟨3 * k, by ring⟩, ?_⟩ rw [Int.emod_eq_emod_iff_emod_sub_eq_zero] exact Int.emod_eq_zero_of_dvd ⟨3 * k - 1, by ring⟩
Int.emod_eq_emod_iff_emod_sub_eq_zero- Two integers have the same remainder modulo n if and only if their difference has remainder 0 modulo n (i.e., n divides their difference).
Int.emod_eq_zero_of_dvd- If an integer a divides an integer b, then the remainder of b modulo a is 0.
Int.not_odd_iff_even.mp- If an integer is not odd, then it is even.
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.
/-- Existence of an odd integer gamma such that a * gamma is congruent to 1 modulo 2b. -/theorem four_point_set_coprime_inverse_odd (n : ℤ) : let a : ℤ := 2 * n - 1 let b : ℤ := 2 * n + 1 ∃ gamma : ℤ, Odd gamma ∧ (a * gamma) % (2 * b) = 1 % (2 * b) := by by_cases h : Odd n · obtain ⟨k, rfl⟩ := h refine ⟨2 * k + 1, ⟨k, by ring⟩, ?_⟩ rw [Int.emod_eq_emod_iff_emod_sub_eq_zero] exact Int.emod_eq_zero_of_dvd ⟨k, by ring⟩ · have he : Even n := Int.not_odd_iff_even.mp h obtain ⟨k, rfl⟩ := he refine ⟨3 * (2 * k) + 1, ⟨3 * k, by ring⟩, ?_⟩ rw [Int.emod_eq_emod_iff_emod_sub_eq_zero] exact Int.emod_eq_zero_of_dvd ⟨3 * k - 1, by ring⟩