AFTD Auto-Formalizing Theoretical Domains

four_point_set_coprime_inverse_odd

theoremverified

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.

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

    line 6

      by_cases h : Odd n
  2. When 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.

    lines 7–10

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

    lines 11–15

    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

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