Prime-power obstructions form a divisor
ProvedNat.prod_pow_factorization_sub_factorization_add_one_dvdnumber-theorytauceti-chebotarev
Let with . Write for the finite set of prime factors of , with , and set . Then
The tested prime-power obstructions combine into a single divisor, including the zero boundary case.
Source and proof credit: the Tau Ceti contributors, original declaration and proof, Apache-2.0, commit 948fe4751b1fe528b6d580c522ca5d743d47f185; adapted to Lean 4.33.1.
Preamble
/- Transplanted from https://github.com/TauCetiProject/TauCeti at 948fe4751b1fe528b6d580c522ca5d743d47f185. Original source copyright/license notices are retained below. Generated exclusively from compiler declaration, command, and reference facts. -/ import Mathlib.Algebra.BigOperators.Finsupp.Basic import Mathlib.Data.Nat.Factorization.Basic section set_option autoImplicit true /- Copyright (c) 2026 The Tau Ceti contributors. All rights reserved. Released under Apache 2.0 license as described in the file LICENSE. Authors: The Tau Ceti contributors -/ /-! # The prime powers that decide whether a divisor fits beside a fixed factor Let `f` and `d` both divide `h`. Whether the product `f * d` still divides `h` is decided one prime at a time, and only at the primes of `f`: room for `f * d` fails at `p` exactly when `d` carries `p` to a power that exceeds the room `h` leaves after `f`, which is `v_p h - v_p f`. So `f * d ∣ h` holds exactly when no prime `p` of `f` divides `d` to the exponent `v_p h - v_p f + 1`. The one-sided reading is what makes the statement useful: the primes outside `f` impose no condition, because `d ∣ h` already leaves them enough room. The exponents `v_p h - v_p f + 1` are themselves exponents of prime powers dividing `h`, both one prime at a time and all at once, since the primes of `f` are distinct. ## Main results * `Nat.mul_dvd_iff_forall_not_pow_dvd`: `f * d ∣ h` as non-divisibility of `d` by a prime power at each prime of `f`. * `Nat.pow_factorization_sub_factorization_add_one_dvd`: the tested prime power divides `h`. * `Nat.prod_pow_factorization_sub_factorization_add_one_dvd`: so does their product over the primes of `f`. -/ section namespace Nat end Nat section Nat open Nat open Finset
Formal statement
theorem Nat.prod_pow_factorization_sub_factorization_add_one_dvd {f h : ℕ} (hf : f ∣ h) :
(∏ p ∈ f.primeFactors, p ^ (h.factorization p - f.factorization p + 1)) ∣ h := by sorry
Source