Divisibility is equivalent to divisibility by every factorization prime power
ProvedWikipedia.SzemeredisTheorem.dvd_iff_primePower_dvdadditive-combinatoricsgreen-tao-port-8822number-theory
For a nonzero natural number and any natural number ,
The criterion includes and , with the usual empty-family convention when .
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_LinearForms_Geometry import Definitions.Def_GreenTaoPort_Wikipedia_GreenTao_LinearForms_Independence import Definitions.Def_GreenTaoPort_Wikipedia_GreenTao_Primes_ReducedResidues import Definitions.Def_GreenTaoPort_Wikipedia_GreenTao_Primes_WTrick import Definitions.Def_GreenTaoPort_Wikipedia_GreenTao_Sieve_CongruenceAverage import Definitions.Def_GreenTaoPort_Wikipedia_GreenTao_Sieve_ExceptionalPrimes import Definitions.Def_GreenTaoPort_Wikipedia_GreenTao_Sieve_LinearFormsExpansion import Definitions.Def_GreenTaoPort_Wikipedia_GreenTao_Sieve_LocalFactors import Definitions.Def_GreenTaoPort_Wikipedia_GreenTao_Sieve_PairedDivisibilityCRT import Definitions.Def_GreenTaoPort_Wikipedia_GreenTao_Sieve_SmoothCutoff import Definitions.Def_GreenTaoPort_Wikipedia_GreenTao_Sieve_SmoothMajorant import Definitions.Def_GreenTaoPort_Wikipedia_GreenTao_Sieve_TruncatedDivisorSum import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Finite_Mean import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_LinearForms_Basic import Mathlib.Algebra.BigOperators.Expect import Mathlib.Algebra.Field.ZMod import Mathlib.Algebra.GCDMonoid.FinsetLemmas import Mathlib.Algebra.Order.BigOperators.Group.Finset import Mathlib.Analysis.Calculus.BumpFunction.InnerProduct import Mathlib.Analysis.Calculus.ContDiff.Deriv import Mathlib.Analysis.Calculus.Deriv.MeanValue import Mathlib.Analysis.Calculus.Deriv.Support import Mathlib.Analysis.SpecialFunctions.Log.Basic import Mathlib.Combinatorics.Pigeonhole import Mathlib.Data.Fintype.BigOperators import Mathlib.Data.Fintype.Card import Mathlib.Data.Fintype.Pi import Mathlib.Data.Int.Lemmas import Mathlib.Data.Nat.Totient import Mathlib.Data.ZMod.Basic import Mathlib.Data.ZMod.QuotientRing import Mathlib.GroupTheory.Index import Mathlib.LinearAlgebra.Pi import Mathlib.Logic.Equiv.Fin.Basic import Mathlib.MeasureTheory.Integral.Bochner.Set import Mathlib.MeasureTheory.Integral.IntegralEqImproper import Mathlib.NumberTheory.ArithmeticFunction.Moebius import Mathlib.NumberTheory.Divisors import Mathlib.NumberTheory.Primorial import Mathlib.Tactic set_option autoImplicit true set_option relaxedAutoImplicit false set_option maxSynthPendingDepth 3 /-! # CRT factorization of paired divisibility densities The divisor expansion of a product of Selberg weights leaves an exact finite density `pairedDivisibilityDensity`. This file isolates the arithmetic steps which can be performed without any analytic estimate. First, the two divisor conditions attached to one form are replaced by their least common multiple. The resulting zero--one function is identified with the indicator of its exact finite support, and each nonzero local modulus is then decomposed into its prime-power divisibility conditions. Second, normalized means are reindexed by the Chinese remainder theorem. For any finite pairwise-coprime family of moduli, a product of functions which depends separately on the corresponding CRT components has mean equal to the product of its local means. We specialize this both to two moduli and to the canonical prime-power decomposition of a nonzero modulus. For arbitrary natural-valued forms, CRT factorization is not automatic: one must still show that the global paired divisibility indicator depends on the CRT components as a product of local indicators. The final definitions and theorems package precisely that remaining obligation, without asserting a false independence statement. -/ open Wikipedia.SzemeredisTheorem open scoped BigOperators /-! ## Collapsing paired divisibility conditions -/ /-! ## Prime-power divisibility data -/
Formal statement
theorem Wikipedia.SzemeredisTheorem.dvd_iff_primePower_dvd
{d n : ℕ} (hd : d ≠ 0) :
d ∣ n ↔
∀ p : d.primeFactors,
(p : ℕ) ^ d.factorization p ∣ n := by sorry
Source