A reduced-residue pigeonhole bound without division
ProvedWikipedia.SzemeredisTheorem.exists_reducedResidue_card_le_totient_mul_card_fiberadditive-combinatoricsgreen-tao-port-8822number-theory
Let and let be a finite set of natural numbers, each coprime to . There is a reduced residue modulo for which .
Preamble
/- Mechanically transplanted from https://github.com/plby/lean-proofs.git at 8822f7ddef30fadbd92e1c6ab4ed897af356af5e. Original scopes and proof bytes are oracle-derived. -/ import Definitions.Def_GreenTaoPort_Wikipedia_GreenTao_Primes_ReducedResidues import Mathlib.Combinatorics.Pigeonhole import Mathlib.Data.Nat.Totient import Mathlib.Data.ZMod.Basic import Mathlib.NumberTheory.Primorial set_option autoImplicit true set_option relaxedAutoImplicit false set_option maxSynthPendingDepth 3 open Wikipedia.SzemeredisTheorem open Finset
Formal statement
theorem Wikipedia.SzemeredisTheorem.exists_reducedResidue_card_le_totient_mul_card_fiber
{W : ℕ} (hW : 0 < W) (S : Finset ℕ)
(hcop : ∀ n ∈ S, n.Coprime W) :
∃ b ∈ reducedResidues W,
#S ≤ W.totient * #(residueFiber S W b) := by sorry
Source