not_div_padicValNat_dvd_div_padicValNat
The statement div_padicValNat_dvd_div_padicValNat is false: The statement is false for non-prime p. Take d = 6, n = 48, p = 4. Then 0 < 6 and 6 ∣ 48. Since 4 ∤ 6, padicValNat 4 6 = 0, so d / 4^{padicValNat 4 6} = 6. Since 4^2 = 16 divides 48 but 4^3 = 64 does not, padicValNat 4 48 = 2, so n / 4^{padicValNat 4 48} = 48 / 16 = 3. But 6 does not divide 3. The statement is presumably intended with p prime (or with a hypothesis such as Fact p.Prime).
Statement
theorem not_div_padicValNat_dvd_div_padicValNat : ¬ (∀ {d n p : ℕ} (hd : 0 < d) (hdn : d ∣ n), d / p ^ padicValNat p d ∣ n / p ^ padicValNat p n)- Related work
- refutes `div_padicValNat_dvd_div_padicValNat`
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem disproves the universal statement by exhibiting an explicit counterexample: d = 6, n = 48, and p = 4. Assuming the statement holds in general, we compute the 4-adic valuations padicValNat 4 6 = 0 and padicValNat 4 48 = 2 using the maximal power division of natural numbers. Specializing the universal hypothesis to these values forces 6 to divide 3, an arithmetic contradiction that refutes the claim.
Assume for contradiction that the divisibility statement holds for all d, n, and p with 0 < d and d ∣ n.
To prove the negation of the universal statement, we assume it as hypothesis h and aim to derive False.
intro hpadicValNat 4 6 = 0
Since 4 does not divide 6 (checked by numerical evaluation), padicValNat.eq_zero_of_not_dvd establishes that padicValNat 4 6 = 0.
uses
padicValNat.eq_zero_of_not_dvdhave h6 : padicValNat 4 6 = 0 := by rw [padicValNat.eq_zero_of_not_dvd] norm_num
padicValNat 4 48 = 2
Using Nat.maxPowDvdDiv_of_pow_mul_eq, we establish that Nat.maxPowDvdDiv 4 48 = (2, 3) because 48 ≠ 0, 4^2 * 3 = 48, and 4 does not divide 3, all verified by basic arithmetic. Unfolding the definition of padicValNat extracts the first component, yielding 2.
uses
Nat.maxPowDvdDiv_of_pow_mul_eqhave h48 : padicValNat 4 48 = 2 := by have h : Nat.maxPowDvdDiv 4 48 = (2, 3) := by apply Nat.maxPowDvdDiv_of_pow_mul_eq (by norm_num : (48:ℕ) ≠ 0) · norm_num · norm_num simp [padicValNat, h]
6 / 4 ^ padicValNat 4 6 ∣ 48 / 4 ^ padicValNat 4 48
We instantiate the universal assumption h with d = 6, n = 48, and p = 4. The side conditions 0 < 6 and 6 ∣ 48 are discharged by arithmetic evaluation.
have hc : 6 / 4 ^ padicValNat 4 6 ∣ 48 / 4 ^ padicValNat 4 48 := h (d := 6) (n := 48) (p := 4) (by norm_num) (by norm_num)
A contradiction is reached (False). automation
Substituting the values padicValNat 4 6 = 0 and padicValNat 4 48 = 2 rewrites the divisibility assumption to 6 / 4^0 ∣ 48 / 4^2, which simplifies to 6 ∣ 3. Numerical evaluation detects that 6 does not divide 3, producing a contradiction.
rw [h6, h48] at hc norm_num at hc
padicValNat.eq_zero_of_not_dvd- If p does not divide n, then padicValNat p n is 0.
Nat.maxPowDvdDiv_of_pow_mul_eq- If n ≠ 0, p^k * l = n, and p does not divide l, then the maximal power division of n by p is the pair (k, l).
- In standard mathematical usage, p-adic valuations are defined only when p is prime. In Mathlib, padicValNat is generalized to arbitrary natural numbers p via Nat.maxPowDvdDiv, returning the highest power k such that p^k divides n. The counterexample fundamentally relies on taking a composite base, p = 4.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem not_div_padicValNat_dvd_div_padicValNat : ¬ (∀ {d n p : ℕ} (hd : 0 < d) (hdn : d ∣ n), d / p ^ padicValNat p d ∣ n / p ^ padicValNat p n) := by intro h have h6 : padicValNat 4 6 = 0 := by rw [padicValNat.eq_zero_of_not_dvd] norm_num have h48 : padicValNat 4 48 = 2 := by have h : Nat.maxPowDvdDiv 4 48 = (2, 3) := by apply Nat.maxPowDvdDiv_of_pow_mul_eq (by norm_num : (48:ℕ) ≠ 0) · norm_num · norm_num simp [padicValNat, h] have hc : 6 / 4 ^ padicValNat 4 6 ∣ 48 / 4 ^ padicValNat 4 48 := h (d := 6) (n := 48) (p := 4) (by norm_num) (by norm_num) rw [h6, h48] at hc norm_num at hc