nat_prime_power_parts_prime_pow
For a prime p and k ≥ 1, S(p^k) = {p^k}.
Statement
theorem nat_prime_power_parts_prime_pow {p k : ℕ} (hp : p.Prime) (hk : k ≠ 0) :
nat_prime_power_parts (p ^ k) = {p ^ k}- Source
- Sanity lemma for nat_prime_power_parts (arXiv:2610.11098 (An improved lower bound for separating words by permutation automata)).
- Verified
- 11 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- nat_prime_power_partsS(q): the set of maximal prime-power divisors of q, i.e. p^(v_p(q)) for each prime p dividing q.
The proof, explained
By definition, the prime power parts of a number are obtained by raising each of its prime factors to its full multiplicity. Since p is prime and k ≥ 1, the only prime factor of p^k is p, with multiplicity k. Thus the set of prime power parts reduces to the singleton {p^k}.
By definition, the prime power parts of p^k is the image of the prime factors of p^k under the map q ↦ q ^ ((p^k).factorization q).
Unfold the definition of `nat_prime_power_parts`.
unfold nat_prime_power_partsThe domain of prime factors reduces to the singleton {p}.
Because p is prime and k ≠ 0, the only prime factor of p^k is p. Applying `Nat.primeFactors_prime_pow` replaces (p ^ k).primeFactors with {p}.
uses
Nat.primeFactors_prime_powrw [Nat.primeFactors_prime_pow hk hp]The prime power parts of p^k equals {p^k}.
The image of {p} under q ↦ q ^ ((p^k).factorization q) evaluates at p to p ^ ((p^k).factorization p). By `Nat.factorization_pow`, the exponent is k * (p.factorization p), which simplifies to k * 1 = k via `hp.factorization_self`. Simplifying the singleton image closes the goal.
uses
Nat.factorization_pow,hp.factorization_selfsimp [Nat.factorization_pow, hp.factorization_self]
Nat.primeFactors_prime_pow- For a prime p and k ≠ 0, the set of prime factors of p^k is {p}.
Nat.factorization_pow- The prime factorization of n^k is k times the prime factorization of n.
hp.factorization_self- For a prime p, the multiplicity of p in its own prime factorization is 1.
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 nat_prime_power_parts_prime_pow {p k : ℕ} (hp : p.Prime) (hk : k ≠ 0) : nat_prime_power_parts (p ^ k) = {p ^ k} := by unfold nat_prime_power_parts rw [Nat.primeFactors_prime_pow hk hp] simp [Nat.factorization_pow, hp.factorization_self]