AFTD Auto-Formalizing Theoretical Domains

not_div_padicValNat_dvd_div_padicValNat

theoremverifiedoriginal

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.

  1. 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.

    line 2

      intro h
  2. padicValNat 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.

    lines 3–5

    uses padicValNat.eq_zero_of_not_dvd

      have h6 : padicValNat 4 6 = 0 := by
        rw [padicValNat.eq_zero_of_not_dvd]
        norm_num
  3. 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.

    lines 6–11

    uses Nat.maxPowDvdDiv_of_pow_mul_eq

      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]
  4. 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.

    lines 12–13

      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)
  5. 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.

    lines 14–15

      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).

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

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
See it in the graphDiscuss this resultChallenge it