R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p : R
k n : ℕ
⊢ (∃ p k, Nat.Prime p ∧ 0 < k ∧ p ^ k = n) ↔ ∃! p, Nat.Prime p ∧ p ∣ n
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p : R
k n : ℕ
⊢ IsPrimePow n ↔ ∃! p, Nat.Prime p ∧ p ∣ n
rw [isPrimePow_nat_iff]
case mp
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p : R
k n : ℕ
⊢ (∃ p k, Nat.Prime p ∧ 0 < k ∧ p ^ k = n) → ∃! p, Nat.Prime p ∧ p ∣ n

case mpr
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p : R
k n : ℕ
⊢ (∃! p, Nat.Prime p ∧ p ∣ n) → ∃ p k, Nat.Prime p ∧ 0 < k ∧ p ^ k = n
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p : R
k n : ℕ
⊢ (∃ p k, Nat.Prime p ∧ 0 < k ∧ p ^ k = n) ↔ ∃! p, Nat.Prime p ∧ p ∣ n
constructor
case mpr.intro.intro.intro
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hq : ∀ (y : ℕ), (fun p => Nat.Prime p ∧ p ∣ n) y → y = p
hp : Nat.Prime p
hn : p ∣ n
⊢ ∃ p k, Nat.Prime p ∧ 0 < k ∧ p ^ k = n
case mpr
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p : R
k n : ℕ
⊢ (∃! p, Nat.Prime p ∧ p ∣ n) → ∃ p k, Nat.Prime p ∧ 0 < k ∧ p ^ k = n
rintro ⟨p, ⟨hp, hn⟩, hq⟩
case mpr.intro.intro.intro.inl
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n p✝ : R
k p : ℕ
hp : Nat.Prime p
hq : ∀ (y : ℕ), (fun p => Nat.Prime p ∧ p ∣ 0) y → y = p
hn : p ∣ 0
⊢ ∃ p k, Nat.Prime p ∧ 0 < k ∧ p ^ k = 0

case mpr.intro.intro.intro.inr
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hq : ∀ (y : ℕ), (fun p => Nat.Prime p ∧ p ∣ n) y → y = p
hp : Nat.Prime p
hn : p ∣ n
hn₀ : n ≠ 0
⊢ ∃ p k, Nat.Prime p ∧ 0 < k ∧ p ^ k = n
case mpr.intro.intro.intro
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hq : ∀ (y : ℕ), (fun p => Nat.Prime p ∧ p ∣ n) y → y = p
hp : Nat.Prime p
hn : p ∣ n
⊢ ∃ p k, Nat.Prime p ∧ 0 < k ∧ p ^ k = n
rcases eq_or_ne n 0 with (rfl | hn₀)
case mpr.intro.intro.intro.inr
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hq : ∀ (y : ℕ), (fun p => Nat.Prime p ∧ p ∣ n) y → y = p
hp : Nat.Prime p
hn : p ∣ n
hn₀ : n ≠ 0
⊢ p ^ ↑(Nat.factorization n) p = n
case mpr.intro.intro.intro.inr
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hq : ∀ (y : ℕ), (fun p => Nat.Prime p ∧ p ∣ n) y → y = p
hp : Nat.Prime p
hn : p ∣ n
hn₀ : n ≠ 0
⊢ ∃ p k, Nat.Prime p ∧ 0 < k ∧ p ^ k = n
refine' ⟨p, n.factorization p, hp, hp.factorization_pos_of_dvd hn₀ hn, _⟩
case mpr.intro.intro.intro.inr
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hp : Nat.Prime p
hn : p ∣ n
hn₀ : n ≠ 0
hq : ∀ (y : ℕ), Nat.Prime y → y ∣ n → y = p
⊢ p ^ ↑(Nat.factorization n) p = n
case mpr.intro.intro.intro.inr
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hq : ∀ (y : ℕ), (fun p => Nat.Prime p ∧ p ∣ n) y → y = p
hp : Nat.Prime p
hn : p ∣ n
hn₀ : n ≠ 0
⊢ p ^ ↑(Nat.factorization n) p = n
simp only [and_imp] at hq
case mpr.intro.intro.intro.inr
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hp : Nat.Prime p
hn : p ∣ n
hn₀ : n ≠ 0
hq : ∀ (y : ℕ), Nat.Prime y → y ∣ n → y = p
⊢ n ∣ p ^ ↑(Nat.factorization n) p
case mpr.intro.intro.intro.inr
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hp : Nat.Prime p
hn : p ∣ n
hn₀ : n ≠ 0
hq : ∀ (y : ℕ), Nat.Prime y → y ∣ n → y = p
⊢ p ^ ↑(Nat.factorization n) p = n
apply Nat.dvd_antisymm (Nat.ord_proj_dvd _ _)
case mpr.intro.intro.intro.inr
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hp : Nat.Prime p
hn : p ∣ n
hn₀ : n ≠ 0
hq : ∀ (y : ℕ), Nat.Prime y → y ∣ n → y = p
⊢ Nat.factors n <+~ Nat.factors (p ^ ↑(Nat.factorization n) p)
case mpr.intro.intro.intro.inr
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hp : Nat.Prime p
hn : p ∣ n
hn₀ : n ≠ 0
hq : ∀ (y : ℕ), Nat.Prime y → y ∣ n → y = p
⊢ n ∣ p ^ ↑(Nat.factorization n) p
apply Nat.dvd_of_factors_subperm hn₀
case mpr.intro.intro.intro.inr
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hp : Nat.Prime p
hn : p ∣ n
hn₀ : n ≠ 0
hq : ∀ (y : ℕ), Nat.Prime y → y ∣ n → y = p
⊢ ∀ (x : ℕ),
    x ∈ Nat.factors n → List.count x (Nat.factors n) ≤ List.count x (List.replicate (↑(Nat.factorization n) p) p)
case mpr.intro.intro.intro.inr
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hp : Nat.Prime p
hn : p ∣ n
hn₀ : n ≠ 0
hq : ∀ (y : ℕ), Nat.Prime y → y ∣ n → y = p
⊢ Nat.factors n <+~ Nat.factors (p ^ ↑(Nat.factorization n) p)
rw [hp.factors_pow, List.subperm_ext_iff]
case mpr.intro.intro.intro.inr
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hp : Nat.Prime p
hn : p ∣ n
hn₀ : n ≠ 0
hq : ∀ (y : ℕ), Nat.Prime y → y ∣ n → y = p
q : ℕ
hq' : q ∈ Nat.factors n
⊢ List.count q (Nat.factors n) ≤ List.count q (List.replicate (↑(Nat.factorization n) p) p)
case mpr.intro.intro.intro.inr
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hp : Nat.Prime p
hn : p ∣ n
hn₀ : n ≠ 0
hq : ∀ (y : ℕ), Nat.Prime y → y ∣ n → y = p
⊢ ∀ (x : ℕ),
    x ∈ Nat.factors n → List.count x (Nat.factors n) ≤ List.count x (List.replicate (↑(Nat.factorization n) p) p)
intro q hq'
case mpr.intro.intro.intro.inr
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hp : Nat.Prime p
hn : p ∣ n
hn₀ : n ≠ 0
hq : ∀ (y : ℕ), Nat.Prime y → y ∣ n → y = p
q : ℕ
hq' : Nat.Prime q ∧ q ∣ n
⊢ List.count q (Nat.factors n) ≤ List.count q (List.replicate (↑(Nat.factorization n) p) p)
case mpr.intro.intro.intro.inr
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hp : Nat.Prime p
hn : p ∣ n
hn₀ : n ≠ 0
hq : ∀ (y : ℕ), Nat.Prime y → y ∣ n → y = p
q : ℕ
hq' : q ∈ Nat.factors n
⊢ List.count q (Nat.factors n) ≤ List.count q (List.replicate (↑(Nat.factorization n) p) p)
rw [Nat.mem_factors hn₀] at hq'
case mpr.intro.intro.intro.inr.refl
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hp : Nat.Prime p
hn : p ∣ n
hn₀ : n ≠ 0
hq : ∀ (y : ℕ), Nat.Prime y → y ∣ n → y = p
hq' : Nat.Prime p ∧ p ∣ n
⊢ List.count p (Nat.factors n) ≤ List.count p (List.replicate (↑(Nat.factorization n) p) p)
case mpr.intro.intro.intro.inr
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hp : Nat.Prime p
hn : p ∣ n
hn₀ : n ≠ 0
hq : ∀ (y : ℕ), Nat.Prime y → y ∣ n → y = p
q : ℕ
hq' : Nat.Prime q ∧ q ∣ n
⊢ List.count q (Nat.factors n) ≤ List.count q (List.replicate (↑(Nat.factorization n) p) p)
cases hq _ hq'.1 hq'.2
no goals
case mpr.intro.intro.intro.inr.refl
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p✝ : R
k n p : ℕ
hp : Nat.Prime p
hn : p ∣ n
hn₀ : n ≠ 0
hq : ∀ (y : ℕ), Nat.Prime y → y ∣ n → y = p
hq' : Nat.Prime p ∧ p ∣ n
⊢ List.count p (Nat.factors n) ≤ List.count p (List.replicate (↑(Nat.factorization n) p) p)
simp
case mp.intro.intro.intro.intro
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n p✝ : R
k✝ p k : ℕ
hp : Nat.Prime p
hk : 0 < k
⊢ ∃! p_1, Nat.Prime p_1 ∧ p_1 ∣ p ^ k
case mp
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n✝ p : R
k n : ℕ
⊢ (∃ p k, Nat.Prime p ∧ 0 < k ∧ p ^ k = n) → ∃! p, Nat.Prime p ∧ p ∣ n
rintro ⟨p, k, hp, hk, rfl⟩
case mp.intro.intro.intro.intro
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n p✝ : R
k✝ p k : ℕ
hp : Nat.Prime p
hk : 0 < k
⊢ ∀ (y : ℕ), (fun p_1 => Nat.Prime p_1 ∧ p_1 ∣ p ^ k) y → y = p
case mp.intro.intro.intro.intro
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n p✝ : R
k✝ p k : ℕ
hp : Nat.Prime p
hk : 0 < k
⊢ ∃! p_1, Nat.Prime p_1 ∧ p_1 ∣ p ^ k
refine' ⟨p, ⟨hp, dvd_pow_self _ hk.ne'⟩, _⟩
case mp.intro.intro.intro.intro.intro
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n p✝ : R
k✝ p k : ℕ
hp : Nat.Prime p
hk : 0 < k
q : ℕ
hq : Nat.Prime q
hq' : q ∣ p ^ k
⊢ q = p
case mp.intro.intro.intro.intro
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n p✝ : R
k✝ p k : ℕ
hp : Nat.Prime p
hk : 0 < k
⊢ ∀ (y : ℕ), (fun p_1 => Nat.Prime p_1 ∧ p_1 ∣ p ^ k) y → y = p
rintro q ⟨hq, hq'⟩
no goals
case mp.intro.intro.intro.intro.intro
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n p✝ : R
k✝ p k : ℕ
hp : Nat.Prime p
hk : 0 < k
q : ℕ
hq : Nat.Prime q
hq' : q ∣ p ^ k
⊢ q = p
exact (Nat.prime_dvd_prime_iff_eq hq hp).1 (hq.dvd_of_dvd_pow hq')
no goals
case mpr.intro.intro.intro.inl
R : Type ?u.8343
inst✝ : CommMonoidWithZero R
n p✝ : R
k p : ℕ
hp : Nat.Prime p
hq : ∀ (y : ℕ), (fun p => Nat.Prime p ∧ p ∣ 0) y → y = p
hn : p ∣ 0
⊢ ∃ p k, Nat.Prime p ∧ 0 < k ∧ p ^ k = 0
cases (hq 2 ⟨Nat.prime_two, dvd_zero 2⟩).trans (hq 3 ⟨Nat.prime_three, dvd_zero 3⟩).symm