LEMMA, p. 505 — residues modulo p = 2 or 3
ProvedGomory69.SpecialGroups.lemma_p505modular-arithmeticp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let or , and let be integers with and . Then there are integers with , and
This finite arithmetic fact is the only place where the exponents 2 and 3 enter the proof of THEOREM 23; it fails for (, ).
Preamble
import Mathlib
Formal statement
namespace Gomory69.SpecialGroups
/-- The LEMMA of p. 505 (Gomory 1969): for `p = 2` or `p = 3`, if `t, s` are integers with
`p > t > 0` and `p > s ≥ 0`, there are integers `t', t''` with `t ≥ t' ≥ 0`, `t ≥ t'' ≥ 0` and
`t' + s ≡ t'' (mod p)`. -/
theorem lemma_p505 (p : ℤ) (hp : p = 2 ∨ p = 3) (t s : ℤ)
(ht₀ : 0 < t) (htp : t < p) (hs₀ : 0 ≤ s) (hsp : s < p) :
∃ t' t'' : ℤ, 0 ≤ t' ∧ t' ≤ t ∧ 0 ≤ t'' ∧ t'' ≤ t ∧ t' + s ≡ t'' [ZMOD p] := by sorry
end Gomory69.SpecialGroups
Source
Gomory, Some polyhedra related to combinatorial problems, Linear Algebra Appl. 2 (1969), p. 505, LEMMA
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.