[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
p q : R[X]
inst✝ : Semiring S
hq : Monic q
p₁ p₂ : R[X]
h : q ∣ p₁ - p₂
⊢ p₁ %ₘ q = p₂ %ₘ q
[PROOFSTEP]
nontriviality R
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
p q : R[X]
inst✝ : Semiring S
hq : Monic q
p₁ p₂ : R[X]
h : q ∣ p₁ - p₂
✝ : Nontrivial R
⊢ p₁ %ₘ q = p₂ %ₘ q
[PROOFSTEP]
obtain ⟨f, sub_eq⟩ := h
[GOAL]
case intro
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
p q : R[X]
inst✝ : Semiring S
hq : Monic q
p₁ p₂ : R[X]
✝ : Nontrivial R
f : R[X]
sub_eq : p₁ - p₂ = q * f
⊢ p₁ %ₘ q = p₂ %ₘ q
[PROOFSTEP]
refine' (div_modByMonic_unique (p₂ /ₘ q + f) _ hq ⟨_, degree_modByMonic_lt _ hq⟩).2
[GOAL]
case intro
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
p q : R[X]
inst✝ : Semiring S
hq : Monic q
p₁ p₂ : R[X]
✝ : Nontrivial R
f : R[X]
sub_eq : p₁ - p₂ = q * f
⊢ p₂ %ₘ q + q * (p₂ /ₘ q + f) = p₁
[PROOFSTEP]
rw [sub_eq_iff_eq_add.mp sub_eq, mul_add, ← add_assoc, modByMonic_add_div _ hq, add_comm]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
p q : R[X]
inst✝ : Semiring S
p₁ p₂ : R[X]
⊢ (p₁ + p₂) %ₘ q = p₁ %ₘ q + p₂ %ₘ q
[PROOFSTEP]
by_cases hq : q.Monic
[GOAL]
case pos
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
p q : R[X]
inst✝ : Semiring S
p₁ p₂ : R[X]
hq : Monic q
⊢ (p₁ + p₂) %ₘ q = p₁ %ₘ q + p₂ %ₘ q
[PROOFSTEP]
cases' subsingleton_or_nontrivial R with hR hR
[GOAL]
case pos.inl
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
p q : R[X]
inst✝ : Semiring S
p₁ p₂ : R[X]
hq : Monic q
hR : Subsingleton R
⊢ (p₁ + p₂) %ₘ q = p₁ %ₘ q + p₂ %ₘ q
[PROOFSTEP]
simp only [eq_iff_true_of_subsingleton]
[GOAL]
case pos.inr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
p q : R[X]
inst✝ : Semiring S
p₁ p₂ : R[X]
hq : Monic q
hR : Nontrivial R
⊢ (p₁ + p₂) %ₘ q = p₁ %ₘ q + p₂ %ₘ q
[PROOFSTEP]
exact
  (div_modByMonic_unique (p₁ /ₘ q + p₂ /ₘ q) _ hq
      ⟨by
        rw [mul_add, add_left_comm, add_assoc, modByMonic_add_div _ hq, ← add_assoc, add_comm (q * _),
          modByMonic_add_div _ hq],
        (degree_add_le _ _).trans_lt (max_lt (degree_modByMonic_lt _ hq) (degree_modByMonic_lt _ hq))⟩).2
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
p q : R[X]
inst✝ : Semiring S
p₁ p₂ : R[X]
hq : Monic q
hR : Nontrivial R
⊢ p₁ %ₘ q + p₂ %ₘ q + q * (p₁ /ₘ q + p₂ /ₘ q) = p₁ + p₂
[PROOFSTEP]
rw [mul_add, add_left_comm, add_assoc, modByMonic_add_div _ hq, ← add_assoc, add_comm (q * _), modByMonic_add_div _ hq]
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
p q : R[X]
inst✝ : Semiring S
p₁ p₂ : R[X]
hq : ¬Monic q
⊢ (p₁ + p₂) %ₘ q = p₁ %ₘ q + p₂ %ₘ q
[PROOFSTEP]
simp_rw [modByMonic_eq_of_not_monic _ hq]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
p✝ q : R[X]
inst✝ : Semiring S
c : R
p : R[X]
⊢ c • p %ₘ q = c • (p %ₘ q)
[PROOFSTEP]
by_cases hq : q.Monic
[GOAL]
case pos
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
p✝ q : R[X]
inst✝ : Semiring S
c : R
p : R[X]
hq : Monic q
⊢ c • p %ₘ q = c • (p %ₘ q)
[PROOFSTEP]
cases' subsingleton_or_nontrivial R with hR hR
[GOAL]
case pos.inl
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
p✝ q : R[X]
inst✝ : Semiring S
c : R
p : R[X]
hq : Monic q
hR : Subsingleton R
⊢ c • p %ₘ q = c • (p %ₘ q)
[PROOFSTEP]
simp only [eq_iff_true_of_subsingleton]
[GOAL]
case pos.inr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
p✝ q : R[X]
inst✝ : Semiring S
c : R
p : R[X]
hq : Monic q
hR : Nontrivial R
⊢ c • p %ₘ q = c • (p %ₘ q)
[PROOFSTEP]
exact
  (div_modByMonic_unique (c • (p /ₘ q)) (c • (p %ₘ q)) hq
      ⟨by rw [mul_smul_comm, ← smul_add, modByMonic_add_div p hq],
        (degree_smul_le _ _).trans_lt (degree_modByMonic_lt _ hq)⟩).2
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
p✝ q : R[X]
inst✝ : Semiring S
c : R
p : R[X]
hq : Monic q
hR : Nontrivial R
⊢ c • (p %ₘ q) + q * c • (p /ₘ q) = c • p
[PROOFSTEP]
rw [mul_smul_comm, ← smul_add, modByMonic_add_div p hq]
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
p✝ q : R[X]
inst✝ : Semiring S
c : R
p : R[X]
hq : ¬Monic q
⊢ c • p %ₘ q = c • (p %ₘ q)
[PROOFSTEP]
simp_rw [modByMonic_eq_of_not_monic _ hq]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
p✝ q✝ : R[X]
inst✝¹ : Ring S
inst✝ : Algebra R S
p q : R[X]
hq : Monic q
x : S
hx : ↑(aeval x) q = 0
⊢ ↑(aeval x) (p %ₘ q) = ↑(aeval x) p
[PROOFSTEP]
rw [modByMonic_eq_sub_mul_div p hq, _root_.map_sub, _root_.map_mul, hx, zero_mul, sub_zero]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p q a✝ b✝ : R[X]
h : a✝ * b✝ = 0
⊢ a✝ = 0 ∨ b✝ = 0
[PROOFSTEP]
rw [← leadingCoeff_eq_zero, ← leadingCoeff_eq_zero]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p q a✝ b✝ : R[X]
h : a✝ * b✝ = 0
⊢ leadingCoeff a✝ = 0 ∨ leadingCoeff b✝ = 0
[PROOFSTEP]
refine' eq_zero_or_eq_zero_of_mul_eq_zero _
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p q a✝ b✝ : R[X]
h : a✝ * b✝ = 0
⊢ leadingCoeff a✝ * leadingCoeff b✝ = 0
[PROOFSTEP]
rw [← leadingCoeff_zero, ← leadingCoeff_mul, h]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : p ≠ 0
hq : q ≠ 0
⊢ natDegree (p * q) = natDegree p + natDegree q
[PROOFSTEP]
rw [← WithBot.coe_eq_coe, ← Nat.cast_withBot, ← degree_eq_natDegree (mul_ne_zero hp hq), WithBot.coe_add, ←
  Nat.cast_withBot, ← degree_eq_natDegree hp, ← Nat.cast_withBot, ← degree_eq_natDegree hq, degree_mul]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p q : R[X]
⊢ trailingDegree (p * q) = trailingDegree p + trailingDegree q
[PROOFSTEP]
by_cases hp : p = 0
[GOAL]
case pos
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : p = 0
⊢ trailingDegree (p * q) = trailingDegree p + trailingDegree q
[PROOFSTEP]
rw [hp, zero_mul, trailingDegree_zero, top_add]
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : ¬p = 0
⊢ trailingDegree (p * q) = trailingDegree p + trailingDegree q
[PROOFSTEP]
by_cases hq : q = 0
[GOAL]
case pos
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : ¬p = 0
hq : q = 0
⊢ trailingDegree (p * q) = trailingDegree p + trailingDegree q
[PROOFSTEP]
rw [hq, mul_zero, trailingDegree_zero, add_top]
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : ¬p = 0
hq : ¬q = 0
⊢ trailingDegree (p * q) = trailingDegree p + trailingDegree q
[PROOFSTEP]
rw [trailingDegree_eq_natTrailingDegree hp, trailingDegree_eq_natTrailingDegree hq,
  trailingDegree_eq_natTrailingDegree (mul_ne_zero hp hq), natTrailingDegree_mul hp hq]
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : ¬p = 0
hq : ¬q = 0
⊢ ↑(natTrailingDegree p + natTrailingDegree q) = ↑(natTrailingDegree p) + ↑(natTrailingDegree q)
[PROOFSTEP]
apply WithTop.coe_add
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n✝ : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q p : R[X]
n : ℕ
⊢ natDegree (p ^ n) = n * natDegree p
[PROOFSTEP]
classical exact
  if hp0 : p = 0 then if hn0 : n = 0 then by simp [hp0, hn0] else by rw [hp0, zero_pow (Nat.pos_of_ne_zero hn0)]; simp
  else natDegree_pow' (by rw [← leadingCoeff_pow, Ne.def, leadingCoeff_eq_zero]; exact pow_ne_zero _ hp0)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n✝ : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q p : R[X]
n : ℕ
⊢ natDegree (p ^ n) = n * natDegree p
[PROOFSTEP]
exact
  if hp0 : p = 0 then if hn0 : n = 0 then by simp [hp0, hn0] else by rw [hp0, zero_pow (Nat.pos_of_ne_zero hn0)]; simp
  else natDegree_pow' (by rw [← leadingCoeff_pow, Ne.def, leadingCoeff_eq_zero]; exact pow_ne_zero _ hp0)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n✝ : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q p : R[X]
n : ℕ
hp0 : p = 0
hn0 : n = 0
⊢ natDegree (p ^ n) = n * natDegree p
[PROOFSTEP]
simp [hp0, hn0]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n✝ : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q p : R[X]
n : ℕ
hp0 : p = 0
hn0 : ¬n = 0
⊢ natDegree (p ^ n) = n * natDegree p
[PROOFSTEP]
rw [hp0, zero_pow (Nat.pos_of_ne_zero hn0)]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n✝ : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q p : R[X]
n : ℕ
hp0 : p = 0
hn0 : ¬n = 0
⊢ natDegree 0 = n * natDegree 0
[PROOFSTEP]
simp
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n✝ : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q p : R[X]
n : ℕ
hp0 : ¬p = 0
⊢ leadingCoeff p ^ n ≠ 0
[PROOFSTEP]
rw [← leadingCoeff_pow, Ne.def, leadingCoeff_eq_zero]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n✝ : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q p : R[X]
n : ℕ
hp0 : ¬p = 0
⊢ ¬p ^ n = 0
[PROOFSTEP]
exact pow_ne_zero _ hp0
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q p : R[X]
hq : q ≠ 0
⊢ degree p ≤ degree (p * q)
[PROOFSTEP]
classical exact
  if hp : p = 0 then by simp only [hp, zero_mul, le_refl]
  else by rw [degree_mul, degree_eq_natDegree hp, degree_eq_natDegree hq];
    exact WithBot.coe_le_coe.2 (Nat.le_add_right _ _)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q p : R[X]
hq : q ≠ 0
⊢ degree p ≤ degree (p * q)
[PROOFSTEP]
exact
  if hp : p = 0 then by simp only [hp, zero_mul, le_refl]
  else by rw [degree_mul, degree_eq_natDegree hp, degree_eq_natDegree hq];
    exact WithBot.coe_le_coe.2 (Nat.le_add_right _ _)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q p : R[X]
hq : q ≠ 0
hp : p = 0
⊢ degree p ≤ degree (p * q)
[PROOFSTEP]
simp only [hp, zero_mul, le_refl]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q p : R[X]
hq : q ≠ 0
hp : ¬p = 0
⊢ degree p ≤ degree (p * q)
[PROOFSTEP]
rw [degree_mul, degree_eq_natDegree hp, degree_eq_natDegree hq]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q p : R[X]
hq : q ≠ 0
hp : ¬p = 0
⊢ ↑(natDegree p) ≤ ↑(natDegree p) + ↑(natDegree q)
[PROOFSTEP]
exact WithBot.coe_le_coe.2 (Nat.le_add_right _ _)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q✝ p q : R[X]
h1 : p ∣ q
h2 : q ≠ 0
⊢ natDegree p ≤ natDegree q
[PROOFSTEP]
rcases h1 with ⟨q, rfl⟩
[GOAL]
case intro
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q✝ p q : R[X]
h2 : p * q ≠ 0
⊢ natDegree p ≤ natDegree (p * q)
[PROOFSTEP]
rw [mul_ne_zero_iff] at h2 
[GOAL]
case intro
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q✝ p q : R[X]
h2 : p ≠ 0 ∧ q ≠ 0
⊢ natDegree p ≤ natDegree (p * q)
[PROOFSTEP]
rw [natDegree_mul h2.1 h2.2]
[GOAL]
case intro
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q✝ p q : R[X]
h2 : p ≠ 0 ∧ q ≠ 0
⊢ natDegree p ≤ natDegree p + natDegree q
[PROOFSTEP]
exact Nat.le_add_right _ _
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q✝ p q : R[X]
h1 : p ∣ q
h2 : q ≠ 0
⊢ degree p ≤ degree q
[PROOFSTEP]
rcases h1 with ⟨q, rfl⟩
[GOAL]
case intro
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q✝ p q : R[X]
h2 : p * q ≠ 0
⊢ degree p ≤ degree (p * q)
[PROOFSTEP]
rw [mul_ne_zero_iff] at h2 
[GOAL]
case intro
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q✝ p q : R[X]
h2 : p ≠ 0 ∧ q ≠ 0
⊢ degree p ≤ degree (p * q)
[PROOFSTEP]
exact degree_le_mul_left p h2.2
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q✝ p q : R[X]
h₁ : p ∣ q
h₂ : degree q < degree p
⊢ q = 0
[PROOFSTEP]
by_contra hc
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q✝ p q : R[X]
h₁ : p ∣ q
h₂ : degree q < degree p
hc : ¬q = 0
⊢ False
[PROOFSTEP]
exact (lt_iff_not_ge _ _).mp h₂ (degree_le_of_dvd h₁ hc)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q✝ p q : R[X]
h₁ : p ∣ q
h₂ : natDegree q < natDegree p
⊢ q = 0
[PROOFSTEP]
by_contra hc
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q✝ p q : R[X]
h₁ : p ∣ q
h₂ : natDegree q < natDegree p
hc : ¬q = 0
⊢ False
[PROOFSTEP]
exact (lt_iff_not_ge _ _).mp h₂ (natDegree_le_of_dvd h₁ hc)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q✝ p q : R[X]
h0 : q ≠ 0
hl : degree q < degree p
⊢ ¬p ∣ q
[PROOFSTEP]
by_contra hcontra
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q✝ p q : R[X]
h0 : q ≠ 0
hl : degree q < degree p
hcontra : p ∣ q
⊢ False
[PROOFSTEP]
exact h0 (eq_zero_of_dvd_of_degree_lt hcontra hl)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q✝ p q : R[X]
h0 : q ≠ 0
hl : natDegree q < natDegree p
⊢ ¬p ∣ q
[PROOFSTEP]
by_contra hcontra
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p✝ q✝ p q : R[X]
h0 : q ≠ 0
hl : natDegree q < natDegree p
hcontra : p ∣ q
⊢ False
[PROOFSTEP]
exact h0 (eq_zero_of_dvd_of_natDegree_lt hcontra hl)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p q p₁ p₂ q₁ q₂ : R[X]
hp₁ : p₁ ≠ 0
hq₁ : q₁ ≠ 0
hp₂ : p₂ ≠ 0
hq₂ : q₂ ≠ 0
h_eq : p₁ * q₂ = p₂ * q₁
⊢ ↑(natDegree p₁) - ↑(natDegree q₁) = ↑(natDegree p₂) - ↑(natDegree q₂)
[PROOFSTEP]
rw [sub_eq_sub_iff_add_eq_add]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p q p₁ p₂ q₁ q₂ : R[X]
hp₁ : p₁ ≠ 0
hq₁ : q₁ ≠ 0
hp₂ : p₂ ≠ 0
hq₂ : q₂ ≠ 0
h_eq : p₁ * q₂ = p₂ * q₁
⊢ ↑(natDegree p₁) + ↑(natDegree q₂) = ↑(natDegree p₂) + ↑(natDegree q₁)
[PROOFSTEP]
norm_cast
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p q p₁ p₂ q₁ q₂ : R[X]
hp₁ : p₁ ≠ 0
hq₁ : q₁ ≠ 0
hp₂ : p₂ ≠ 0
hq₂ : q₂ ≠ 0
h_eq : p₁ * q₂ = p₂ * q₁
⊢ natDegree p₁ + natDegree q₂ = natDegree p₂ + natDegree q₁
[PROOFSTEP]
rw [← natDegree_mul hp₁ hq₂, ← natDegree_mul hp₂ hq₁, h_eq]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p q : R[X]
h : IsUnit p
⊢ natDegree p = 0
[PROOFSTEP]
nontriviality R
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p q : R[X]
h : IsUnit p
✝ : Nontrivial R
⊢ natDegree p = 0
[PROOFSTEP]
obtain ⟨q, hq⟩ := h.exists_right_inv
[GOAL]
case intro
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p q✝ : R[X]
h : IsUnit p
✝ : Nontrivial R
q : R[X]
hq : p * q = 1
⊢ natDegree p = 0
[PROOFSTEP]
have := natDegree_mul (left_ne_zero_of_mul_eq_one hq) (right_ne_zero_of_mul_eq_one hq)
[GOAL]
case intro
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p q✝ : R[X]
h : IsUnit p
✝ : Nontrivial R
q : R[X]
hq : p * q = 1
this : natDegree (p * q) = natDegree p + natDegree q
⊢ natDegree p = 0
[PROOFSTEP]
rw [hq, natDegree_one, eq_comm, add_eq_zero_iff] at this 
[GOAL]
case intro
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : Semiring R
inst✝ : NoZeroDivisors R
p q✝ : R[X]
h : IsUnit p
✝ : Nontrivial R
q : R[X]
hq : p * q = 1
this : natDegree p = 0 ∧ natDegree q = 0
⊢ natDegree p = 0
[PROOFSTEP]
exact this.1
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : Monic p
hp1 : p ≠ 1
⊢ Irreducible p ↔ ∀ (f g : R[X]), Monic f → Monic g → f * g = p → f = 1 ∨ g = 1
[PROOFSTEP]
refine'
  ⟨fun h f g hf hg hp => (h.2 f g hp.symm).imp hf.eq_one_of_isUnit hg.eq_one_of_isUnit, fun h =>
    ⟨hp1 ∘ hp.eq_one_of_isUnit, fun f g hfg =>
      (h (g * C f.leadingCoeff) (f * C g.leadingCoeff) _ _ _).symm.imp (isUnit_of_mul_eq_one f _)
        (isUnit_of_mul_eq_one g _)⟩⟩
[GOAL]
case refine'_1
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : Monic p
hp1 : p ≠ 1
h : ∀ (f g : R[X]), Monic f → Monic g → f * g = p → f = 1 ∨ g = 1
f g : R[X]
hfg : p = f * g
⊢ Monic (g * ↑C (leadingCoeff f))
[PROOFSTEP]
rwa [Monic, leadingCoeff_mul, leadingCoeff_C, ← leadingCoeff_mul, mul_comm, ← hfg, ← Monic]
[GOAL]
case refine'_2
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : Monic p
hp1 : p ≠ 1
h : ∀ (f g : R[X]), Monic f → Monic g → f * g = p → f = 1 ∨ g = 1
f g : R[X]
hfg : p = f * g
⊢ Monic (f * ↑C (leadingCoeff g))
[PROOFSTEP]
rwa [Monic, leadingCoeff_mul, leadingCoeff_C, ← leadingCoeff_mul, ← hfg, ← Monic]
[GOAL]
case refine'_3
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : Monic p
hp1 : p ≠ 1
h : ∀ (f g : R[X]), Monic f → Monic g → f * g = p → f = 1 ∨ g = 1
f g : R[X]
hfg : p = f * g
⊢ g * ↑C (leadingCoeff f) * (f * ↑C (leadingCoeff g)) = p
[PROOFSTEP]
rw [mul_mul_mul_comm, ← C_mul, ← leadingCoeff_mul, ← hfg, hp.leadingCoeff, C_1, mul_one, mul_comm, ← hfg]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : Monic p
⊢ Irreducible p ↔ p ≠ 1 ∧ ∀ (f g : R[X]), Monic f → Monic g → f * g = p → natDegree f = 0 ∨ natDegree g = 0
[PROOFSTEP]
by_cases hp1 : p = 1
[GOAL]
case pos
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : Monic p
hp1 : p = 1
⊢ Irreducible p ↔ p ≠ 1 ∧ ∀ (f g : R[X]), Monic f → Monic g → f * g = p → natDegree f = 0 ∨ natDegree g = 0
[PROOFSTEP]
simp [hp1]
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : Monic p
hp1 : ¬p = 1
⊢ Irreducible p ↔ p ≠ 1 ∧ ∀ (f g : R[X]), Monic f → Monic g → f * g = p → natDegree f = 0 ∨ natDegree g = 0
[PROOFSTEP]
rw [irreducible_of_monic hp hp1, and_iff_right hp1]
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : Monic p
hp1 : ¬p = 1
⊢ (∀ (f g : R[X]), Monic f → Monic g → f * g = p → f = 1 ∨ g = 1) ↔
    ∀ (f g : R[X]), Monic f → Monic g → f * g = p → natDegree f = 0 ∨ natDegree g = 0
[PROOFSTEP]
refine' forall₄_congr fun a b ha hb => _
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : Monic p
hp1 : ¬p = 1
a b : R[X]
ha : Monic a
hb : Monic b
⊢ a * b = p → a = 1 ∨ b = 1 ↔ a * b = p → natDegree a = 0 ∨ natDegree b = 0
[PROOFSTEP]
rw [ha.natDegree_eq_zero_iff_eq_one, hb.natDegree_eq_zero_iff_eq_one]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : Monic p
⊢ Irreducible p ↔ p ≠ 1 ∧ ∀ (f g : R[X]), Monic f → Monic g → f * g = p → ¬natDegree g ∈ Ioc 0 (natDegree p / 2)
[PROOFSTEP]
simp_rw [hp.irreducible_iff_natDegree, mem_Ioc, Nat.le_div_iff_mul_le zero_lt_two, mul_two]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : Monic p
⊢ (p ≠ 1 ∧ ∀ (f g : R[X]), Monic f → Monic g → f * g = p → natDegree f = 0 ∨ natDegree g = 0) ↔
    p ≠ 1 ∧ ∀ (f g : R[X]), Monic f → Monic g → f * g = p → ¬(0 < natDegree g ∧ natDegree g + natDegree g ≤ natDegree p)
[PROOFSTEP]
apply and_congr_right'
[GOAL]
case h
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : Monic p
⊢ (∀ (f g : R[X]), Monic f → Monic g → f * g = p → natDegree f = 0 ∨ natDegree g = 0) ↔
    ∀ (f g : R[X]), Monic f → Monic g → f * g = p → ¬(0 < natDegree g ∧ natDegree g + natDegree g ≤ natDegree p)
[PROOFSTEP]
constructor
[GOAL]
case h.mp
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : Monic p
⊢ (∀ (f g : R[X]), Monic f → Monic g → f * g = p → natDegree f = 0 ∨ natDegree g = 0) →
    ∀ (f g : R[X]), Monic f → Monic g → f * g = p → ¬(0 < natDegree g ∧ natDegree g + natDegree g ≤ natDegree p)
[PROOFSTEP]
intro h f g hf hg he
[GOAL]
case h.mpr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : Monic p
⊢ (∀ (f g : R[X]), Monic f → Monic g → f * g = p → ¬(0 < natDegree g ∧ natDegree g + natDegree g ≤ natDegree p)) →
    ∀ (f g : R[X]), Monic f → Monic g → f * g = p → natDegree f = 0 ∨ natDegree g = 0
[PROOFSTEP]
intro h f g hf hg he
[GOAL]
case h.mp
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : Monic p
h : ∀ (f g : R[X]), Monic f → Monic g → f * g = p → natDegree f = 0 ∨ natDegree g = 0
f g : R[X]
hf : Monic f
hg : Monic g
he : f * g = p
⊢ ¬(0 < natDegree g ∧ natDegree g + natDegree g ≤ natDegree p)
[PROOFSTEP]
subst he
[GOAL]
case h.mpr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hp : Monic p
h : ∀ (f g : R[X]), Monic f → Monic g → f * g = p → ¬(0 < natDegree g ∧ natDegree g + natDegree g ≤ natDegree p)
f g : R[X]
hf : Monic f
hg : Monic g
he : f * g = p
⊢ natDegree f = 0 ∨ natDegree g = 0
[PROOFSTEP]
subst he
[GOAL]
case h.mp
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
q f g : R[X]
hf : Monic f
hg : Monic g
hp : Monic (f * g)
h : ∀ (f_1 g_1 : R[X]), Monic f_1 → Monic g_1 → f_1 * g_1 = f * g → natDegree f_1 = 0 ∨ natDegree g_1 = 0
⊢ ¬(0 < natDegree g ∧ natDegree g + natDegree g ≤ natDegree (f * g))
[PROOFSTEP]
rw [hf.natDegree_mul hg, add_le_add_iff_right]
[GOAL]
case h.mp
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
q f g : R[X]
hf : Monic f
hg : Monic g
hp : Monic (f * g)
h : ∀ (f_1 g_1 : R[X]), Monic f_1 → Monic g_1 → f_1 * g_1 = f * g → natDegree f_1 = 0 ∨ natDegree g_1 = 0
⊢ ¬(0 < natDegree g ∧ natDegree g ≤ natDegree f)
[PROOFSTEP]
exact fun ha => (h f g hf hg rfl).elim (ha.1.trans_le ha.2).ne' ha.1.ne'
[GOAL]
case h.mpr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
q f g : R[X]
hf : Monic f
hg : Monic g
hp : Monic (f * g)
h :
  ∀ (f_1 g_1 : R[X]),
    Monic f_1 → Monic g_1 → f_1 * g_1 = f * g → ¬(0 < natDegree g_1 ∧ natDegree g_1 + natDegree g_1 ≤ natDegree (f * g))
⊢ natDegree f = 0 ∨ natDegree g = 0
[PROOFSTEP]
simp_rw [hf.natDegree_mul hg, pos_iff_ne_zero] at h 
[GOAL]
case h.mpr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
q f g : R[X]
hf : Monic f
hg : Monic g
hp : Monic (f * g)
h :
  ∀ (f_1 g_1 : R[X]),
    Monic f_1 →
      Monic g_1 → f_1 * g_1 = f * g → ¬(natDegree g_1 ≠ 0 ∧ natDegree g_1 + natDegree g_1 ≤ natDegree f + natDegree g)
⊢ natDegree f = 0 ∨ natDegree g = 0
[PROOFSTEP]
contrapose! h
[GOAL]
case h.mpr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
q f g : R[X]
hf : Monic f
hg : Monic g
hp : Monic (f * g)
h : natDegree f ≠ 0 ∧ natDegree g ≠ 0
⊢ ∃ f_1 g_1,
    Monic f_1 ∧
      Monic g_1 ∧ f_1 * g_1 = f * g ∧ natDegree g_1 ≠ 0 ∧ natDegree g_1 + natDegree g_1 ≤ natDegree f + natDegree g
[PROOFSTEP]
obtain hl | hl := le_total f.natDegree g.natDegree
[GOAL]
case h.mpr.inl
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
q f g : R[X]
hf : Monic f
hg : Monic g
hp : Monic (f * g)
h : natDegree f ≠ 0 ∧ natDegree g ≠ 0
hl : natDegree f ≤ natDegree g
⊢ ∃ f_1 g_1,
    Monic f_1 ∧
      Monic g_1 ∧ f_1 * g_1 = f * g ∧ natDegree g_1 ≠ 0 ∧ natDegree g_1 + natDegree g_1 ≤ natDegree f + natDegree g
[PROOFSTEP]
exact ⟨g, f, hg, hf, mul_comm g f, h.1, add_le_add_left hl _⟩
[GOAL]
case h.mpr.inr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
q f g : R[X]
hf : Monic f
hg : Monic g
hp : Monic (f * g)
h : natDegree f ≠ 0 ∧ natDegree g ≠ 0
hl : natDegree g ≤ natDegree f
⊢ ∃ f_1 g_1,
    Monic f_1 ∧
      Monic g_1 ∧ f_1 * g_1 = f * g ∧ natDegree g_1 ≠ 0 ∧ natDegree g_1 + natDegree g_1 ≤ natDegree f + natDegree g
[PROOFSTEP]
exact ⟨f, g, hf, hg, rfl, h.2, add_le_add_right hl _⟩
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hm : Monic p
hnd : natDegree p = 2
⊢ ¬Irreducible p ↔ ∃ c₁ c₂, coeff p 0 = c₁ * c₂ ∧ coeff p 1 = c₁ + c₂
[PROOFSTEP]
cases subsingleton_or_nontrivial R
[GOAL]
case inl
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hm : Monic p
hnd : natDegree p = 2
h✝ : Subsingleton R
⊢ ¬Irreducible p ↔ ∃ c₁ c₂, coeff p 0 = c₁ * c₂ ∧ coeff p 1 = c₁ + c₂
[PROOFSTEP]
simp [natDegree_of_subsingleton] at hnd 
[GOAL]
case inr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hm : Monic p
hnd : natDegree p = 2
h✝ : Nontrivial R
⊢ ¬Irreducible p ↔ ∃ c₁ c₂, coeff p 0 = c₁ * c₂ ∧ coeff p 1 = c₁ + c₂
[PROOFSTEP]
rw [hm.irreducible_iff_natDegree', and_iff_right, hnd]
[GOAL]
case inr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hm : Monic p
hnd : natDegree p = 2
h✝ : Nontrivial R
⊢ (¬∀ (f g : R[X]), Monic f → Monic g → f * g = p → ¬natDegree g ∈ Ioc 0 (2 / 2)) ↔
    ∃ c₁ c₂, coeff p 0 = c₁ * c₂ ∧ coeff p 1 = c₁ + c₂
case inr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hm : Monic p
hnd : natDegree p = 2
h✝ : Nontrivial R
⊢ p ≠ 1
[PROOFSTEP]
push_neg
[GOAL]
case inr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hm : Monic p
hnd : natDegree p = 2
h✝ : Nontrivial R
⊢ (∃ f g, Monic f ∧ Monic g ∧ f * g = p ∧ natDegree g ∈ Ioc 0 (2 / 2)) ↔
    ∃ c₁ c₂, coeff p 0 = c₁ * c₂ ∧ coeff p 1 = c₁ + c₂
case inr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hm : Monic p
hnd : natDegree p = 2
h✝ : Nontrivial R
⊢ p ≠ 1
[PROOFSTEP]
constructor
[GOAL]
case inr.mp
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hm : Monic p
hnd : natDegree p = 2
h✝ : Nontrivial R
⊢ (∃ f g, Monic f ∧ Monic g ∧ f * g = p ∧ natDegree g ∈ Ioc 0 (2 / 2)) →
    ∃ c₁ c₂, coeff p 0 = c₁ * c₂ ∧ coeff p 1 = c₁ + c₂
[PROOFSTEP]
rintro ⟨a, b, ha, hb, rfl, hdb⟩
[GOAL]
case inr.mp.intro.intro.intro.intro.intro
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
q : R[X]
h✝ : Nontrivial R
a b : R[X]
ha : Monic a
hb : Monic b
hdb : natDegree b ∈ Ioc 0 (2 / 2)
hm : Monic (a * b)
hnd : natDegree (a * b) = 2
⊢ ∃ c₁ c₂, coeff (a * b) 0 = c₁ * c₂ ∧ coeff (a * b) 1 = c₁ + c₂
[PROOFSTEP]
simp only [zero_lt_two, Nat.div_self, ge_iff_le, Nat.Ioc_succ_singleton, zero_add, mem_singleton] at hdb 
[GOAL]
case inr.mp.intro.intro.intro.intro.intro
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
q : R[X]
h✝ : Nontrivial R
a b : R[X]
ha : Monic a
hb : Monic b
hm : Monic (a * b)
hnd : natDegree (a * b) = 2
hdb : natDegree b = 1
⊢ ∃ c₁ c₂, coeff (a * b) 0 = c₁ * c₂ ∧ coeff (a * b) 1 = c₁ + c₂
[PROOFSTEP]
have hda := hnd
[GOAL]
case inr.mp.intro.intro.intro.intro.intro
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
q : R[X]
h✝ : Nontrivial R
a b : R[X]
ha : Monic a
hb : Monic b
hm : Monic (a * b)
hnd : natDegree (a * b) = 2
hdb : natDegree b = 1
hda : natDegree (a * b) = 2
⊢ ∃ c₁ c₂, coeff (a * b) 0 = c₁ * c₂ ∧ coeff (a * b) 1 = c₁ + c₂
[PROOFSTEP]
rw [ha.natDegree_mul hb, hdb] at hda 
[GOAL]
case inr.mp.intro.intro.intro.intro.intro
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
q : R[X]
h✝ : Nontrivial R
a b : R[X]
ha : Monic a
hb : Monic b
hm : Monic (a * b)
hnd : natDegree (a * b) = 2
hdb : natDegree b = 1
hda : natDegree a + 1 = 2
⊢ ∃ c₁ c₂, coeff (a * b) 0 = c₁ * c₂ ∧ coeff (a * b) 1 = c₁ + c₂
[PROOFSTEP]
use a.coeff 0, b.coeff 0, mul_coeff_zero a b
[GOAL]
case right
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
q : R[X]
h✝ : Nontrivial R
a b : R[X]
ha : Monic a
hb : Monic b
hm : Monic (a * b)
hnd : natDegree (a * b) = 2
hdb : natDegree b = 1
hda : natDegree a + 1 = 2
⊢ coeff (a * b) 1 = coeff a 0 + coeff b 0
[PROOFSTEP]
simpa only [nextCoeff, hnd, add_right_cancel hda, hdb] using ha.nextCoeff_mul hb
[GOAL]
case inr.mpr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hm : Monic p
hnd : natDegree p = 2
h✝ : Nontrivial R
⊢ (∃ c₁ c₂, coeff p 0 = c₁ * c₂ ∧ coeff p 1 = c₁ + c₂) →
    ∃ f g, Monic f ∧ Monic g ∧ f * g = p ∧ natDegree g ∈ Ioc 0 (2 / 2)
[PROOFSTEP]
rintro ⟨c₁, c₂, hmul, hadd⟩
[GOAL]
case inr.mpr.intro.intro.intro
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hm : Monic p
hnd : natDegree p = 2
h✝ : Nontrivial R
c₁ c₂ : R
hmul : coeff p 0 = c₁ * c₂
hadd : coeff p 1 = c₁ + c₂
⊢ ∃ f g, Monic f ∧ Monic g ∧ f * g = p ∧ natDegree g ∈ Ioc 0 (2 / 2)
[PROOFSTEP]
refine ⟨X + C c₁, X + C c₂, monic_X_add_C _, monic_X_add_C _, ?_, ?_⟩
[GOAL]
case inr.mpr.intro.intro.intro.refine_1
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hm : Monic p
hnd : natDegree p = 2
h✝ : Nontrivial R
c₁ c₂ : R
hmul : coeff p 0 = c₁ * c₂
hadd : coeff p 1 = c₁ + c₂
⊢ (X + ↑C c₁) * (X + ↑C c₂) = p
[PROOFSTEP]
rw [p.as_sum_range_C_mul_X_pow, hnd, Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_one, ← hnd,
  hm.coeff_natDegree, hnd, hmul, hadd, C_mul, C_add, C_1]
[GOAL]
case inr.mpr.intro.intro.intro.refine_1
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hm : Monic p
hnd : natDegree p = 2
h✝ : Nontrivial R
c₁ c₂ : R
hmul : coeff p 0 = c₁ * c₂
hadd : coeff p 1 = c₁ + c₂
⊢ (X + ↑C c₁) * (X + ↑C c₂) = ↑C c₁ * ↑C c₂ * X ^ 0 + (↑C c₁ + ↑C c₂) * X ^ 1 + 1 * X ^ 2
[PROOFSTEP]
ring
[GOAL]
case inr.mpr.intro.intro.intro.refine_2
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hm : Monic p
hnd : natDegree p = 2
h✝ : Nontrivial R
c₁ c₂ : R
hmul : coeff p 0 = c₁ * c₂
hadd : coeff p 1 = c₁ + c₂
⊢ natDegree (X + ↑C c₂) ∈ Ioc 0 (2 / 2)
[PROOFSTEP]
rw [mem_Ioc, natDegree_X_add_C _]
[GOAL]
case inr.mpr.intro.intro.intro.refine_2
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hm : Monic p
hnd : natDegree p = 2
h✝ : Nontrivial R
c₁ c₂ : R
hmul : coeff p 0 = c₁ * c₂
hadd : coeff p 1 = c₁ + c₂
⊢ 0 < 1 ∧ 1 ≤ 2 / 2
[PROOFSTEP]
simp
[GOAL]
case inr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
hm : Monic p
hnd : natDegree p = 2
h✝ : Nontrivial R
⊢ p ≠ 1
[PROOFSTEP]
rintro rfl
[GOAL]
case inr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
q : R[X]
h✝ : Nontrivial R
hm : Monic 1
hnd : natDegree 1 = 2
⊢ False
[PROOFSTEP]
simp [natDegree_one] at hnd 
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommSemiring R
inst✝ : NoZeroDivisors R
p q : R[X]
⊢ IsRoot (p * q) a ↔ IsRoot p a ∨ IsRoot q a
[PROOFSTEP]
simp_rw [IsRoot, eval_mul, mul_eq_zero]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝ : CommRing R
p : R[X]
p0 : p ≠ 0
a : R
n : ℕ
⊢ n ≤ rootMultiplicity a p ↔ (X - ↑C a) ^ n ∣ p
[PROOFSTEP]
classical
rw [rootMultiplicity_eq_nat_find_of_nonzero p0, Nat.le_find_iff]
simp_rw [Classical.not_not]
refine ⟨fun h => ?_, fun h m hm => (pow_dvd_pow _ hm).trans h⟩
cases' n with n;
· rw [pow_zero]
  apply one_dvd;
· exact h n n.lt_succ_self
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝ : CommRing R
p : R[X]
p0 : p ≠ 0
a : R
n : ℕ
⊢ n ≤ rootMultiplicity a p ↔ (X - ↑C a) ^ n ∣ p
[PROOFSTEP]
rw [rootMultiplicity_eq_nat_find_of_nonzero p0, Nat.le_find_iff]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝ : CommRing R
p : R[X]
p0 : p ≠ 0
a : R
n : ℕ
⊢ (∀ (m : ℕ), m < n → ¬¬(X - ↑C a) ^ (m + 1) ∣ p) ↔ (X - ↑C a) ^ n ∣ p
[PROOFSTEP]
simp_rw [Classical.not_not]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝ : CommRing R
p : R[X]
p0 : p ≠ 0
a : R
n : ℕ
⊢ (∀ (m : ℕ), m < n → (X - ↑C a) ^ (m + 1) ∣ p) ↔ (X - ↑C a) ^ n ∣ p
[PROOFSTEP]
refine ⟨fun h => ?_, fun h m hm => (pow_dvd_pow _ hm).trans h⟩
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝ : CommRing R
p : R[X]
p0 : p ≠ 0
a : R
n : ℕ
h : ∀ (m : ℕ), m < n → (X - ↑C a) ^ (m + 1) ∣ p
⊢ (X - ↑C a) ^ n ∣ p
[PROOFSTEP]
cases' n with n
[GOAL]
case zero
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝ : CommRing R
p : R[X]
p0 : p ≠ 0
a : R
h : ∀ (m : ℕ), m < Nat.zero → (X - ↑C a) ^ (m + 1) ∣ p
⊢ (X - ↑C a) ^ Nat.zero ∣ p
[PROOFSTEP]
rw [pow_zero]
[GOAL]
case zero
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝ : CommRing R
p : R[X]
p0 : p ≠ 0
a : R
h : ∀ (m : ℕ), m < Nat.zero → (X - ↑C a) ^ (m + 1) ∣ p
⊢ 1 ∣ p
[PROOFSTEP]
apply one_dvd
[GOAL]
case succ
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝ : CommRing R
p : R[X]
p0 : p ≠ 0
a : R
n : ℕ
h : ∀ (m : ℕ), m < Nat.succ n → (X - ↑C a) ^ (m + 1) ∣ p
⊢ (X - ↑C a) ^ Nat.succ n ∣ p
[PROOFSTEP]
exact h n n.lt_succ_self
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝ : CommRing R
p : R[X]
p0 : p ≠ 0
a : R
n : ℕ
⊢ rootMultiplicity a p ≤ n ↔ ¬(X - ↑C a) ^ (n + 1) ∣ p
[PROOFSTEP]
rw [← (le_rootMultiplicity_iff p0).not, not_le, Nat.lt_add_one_iff]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝ : CommRing R
p : R[X]
p0 : p ≠ 0
a : R
⊢ ¬(X - ↑C a) ^ (rootMultiplicity a p + 1) ∣ p
[PROOFSTEP]
rw [← rootMultiplicity_le_iff p0]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝ : CommRing R
p q : R[X]
a : R
hzero : p + q ≠ 0
⊢ min (rootMultiplicity a p) (rootMultiplicity a q) ≤ rootMultiplicity a (p + q)
[PROOFSTEP]
rw [le_rootMultiplicity_iff hzero]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝ : CommRing R
p q : R[X]
a : R
hzero : p + q ≠ 0
⊢ (X - ↑C a) ^ min (rootMultiplicity a p) (rootMultiplicity a q) ∣ p + q
[PROOFSTEP]
have hdivp : (X - C a) ^ rootMultiplicity a p ∣ p := pow_rootMultiplicity_dvd p a
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝ : CommRing R
p q : R[X]
a : R
hzero : p + q ≠ 0
hdivp : (X - ↑C a) ^ rootMultiplicity a p ∣ p
⊢ (X - ↑C a) ^ min (rootMultiplicity a p) (rootMultiplicity a q) ∣ p + q
[PROOFSTEP]
have hdivq : (X - C a) ^ rootMultiplicity a q ∣ q := pow_rootMultiplicity_dvd q a
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝ : CommRing R
p q : R[X]
a : R
hzero : p + q ≠ 0
hdivp : (X - ↑C a) ^ rootMultiplicity a p ∣ p
hdivq : (X - ↑C a) ^ rootMultiplicity a q ∣ q
⊢ (X - ↑C a) ^ min (rootMultiplicity a p) (rootMultiplicity a q) ∣ p + q
[PROOFSTEP]
exact min_pow_dvd_add hdivp hdivq
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
r : R
x✝¹ x✝ : R[X]
⊢ X - ↑C r ∣ x✝¹ * x✝ → X - ↑C r ∣ x✝¹ ∨ X - ↑C r ∣ x✝
[PROOFSTEP]
simp_rw [dvd_iff_isRoot, IsRoot.def, eval_mul, mul_eq_zero]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
r : R
x✝¹ x✝ : R[X]
⊢ eval r x✝¹ = 0 ∨ eval r x✝ = 0 → eval r x✝¹ = 0 ∨ eval r x✝ = 0
[PROOFSTEP]
exact id
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
⊢ Prime X
[PROOFSTEP]
convert prime_X_sub_C (0 : R)
[GOAL]
case h.e'_3
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
⊢ X = X - ↑C 0
[PROOFSTEP]
simp
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hp1 : degree p = 1
hm : Monic p
⊢ p = X - ↑C (-coeff p 0)
[PROOFSTEP]
simpa [hm.leadingCoeff] using eq_X_add_C_of_degree_eq_one hp1
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hp : Monic p
hq : Monic q
hpq : Associated p q
⊢ p = q
[PROOFSTEP]
obtain ⟨u, hu⟩ := hpq
[GOAL]
case intro
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hp : Monic p
hq : Monic q
u : R[X]ˣ
hu : p * ↑u = q
⊢ p = q
[PROOFSTEP]
unfold Monic at hp hq 
[GOAL]
case intro
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hp : leadingCoeff p = 1
hq : leadingCoeff q = 1
u : R[X]ˣ
hu : p * ↑u = q
⊢ p = q
[PROOFSTEP]
rw [eq_C_of_degree_le_zero (degree_coe_units _).le] at hu 
[GOAL]
case intro
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hp : leadingCoeff p = 1
hq : leadingCoeff q = 1
u : R[X]ˣ
hu : p * ↑C (coeff (↑u) 0) = q
⊢ p = q
[PROOFSTEP]
rw [← hu, leadingCoeff_mul, hp, one_mul, leadingCoeff_C] at hq 
[GOAL]
case intro
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hp : leadingCoeff p = 1
u : R[X]ˣ
hq : coeff (↑u) 0 = 1
hu : p * ↑C (coeff (↑u) 0) = q
⊢ p = q
[PROOFSTEP]
rwa [hq, C_1, mul_one] at hu 
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
x : R
hpq : p * q ≠ 0
⊢ rootMultiplicity x (p * q) = rootMultiplicity x p + rootMultiplicity x q
[PROOFSTEP]
classical
have hp : p ≠ 0 := left_ne_zero_of_mul hpq
have hq : q ≠ 0 := right_ne_zero_of_mul hpq
rw [rootMultiplicity_eq_multiplicity (p * q), dif_neg hpq, rootMultiplicity_eq_multiplicity p, dif_neg hp,
  rootMultiplicity_eq_multiplicity q, dif_neg hq, multiplicity.mul' (prime_X_sub_C x)]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
x : R
hpq : p * q ≠ 0
⊢ rootMultiplicity x (p * q) = rootMultiplicity x p + rootMultiplicity x q
[PROOFSTEP]
have hp : p ≠ 0 := left_ne_zero_of_mul hpq
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
x : R
hpq : p * q ≠ 0
hp : p ≠ 0
⊢ rootMultiplicity x (p * q) = rootMultiplicity x p + rootMultiplicity x q
[PROOFSTEP]
have hq : q ≠ 0 := right_ne_zero_of_mul hpq
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
x : R
hpq : p * q ≠ 0
hp : p ≠ 0
hq : q ≠ 0
⊢ rootMultiplicity x (p * q) = rootMultiplicity x p + rootMultiplicity x q
[PROOFSTEP]
rw [rootMultiplicity_eq_multiplicity (p * q), dif_neg hpq, rootMultiplicity_eq_multiplicity p, dif_neg hp,
  rootMultiplicity_eq_multiplicity q, dif_neg hq, multiplicity.mul' (prime_X_sub_C x)]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
x : R
⊢ rootMultiplicity x (X - ↑C x) = 1
[PROOFSTEP]
classical rw [rootMultiplicity_eq_multiplicity, dif_neg (X_sub_C_ne_zero x), multiplicity.get_multiplicity_self]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
x : R
⊢ rootMultiplicity x (X - ↑C x) = 1
[PROOFSTEP]
rw [rootMultiplicity_eq_multiplicity, dif_neg (X_sub_C_ne_zero x), multiplicity.get_multiplicity_self]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p q : R[X]
inst✝ : DecidableEq R
x y : R
⊢ rootMultiplicity x (X - ↑C y) = if x = y then 1 else 0
[PROOFSTEP]
split_ifs with hxy
[GOAL]
case pos
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p q : R[X]
inst✝ : DecidableEq R
x y : R
hxy : x = y
⊢ rootMultiplicity x (X - ↑C y) = 1
[PROOFSTEP]
rw [hxy]
[GOAL]
case pos
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p q : R[X]
inst✝ : DecidableEq R
x y : R
hxy : x = y
⊢ rootMultiplicity y (X - ↑C y) = 1
[PROOFSTEP]
exact rootMultiplicity_X_sub_C_self
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p q : R[X]
inst✝ : DecidableEq R
x y : R
hxy : ¬x = y
⊢ rootMultiplicity x (X - ↑C y) = 0
[PROOFSTEP]
exact rootMultiplicity_eq_zero (mt root_X_sub_C.mp (Ne.symm hxy))
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
a : R
n : ℕ
⊢ rootMultiplicity a ((X - ↑C a) ^ n) = n
[PROOFSTEP]
induction' n with n hn
[GOAL]
case zero
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
a : R
⊢ rootMultiplicity a ((X - ↑C a) ^ Nat.zero) = Nat.zero
[PROOFSTEP]
refine' rootMultiplicity_eq_zero _
[GOAL]
case zero
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
a : R
⊢ ¬IsRoot ((X - ↑C a) ^ Nat.zero) a
[PROOFSTEP]
simp only [eval_one, IsRoot.def, not_false_iff, one_ne_zero, pow_zero, Nat.zero_eq]
[GOAL]
case succ
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
a : R
n : ℕ
hn : rootMultiplicity a ((X - ↑C a) ^ n) = n
⊢ rootMultiplicity a ((X - ↑C a) ^ Nat.succ n) = Nat.succ n
[PROOFSTEP]
have hzero := pow_ne_zero n.succ (X_sub_C_ne_zero a)
[GOAL]
case succ
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
a : R
n : ℕ
hn : rootMultiplicity a ((X - ↑C a) ^ n) = n
hzero : (X - ↑C a) ^ Nat.succ n ≠ 0
⊢ rootMultiplicity a ((X - ↑C a) ^ Nat.succ n) = Nat.succ n
[PROOFSTEP]
rw [pow_succ (X - C a) n] at hzero ⊢
[GOAL]
case succ
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
a : R
n : ℕ
hn : rootMultiplicity a ((X - ↑C a) ^ n) = n
hzero : (X - ↑C a) * (X - ↑C a) ^ n ≠ 0
⊢ rootMultiplicity a ((X - ↑C a) * (X - ↑C a) ^ n) = Nat.succ n
[PROOFSTEP]
simp only [rootMultiplicity_mul hzero, rootMultiplicity_X_sub_C_self, hn, Nat.one_add]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h✝ : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
h : p /ₘ (X - ↑C x) = 0
⊢ False
[PROOFSTEP]
rw [← mul_divByMonic_eq_iff_isRoot.2 hx, h, mul_zero] at hp 
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
this : Decidable (∃ x, IsRoot p x)
h✝ : ∃ x, IsRoot p x
x : R
hp : 0 ≠ 0
hx : IsRoot p x
hpd : 0 < degree p
h : p /ₘ (X - ↑C x) = 0
⊢ False
[PROOFSTEP]
exact hp rfl
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
⊢ 0 < 1
[PROOFSTEP]
decide
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
t : Multiset R
htd : ↑(↑Multiset.card t) ≤ degree (p /ₘ (X - ↑C x))
htr : ∀ (a : R), count a t = rootMultiplicity a (p /ₘ (X - ↑C x))
⊢ degree (X - ↑C x) ≤ degree p
[PROOFSTEP]
rw [degree_X_sub_C, degree_eq_natDegree hp]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
t : Multiset R
htd : ↑(↑Multiset.card t) ≤ degree (p /ₘ (X - ↑C x))
htr : ∀ (a : R), count a t = rootMultiplicity a (p /ₘ (X - ↑C x))
⊢ 1 ≤ ↑(natDegree p)
[PROOFSTEP]
rw [degree_eq_natDegree hp] at hpd 
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < ↑(natDegree p)
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
t : Multiset R
htd : ↑(↑Multiset.card t) ≤ degree (p /ₘ (X - ↑C x))
htr : ∀ (a : R), count a t = rootMultiplicity a (p /ₘ (X - ↑C x))
⊢ 1 ≤ ↑(natDegree p)
[PROOFSTEP]
exact WithBot.coe_le_coe.2 (WithBot.coe_lt_coe.1 hpd)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
t : Multiset R
htd : ↑(↑Multiset.card t) ≤ degree (p /ₘ (X - ↑C x))
htr : ∀ (a : R), count a t = rootMultiplicity a (p /ₘ (X - ↑C x))
hdeg : degree (X - ↑C x) ≤ degree p
hdiv0 : p /ₘ (X - ↑C x) ≠ 0
⊢ ↑(↑Multiset.card (x ::ₘ t)) = ↑(↑Multiset.card t) + 1
[PROOFSTEP]
congr
[GOAL]
case e_a
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
t : Multiset R
htd : ↑(↑Multiset.card t) ≤ degree (p /ₘ (X - ↑C x))
htr : ∀ (a : R), count a t = rootMultiplicity a (p /ₘ (X - ↑C x))
hdeg : degree (X - ↑C x) ≤ degree p
hdiv0 : p /ₘ (X - ↑C x) ≠ 0
⊢ ↑Multiset.card (x ::ₘ t) = Add.add (↑(↑Multiset.card t)) 1
[PROOFSTEP]
exact_mod_cast Multiset.card_cons _ _
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
t : Multiset R
htd : ↑(↑Multiset.card t) ≤ degree (p /ₘ (X - ↑C x))
htr : ∀ (a : R), count a t = rootMultiplicity a (p /ₘ (X - ↑C x))
hdeg : degree (X - ↑C x) ≤ degree p
hdiv0 : p /ₘ (X - ↑C x) ≠ 0
⊢ ↑(↑Multiset.card t) + 1 ≤ degree p
[PROOFSTEP]
rw [← degree_add_divByMonic (monic_X_sub_C x) hdeg, degree_X_sub_C, add_comm]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
t : Multiset R
htd : ↑(↑Multiset.card t) ≤ degree (p /ₘ (X - ↑C x))
htr : ∀ (a : R), count a t = rootMultiplicity a (p /ₘ (X - ↑C x))
hdeg : degree (X - ↑C x) ≤ degree p
hdiv0 : p /ₘ (X - ↑C x) ≠ 0
⊢ 1 + ↑(↑Multiset.card t) ≤ 1 + degree (p /ₘ (X - ↑C x))
[PROOFSTEP]
exact add_le_add (le_refl (1 : WithBot ℕ)) htd
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
t : Multiset R
htd : ↑(↑Multiset.card t) ≤ degree (p /ₘ (X - ↑C x))
htr : ∀ (a : R), count a t = rootMultiplicity a (p /ₘ (X - ↑C x))
hdeg : degree (X - ↑C x) ≤ degree p
hdiv0 : p /ₘ (X - ↑C x) ≠ 0
⊢ ∀ (a : R), count a (x ::ₘ t) = rootMultiplicity a p
[PROOFSTEP]
change ∀ (a : R), count a (x ::ₘ t) = rootMultiplicity a p
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
t : Multiset R
htd : ↑(↑Multiset.card t) ≤ degree (p /ₘ (X - ↑C x))
htr : ∀ (a : R), count a t = rootMultiplicity a (p /ₘ (X - ↑C x))
hdeg : degree (X - ↑C x) ≤ degree p
hdiv0 : p /ₘ (X - ↑C x) ≠ 0
⊢ ∀ (a : R), count a (x ::ₘ t) = rootMultiplicity a p
[PROOFSTEP]
intro a
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
t : Multiset R
htd : ↑(↑Multiset.card t) ≤ degree (p /ₘ (X - ↑C x))
htr : ∀ (a : R), count a t = rootMultiplicity a (p /ₘ (X - ↑C x))
hdeg : degree (X - ↑C x) ≤ degree p
hdiv0 : p /ₘ (X - ↑C x) ≠ 0
a : R
⊢ count a (x ::ₘ t) = rootMultiplicity a p
[PROOFSTEP]
conv_rhs => rw [← mul_divByMonic_eq_iff_isRoot.mpr hx]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
t : Multiset R
htd : ↑(↑Multiset.card t) ≤ degree (p /ₘ (X - ↑C x))
htr : ∀ (a : R), count a t = rootMultiplicity a (p /ₘ (X - ↑C x))
hdeg : degree (X - ↑C x) ≤ degree p
hdiv0 : p /ₘ (X - ↑C x) ≠ 0
a : R
| rootMultiplicity a p
[PROOFSTEP]
rw [← mul_divByMonic_eq_iff_isRoot.mpr hx]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
t : Multiset R
htd : ↑(↑Multiset.card t) ≤ degree (p /ₘ (X - ↑C x))
htr : ∀ (a : R), count a t = rootMultiplicity a (p /ₘ (X - ↑C x))
hdeg : degree (X - ↑C x) ≤ degree p
hdiv0 : p /ₘ (X - ↑C x) ≠ 0
a : R
| rootMultiplicity a p
[PROOFSTEP]
rw [← mul_divByMonic_eq_iff_isRoot.mpr hx]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
t : Multiset R
htd : ↑(↑Multiset.card t) ≤ degree (p /ₘ (X - ↑C x))
htr : ∀ (a : R), count a t = rootMultiplicity a (p /ₘ (X - ↑C x))
hdeg : degree (X - ↑C x) ≤ degree p
hdiv0 : p /ₘ (X - ↑C x) ≠ 0
a : R
| rootMultiplicity a p
[PROOFSTEP]
rw [← mul_divByMonic_eq_iff_isRoot.mpr hx]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
t : Multiset R
htd : ↑(↑Multiset.card t) ≤ degree (p /ₘ (X - ↑C x))
htr : ∀ (a : R), count a t = rootMultiplicity a (p /ₘ (X - ↑C x))
hdeg : degree (X - ↑C x) ≤ degree p
hdiv0 : p /ₘ (X - ↑C x) ≠ 0
a : R
⊢ count a (x ::ₘ t) = rootMultiplicity a ((X - ↑C x) * (p /ₘ (X - ↑C x)))
[PROOFSTEP]
rw [rootMultiplicity_mul (mul_ne_zero (X_sub_C_ne_zero x) hdiv0), rootMultiplicity_X_sub_C, ← htr a]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
t : Multiset R
htd : ↑(↑Multiset.card t) ≤ degree (p /ₘ (X - ↑C x))
htr : ∀ (a : R), count a t = rootMultiplicity a (p /ₘ (X - ↑C x))
hdeg : degree (X - ↑C x) ≤ degree p
hdiv0 : p /ₘ (X - ↑C x) ≠ 0
a : R
⊢ count a (x ::ₘ t) = (if a = x then 1 else 0) + count a t
[PROOFSTEP]
split_ifs with ha
[GOAL]
case pos
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
t : Multiset R
htd : ↑(↑Multiset.card t) ≤ degree (p /ₘ (X - ↑C x))
htr : ∀ (a : R), count a t = rootMultiplicity a (p /ₘ (X - ↑C x))
hdeg : degree (X - ↑C x) ≤ degree p
hdiv0 : p /ₘ (X - ↑C x) ≠ 0
a : R
ha : a = x
⊢ count a (x ::ₘ t) = 1 + count a t
[PROOFSTEP]
rw [ha, count_cons_self, add_comm]
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
t : Multiset R
htd : ↑(↑Multiset.card t) ≤ degree (p /ₘ (X - ↑C x))
htr : ∀ (a : R), count a t = rootMultiplicity a (p /ₘ (X - ↑C x))
hdeg : degree (X - ↑C x) ≤ degree p
hdiv0 : p /ₘ (X - ↑C x) ≠ 0
a : R
ha : ¬a = x
⊢ count a (x ::ₘ t) = 0 + count a t
[PROOFSTEP]
rw [count_cons_of_ne ha, zero_add]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ¬∃ x, IsRoot p x
⊢ ∀ (a : R), count a 0 = rootMultiplicity a p
[PROOFSTEP]
intro a
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p ≠ 0
this : Decidable (∃ x, IsRoot p x)
h : ¬∃ x, IsRoot p x
a : R
⊢ count a 0 = rootMultiplicity a p
[PROOFSTEP]
rw [count_zero, rootMultiplicity_eq_zero (not_exists.mp h a)]
[GOAL]
R : Type u
inst✝² : CommRing R
inst✝¹ : IsDomain R
inst✝ : DecidableEq R
_x✝ : (x : R[X]) ×' x ≠ 0
a✝¹ :
  ∀ (y : (x : R[X]) ×' x ≠ 0),
    (invImage (fun a => PSigma.casesOn a fun p snd => natDegree p) instWellFoundedRelation).1 y _x✝ →
      ∃ s, ↑(↑Multiset.card s) ≤ degree y.1 ∧ ∀ (a : R), count a s = rootMultiplicity a y.1
x✝² : R[X]
x✝¹ : x✝² ≠ 0
a✝ :
  ∀ (y : (x : R[X]) ×' x ≠ 0),
    (invImage (fun a => PSigma.casesOn a fun p snd => natDegree p) instWellFoundedRelation).1 y
        { fst := x✝², snd := x✝¹ } →
      ∃ s, ↑(↑Multiset.card s) ≤ degree y.1 ∧ ∀ (a : R), count a s = rootMultiplicity a y.1
p : R[X]
hp : p ≠ 0
x✝ :
  ∀ (y : (x : R[X]) ×' x ≠ 0),
    (invImage (fun a => PSigma.casesOn a fun p snd => natDegree p) instWellFoundedRelation).1 y
        { fst := p, snd := hp } →
      ∃ s, ↑(↑Multiset.card s) ≤ degree y.1 ∧ ∀ (a : R), count a s = rootMultiplicity a y.1
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
⊢ (invImage (fun a => PSigma.casesOn a fun p snd => natDegree p) instWellFoundedRelation).1
    { fst := p /ₘ (X - ↑C x), snd := hd0 } { fst := p, snd := hp }
[PROOFSTEP]
{ simp_wf
  apply WithBot.coe_lt_coe.mp
  simp only [degree_eq_natDegree hp, degree_eq_natDegree hd0, ← Nat.cast_withBot] at wf ; assumption
}
[GOAL]
R : Type u
inst✝² : CommRing R
inst✝¹ : IsDomain R
inst✝ : DecidableEq R
_x✝ : (x : R[X]) ×' x ≠ 0
a✝¹ :
  ∀ (y : (x : R[X]) ×' x ≠ 0),
    (invImage (fun a => PSigma.casesOn a fun p snd => natDegree p) instWellFoundedRelation).1 y _x✝ →
      ∃ s, ↑(↑Multiset.card s) ≤ degree y.1 ∧ ∀ (a : R), count a s = rootMultiplicity a y.1
x✝² : R[X]
x✝¹ : x✝² ≠ 0
a✝ :
  ∀ (y : (x : R[X]) ×' x ≠ 0),
    (invImage (fun a => PSigma.casesOn a fun p snd => natDegree p) instWellFoundedRelation).1 y
        { fst := x✝², snd := x✝¹ } →
      ∃ s, ↑(↑Multiset.card s) ≤ degree y.1 ∧ ∀ (a : R), count a s = rootMultiplicity a y.1
p : R[X]
hp : p ≠ 0
x✝ :
  ∀ (y : (x : R[X]) ×' x ≠ 0),
    (invImage (fun a => PSigma.casesOn a fun p snd => natDegree p) instWellFoundedRelation).1 y
        { fst := p, snd := hp } →
      ∃ s, ↑(↑Multiset.card s) ≤ degree y.1 ∧ ∀ (a : R), count a s = rootMultiplicity a y.1
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
⊢ (invImage (fun a => PSigma.casesOn a fun p snd => natDegree p) instWellFoundedRelation).1
    { fst := p /ₘ (X - ↑C x), snd := hd0 } { fst := p, snd := hp }
[PROOFSTEP]
simp_wf
[GOAL]
R : Type u
inst✝² : CommRing R
inst✝¹ : IsDomain R
inst✝ : DecidableEq R
_x✝ : (x : R[X]) ×' x ≠ 0
a✝¹ :
  ∀ (y : (x : R[X]) ×' x ≠ 0),
    (invImage (fun a => PSigma.casesOn a fun p snd => natDegree p) instWellFoundedRelation).1 y _x✝ →
      ∃ s, ↑(↑Multiset.card s) ≤ degree y.1 ∧ ∀ (a : R), count a s = rootMultiplicity a y.1
x✝² : R[X]
x✝¹ : x✝² ≠ 0
a✝ :
  ∀ (y : (x : R[X]) ×' x ≠ 0),
    (invImage (fun a => PSigma.casesOn a fun p snd => natDegree p) instWellFoundedRelation).1 y
        { fst := x✝², snd := x✝¹ } →
      ∃ s, ↑(↑Multiset.card s) ≤ degree y.1 ∧ ∀ (a : R), count a s = rootMultiplicity a y.1
p : R[X]
hp : p ≠ 0
x✝ :
  ∀ (y : (x : R[X]) ×' x ≠ 0),
    (invImage (fun a => PSigma.casesOn a fun p snd => natDegree p) instWellFoundedRelation).1 y
        { fst := p, snd := hp } →
      ∃ s, ↑(↑Multiset.card s) ≤ degree y.1 ∧ ∀ (a : R), count a s = rootMultiplicity a y.1
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
⊢ natDegree (p /ₘ (X - ↑C x)) < natDegree p
[PROOFSTEP]
apply WithBot.coe_lt_coe.mp
[GOAL]
R : Type u
inst✝² : CommRing R
inst✝¹ : IsDomain R
inst✝ : DecidableEq R
_x✝ : (x : R[X]) ×' x ≠ 0
a✝¹ :
  ∀ (y : (x : R[X]) ×' x ≠ 0),
    (invImage (fun a => PSigma.casesOn a fun p snd => natDegree p) instWellFoundedRelation).1 y _x✝ →
      ∃ s, ↑(↑Multiset.card s) ≤ degree y.1 ∧ ∀ (a : R), count a s = rootMultiplicity a y.1
x✝² : R[X]
x✝¹ : x✝² ≠ 0
a✝ :
  ∀ (y : (x : R[X]) ×' x ≠ 0),
    (invImage (fun a => PSigma.casesOn a fun p snd => natDegree p) instWellFoundedRelation).1 y
        { fst := x✝², snd := x✝¹ } →
      ∃ s, ↑(↑Multiset.card s) ≤ degree y.1 ∧ ∀ (a : R), count a s = rootMultiplicity a y.1
p : R[X]
hp : p ≠ 0
x✝ :
  ∀ (y : (x : R[X]) ×' x ≠ 0),
    (invImage (fun a => PSigma.casesOn a fun p snd => natDegree p) instWellFoundedRelation).1 y
        { fst := p, snd := hp } →
      ∃ s, ↑(↑Multiset.card s) ≤ degree y.1 ∧ ∀ (a : R), count a s = rootMultiplicity a y.1
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : degree (p /ₘ (X - ↑C x)) < degree p
⊢ ↑(natDegree (p /ₘ (X - ↑C x))) < ↑(natDegree p)
[PROOFSTEP]
simp only [degree_eq_natDegree hp, degree_eq_natDegree hd0, ← Nat.cast_withBot] at wf 
[GOAL]
R : Type u
inst✝² : CommRing R
inst✝¹ : IsDomain R
inst✝ : DecidableEq R
_x✝ : (x : R[X]) ×' x ≠ 0
a✝¹ :
  ∀ (y : (x : R[X]) ×' x ≠ 0),
    (invImage (fun a => PSigma.casesOn a fun p snd => natDegree p) instWellFoundedRelation).1 y _x✝ →
      ∃ s, ↑(↑Multiset.card s) ≤ degree y.1 ∧ ∀ (a : R), count a s = rootMultiplicity a y.1
x✝² : R[X]
x✝¹ : x✝² ≠ 0
a✝ :
  ∀ (y : (x : R[X]) ×' x ≠ 0),
    (invImage (fun a => PSigma.casesOn a fun p snd => natDegree p) instWellFoundedRelation).1 y
        { fst := x✝², snd := x✝¹ } →
      ∃ s, ↑(↑Multiset.card s) ≤ degree y.1 ∧ ∀ (a : R), count a s = rootMultiplicity a y.1
p : R[X]
hp : p ≠ 0
x✝ :
  ∀ (y : (x : R[X]) ×' x ≠ 0),
    (invImage (fun a => PSigma.casesOn a fun p snd => natDegree p) instWellFoundedRelation).1 y
        { fst := p, snd := hp } →
      ∃ s, ↑(↑Multiset.card s) ≤ degree y.1 ∧ ∀ (a : R), count a s = rootMultiplicity a y.1
h : ∃ x, IsRoot p x
x : R
hx : IsRoot p x
hpd : 0 < degree p
hd0 : p /ₘ (X - ↑C x) ≠ 0
wf : ↑(natDegree (p /ₘ (X - ↑C x))) < ↑(natDegree p)
⊢ ↑(natDegree (p /ₘ (X - ↑C x))) < ↑(natDegree p)
[PROOFSTEP]
assumption
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝³ : CommRing R
inst✝² : IsDomain R
p✝ q : R[X]
inst✝¹ : DecidableEq R
p : R[X]
inst✝ : Decidable (p = 0)
⊢ roots p =
    if h : p = 0 then ∅
    else Classical.choose (_ : ∃ s, ↑(↑Multiset.card s) ≤ degree p ∧ ∀ (a : R), count a s = rootMultiplicity a p)
[PROOFSTEP]
rename_i iR ip0
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q : R[X]
iR : DecidableEq R
p : R[X]
ip0 : Decidable (p = 0)
⊢ roots p =
    if h : p = 0 then ∅
    else Classical.choose (_ : ∃ s, ↑(↑Multiset.card s) ≤ degree p ∧ ∀ (a : R), count a s = rootMultiplicity a p)
[PROOFSTEP]
obtain rfl := Subsingleton.elim iR (Classical.decEq R)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
ip0 : Decidable (p = 0)
⊢ roots p =
    if h : p = 0 then ∅
    else Classical.choose (_ : ∃ s, ↑(↑Multiset.card s) ≤ degree p ∧ ∀ (a : R), count a s = rootMultiplicity a p)
[PROOFSTEP]
obtain rfl := Subsingleton.elim ip0 (Classical.dec (p = 0))
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
⊢ roots p =
    if h : p = 0 then ∅
    else Classical.choose (_ : ∃ s, ↑(↑Multiset.card s) ≤ degree p ∧ ∀ (a : R), count a s = rootMultiplicity a p)
[PROOFSTEP]
rfl
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hp0 : p ≠ 0
⊢ ↑(↑Multiset.card (roots p)) ≤ degree p
[PROOFSTEP]
classical
unfold roots
rw [dif_neg hp0]
exact (Classical.choose_spec (exists_multiset_roots hp0)).1
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hp0 : p ≠ 0
⊢ ↑(↑Multiset.card (roots p)) ≤ degree p
[PROOFSTEP]
unfold roots
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hp0 : p ≠ 0
⊢ ↑(↑Multiset.card
        (if h : p = 0 then ∅
        else
          Classical.choose (_ : ∃ s, ↑(↑Multiset.card s) ≤ degree p ∧ ∀ (a : R), count a s = rootMultiplicity a p))) ≤
    degree p
[PROOFSTEP]
rw [dif_neg hp0]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hp0 : p ≠ 0
⊢ ↑(↑Multiset.card
        (Classical.choose (_ : ∃ s, ↑(↑Multiset.card s) ≤ degree p ∧ ∀ (a : R), count a s = rootMultiplicity a p))) ≤
    degree p
[PROOFSTEP]
exact (Classical.choose_spec (exists_multiset_roots hp0)).1
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
⊢ ↑Multiset.card (roots p) ≤ natDegree p
[PROOFSTEP]
by_cases hp0 : p = 0
[GOAL]
case pos
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
hp0 : p = 0
⊢ ↑Multiset.card (roots p) ≤ natDegree p
[PROOFSTEP]
simp [hp0]
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
hp0 : ¬p = 0
⊢ ↑Multiset.card (roots p) ≤ natDegree p
[PROOFSTEP]
exact WithBot.coe_le_coe.1 (le_trans (card_roots hp0) (le_of_eq <| degree_eq_natDegree hp0))
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
a : R
hp0 : 0 < degree p
⊢ degree (p - ↑C a) = degree p
[PROOFSTEP]
rw [sub_eq_add_neg, ← C_neg]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
a : R
hp0 : 0 < degree p
⊢ degree (p + ↑C (-a)) = degree p
[PROOFSTEP]
exact degree_add_C hp0
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
a : R
hp0 : 0 < degree p
h : p = 0
⊢ False
[PROOFSTEP]
simp_all [lt_irrefl]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
⊢ count a (roots p) = rootMultiplicity a p
[PROOFSTEP]
classical
by_cases hp : p = 0
· simp [hp]
rw [roots_def, dif_neg hp]
exact (Classical.choose_spec (exists_multiset_roots hp)).2 a
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
⊢ count a (roots p) = rootMultiplicity a p
[PROOFSTEP]
by_cases hp : p = 0
[GOAL]
case pos
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : p = 0
⊢ count a (roots p) = rootMultiplicity a p
[PROOFSTEP]
simp [hp]
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : ¬p = 0
⊢ count a (roots p) = rootMultiplicity a p
[PROOFSTEP]
rw [roots_def, dif_neg hp]
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : DecidableEq R
p : R[X]
hp : ¬p = 0
⊢ count a (Classical.choose (_ : ∃ s, ↑(↑Multiset.card s) ≤ degree p ∧ ∀ (a : R), count a s = rootMultiplicity a p)) =
    rootMultiplicity a p
[PROOFSTEP]
exact (Classical.choose_spec (exists_multiset_roots hp)).2 a
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
⊢ a ∈ roots p ↔ p ≠ 0 ∧ IsRoot p a
[PROOFSTEP]
classical rw [← count_pos, count_roots p, rootMultiplicity_pos']
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
⊢ a ∈ roots p ↔ p ≠ 0 ∧ IsRoot p a
[PROOFSTEP]
rw [← count_pos, count_roots p, rootMultiplicity_pos']
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
x : R
w : p ≠ 0
⊢ x ∈ roots p ↔ ↑(aeval x) p = 0
[PROOFSTEP]
rw [mem_roots w, IsRoot.def, aeval_def, eval₂_eq_eval_map]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
x : R
w : p ≠ 0
⊢ eval x p = 0 ↔ eval x (map (algebraMap R R) p) = 0
[PROOFSTEP]
simp
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
hp : p ≠ 0
⊢ Set.Finite {x | IsRoot p x}
[PROOFSTEP]
classical simpa only [← Finset.setOf_mem, Multiset.mem_toFinset, mem_roots hp] using p.roots.toFinset.finite_toSet
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
hp : p ≠ 0
⊢ Set.Finite {x | IsRoot p x}
[PROOFSTEP]
simpa only [← Finset.setOf_mem, Multiset.mem_toFinset, mem_roots hp] using p.roots.toFinset.finite_toSet
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
h : Set.Infinite {x | eval x p = eval x q}
⊢ p = q
[PROOFSTEP]
rw [← sub_eq_zero]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
h : Set.Infinite {x | eval x p = eval x q}
⊢ p - q = 0
[PROOFSTEP]
apply eq_zero_of_infinite_isRoot
[GOAL]
case h
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
h : Set.Infinite {x | eval x p = eval x q}
⊢ Set.Infinite {x | IsRoot (p - q) x}
[PROOFSTEP]
simpa only [IsRoot, eval_sub, sub_eq_zero]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
hpq : p * q ≠ 0
⊢ roots (p * q) = roots p + roots q
[PROOFSTEP]
classical exact
  Multiset.ext.mpr fun r => by rw [count_add, count_roots, count_roots, count_roots, rootMultiplicity_mul hpq]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
hpq : p * q ≠ 0
⊢ roots (p * q) = roots p + roots q
[PROOFSTEP]
exact Multiset.ext.mpr fun r => by rw [count_add, count_roots, count_roots, count_roots, rootMultiplicity_mul hpq]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
hpq : p * q ≠ 0
r : R
⊢ count r (roots (p * q)) = count r (roots p + roots q)
[PROOFSTEP]
rw [count_add, count_roots, count_roots, count_roots, rootMultiplicity_mul hpq]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
h : q ≠ 0
⊢ p ∣ q → roots p ≤ roots q
[PROOFSTEP]
rintro ⟨k, rfl⟩
[GOAL]
case intro
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p k : R[X]
h : p * k ≠ 0
⊢ roots p ≤ roots (p * k)
[PROOFSTEP]
exact Multiset.le_iff_exists_add.mpr ⟨k.roots, roots_mul h⟩
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
a x : R
⊢ x ∈ roots (p - ↑C a) ↔ p ≠ ↑C a ∧ eval x p = a
[PROOFSTEP]
rw [mem_roots', IsRoot.def, sub_ne_zero, eval_sub, sub_eq_zero, eval_C]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
r : R
⊢ roots (X - ↑C r) = {r}
[PROOFSTEP]
classical
ext s
rw [count_roots, rootMultiplicity_X_sub_C, count_singleton]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
r : R
⊢ roots (X - ↑C r) = {r}
[PROOFSTEP]
ext s
[GOAL]
case a
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
r s : R
⊢ count s (roots (X - ↑C r)) = count s {r}
[PROOFSTEP]
rw [count_roots, rootMultiplicity_X_sub_C, count_singleton]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
⊢ roots X = {0}
[PROOFSTEP]
rw [← roots_X_sub_C, C_0, sub_zero]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
x : R
⊢ roots (↑C x) = 0
[PROOFSTEP]
classical exact
  if H : x = 0 then by rw [H, C_0, roots_zero]
  else Multiset.ext.mpr fun r => (by rw [count_roots, count_zero, rootMultiplicity_eq_zero (not_isRoot_C _ _ H)])
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
x : R
⊢ roots (↑C x) = 0
[PROOFSTEP]
exact
  if H : x = 0 then by rw [H, C_0, roots_zero]
  else Multiset.ext.mpr fun r => (by rw [count_roots, count_zero, rootMultiplicity_eq_zero (not_isRoot_C _ _ H)])
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
x : R
H : x = 0
⊢ roots (↑C x) = 0
[PROOFSTEP]
rw [H, C_0, roots_zero]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
x : R
H : ¬x = 0
r : R
⊢ count r (roots (↑C x)) = count r 0
[PROOFSTEP]
rw [count_roots, count_zero, rootMultiplicity_eq_zero (not_isRoot_C _ _ H)]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
ha : a ≠ 0
⊢ roots (↑C a * p) = roots p
[PROOFSTEP]
by_cases hp : p = 0
[GOAL]
case pos
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
ha : a ≠ 0
hp : p = 0
⊢ roots (↑C a * p) = roots p
[PROOFSTEP]
simp only [roots_mul, *, Ne.def, mul_eq_zero, C_eq_zero, or_self_iff, not_false_iff, roots_C, zero_add, mul_zero]
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
ha : a ≠ 0
hp : ¬p = 0
⊢ roots (↑C a * p) = roots p
[PROOFSTEP]
simp only [roots_mul, *, Ne.def, mul_eq_zero, C_eq_zero, or_self_iff, not_false_iff, roots_C, zero_add, mul_zero]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
ha : a ≠ 0
⊢ roots (a • p) = roots p
[PROOFSTEP]
rw [smul_eq_C_mul, roots_C_mul _ ha]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
L : List R[X]
hd : R[X]
tl : List R[X]
ih : ¬0 ∈ tl → roots (List.prod tl) = Multiset.bind (↑tl) roots
H : ¬0 ∈ hd :: tl
⊢ roots (List.prod (hd :: tl)) = Multiset.bind (↑(hd :: tl)) roots
[PROOFSTEP]
rw [List.mem_cons, not_or] at H 
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
L : List R[X]
hd : R[X]
tl : List R[X]
ih : ¬0 ∈ tl → roots (List.prod tl) = Multiset.bind (↑tl) roots
H : ¬0 = hd ∧ ¬0 ∈ tl
⊢ roots (List.prod (hd :: tl)) = Multiset.bind (↑(hd :: tl)) roots
[PROOFSTEP]
rw [List.prod_cons, roots_mul (mul_ne_zero (Ne.symm H.1) <| List.prod_ne_zero H.2), ← Multiset.cons_coe,
  Multiset.cons_bind, ih H.2]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
m : Multiset R[X]
⊢ ¬0 ∈ m → roots (prod m) = Multiset.bind m roots
[PROOFSTEP]
rcases m with ⟨L⟩
[GOAL]
case mk
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
m : Multiset R[X]
L : List R[X]
⊢ ¬0 ∈ Quot.mk Setoid.r L → roots (prod (Quot.mk Setoid.r L)) = Multiset.bind (Quot.mk Setoid.r L) roots
[PROOFSTEP]
simpa only [Multiset.coe_prod, quot_mk_to_coe''] using roots_list_prod L
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
ι : Type u_1
f : ι → R[X]
s : Finset ι
⊢ Finset.prod s f ≠ 0 → roots (Finset.prod s f) = Multiset.bind s.val fun i => roots (f i)
[PROOFSTEP]
rcases s with ⟨m, hm⟩
[GOAL]
case mk
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
ι : Type u_1
f : ι → R[X]
m : Multiset ι
hm : Nodup m
⊢ Finset.prod { val := m, nodup := hm } f ≠ 0 →
    roots (Finset.prod { val := m, nodup := hm } f) = Multiset.bind { val := m, nodup := hm }.val fun i => roots (f i)
[PROOFSTEP]
simpa [Multiset.prod_eq_zero_iff, Multiset.bind_map] using roots_multiset_prod (m.map f)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
n : ℕ
⊢ roots (p ^ n) = n • roots p
[PROOFSTEP]
induction' n with n ihn
[GOAL]
case zero
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
⊢ roots (p ^ Nat.zero) = Nat.zero • roots p
[PROOFSTEP]
rw [pow_zero, roots_one, Nat.zero_eq, zero_smul, empty_eq_zero]
[GOAL]
case succ
R : Type u
S : Type v
T : Type w
a b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
n : ℕ
ihn : roots (p ^ n) = n • roots p
⊢ roots (p ^ Nat.succ n) = Nat.succ n • roots p
[PROOFSTEP]
rcases eq_or_ne p 0 with (rfl | hp)
[GOAL]
case succ.inl
R : Type u
S : Type v
T : Type w
a b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
n : ℕ
ihn : roots (0 ^ n) = n • roots 0
⊢ roots (0 ^ Nat.succ n) = Nat.succ n • roots 0
[PROOFSTEP]
rw [zero_pow n.succ_pos, roots_zero, smul_zero]
[GOAL]
case succ.inr
R : Type u
S : Type v
T : Type w
a b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
n : ℕ
ihn : roots (p ^ n) = n • roots p
hp : p ≠ 0
⊢ roots (p ^ Nat.succ n) = Nat.succ n • roots p
[PROOFSTEP]
rw [pow_succ', roots_mul (mul_ne_zero (pow_ne_zero _ hp) hp), ihn, Nat.succ_eq_add_one, add_smul, one_smul]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
n : ℕ
⊢ roots (X ^ n) = n • {0}
[PROOFSTEP]
rw [roots_pow, roots_X]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
ha : a ≠ 0
n : ℕ
⊢ roots (↑C a * X ^ n) = n • {0}
[PROOFSTEP]
rw [roots_C_mul _ ha, roots_X_pow]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
ha : a ≠ 0
n : ℕ
⊢ roots (↑(monomial n) a) = n • {0}
[PROOFSTEP]
rw [← C_mul_X_pow_eq_monomial, roots_C_mul_X_pow ha]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
s : Finset R
⊢ roots (Finset.prod s fun a => X - ↑C a) = s.val
[PROOFSTEP]
apply (roots_prod (fun a => X - C a) s ?_).trans
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
s : Finset R
⊢ (Multiset.bind s.val fun i => roots (X - ↑C i)) = s.val
[PROOFSTEP]
simp_rw [roots_X_sub_C]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
s : Finset R
⊢ (Multiset.bind s.val fun i => {i}) = s.val
[PROOFSTEP]
rw [Multiset.bind_singleton, Multiset.map_id']
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
s : Finset R
⊢ (Finset.prod s fun a => X - ↑C a) ≠ 0
[PROOFSTEP]
refine prod_ne_zero_iff.mpr (fun a _ => X_sub_C_ne_zero a)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
s : Multiset R
⊢ roots (prod (Multiset.map (fun a => X - ↑C a) s)) = s
[PROOFSTEP]
rw [roots_multiset_prod, Multiset.bind_map]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
s : Multiset R
⊢ (Multiset.bind s fun a => roots (X - ↑C a)) = s
[PROOFSTEP]
simp_rw [roots_X_sub_C]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
s : Multiset R
⊢ (Multiset.bind s fun a => {a}) = s
[PROOFSTEP]
rw [Multiset.bind_singleton, Multiset.map_id']
[GOAL]
case a
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
s : Multiset R
⊢ ¬0 ∈ Multiset.map (fun a => X - ↑C a) s
[PROOFSTEP]
rw [Multiset.mem_map]
[GOAL]
case a
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
s : Multiset R
⊢ ¬∃ a, a ∈ s ∧ X - ↑C a = 0
[PROOFSTEP]
rintro ⟨a, -, h⟩
[GOAL]
case a.intro.intro
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
s : Multiset R
a : R
h : X - ↑C a = 0
⊢ False
[PROOFSTEP]
exact X_sub_C_ne_zero a h
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
s : Multiset R
⊢ natDegree (prod (Multiset.map (fun a => X - ↑C a) s)) = ↑Multiset.card s
[PROOFSTEP]
rw [natDegree_multiset_prod_of_monic, Multiset.map_map]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
s : Multiset R
⊢ Multiset.sum (Multiset.map (natDegree ∘ fun a => X - ↑C a) s) = ↑Multiset.card s
[PROOFSTEP]
simp only [(· ∘ ·), natDegree_X_sub_C, Multiset.map_const', Multiset.sum_replicate, smul_eq_mul, mul_one]
[GOAL]
case h
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
s : Multiset R
⊢ ∀ (f : R[X]), f ∈ Multiset.map (fun a => X - ↑C a) s → Monic f
[PROOFSTEP]
exact Multiset.forall_mem_map_iff.2 fun a _ => monic_X_sub_C a
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
n : ℕ
hn : 0 < n
a x : R
⊢ x ∈ nthRoots n a ↔ x ^ n = a
[PROOFSTEP]
rw [nthRoots, mem_roots (X_pow_sub_C_ne_zero hn a), IsRoot.def, eval_sub, eval_C, eval_pow, eval_X, sub_eq_zero]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
r : R
⊢ nthRoots 0 r = 0
[PROOFSTEP]
simp only [empty_eq_zero, pow_zero, nthRoots, ← C_1, ← C_sub, roots_C]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
n : ℕ
a : R
⊢ ↑Multiset.card (nthRoots n a) ≤ n
[PROOFSTEP]
classical exact
  (if hn : n = 0 then
    if h : (X : R[X]) ^ n - C a = 0 then by
      simp [Nat.zero_le, nthRoots, roots, h, dif_pos rfl, empty_eq_zero, Multiset.card_zero]
    else
      WithBot.coe_le_coe.1
        (le_trans (card_roots h)
          (by
            rw [hn, pow_zero, ← C_1, ← RingHom.map_sub]
            exact degree_C_le))
  else by
    rw [← WithBot.coe_le_coe]
    simp only [← Nat.cast_withBot]
    rw [← degree_X_pow_sub_C (Nat.pos_of_ne_zero hn) a]
    exact card_roots (X_pow_sub_C_ne_zero (Nat.pos_of_ne_zero hn) a))
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
n : ℕ
a : R
⊢ ↑Multiset.card (nthRoots n a) ≤ n
[PROOFSTEP]
exact
  (if hn : n = 0 then
    if h : (X : R[X]) ^ n - C a = 0 then by
      simp [Nat.zero_le, nthRoots, roots, h, dif_pos rfl, empty_eq_zero, Multiset.card_zero]
    else
      WithBot.coe_le_coe.1
        (le_trans (card_roots h)
          (by
            rw [hn, pow_zero, ← C_1, ← RingHom.map_sub]
            exact degree_C_le))
  else by
    rw [← WithBot.coe_le_coe]
    simp only [← Nat.cast_withBot]
    rw [← degree_X_pow_sub_C (Nat.pos_of_ne_zero hn) a]
    exact card_roots (X_pow_sub_C_ne_zero (Nat.pos_of_ne_zero hn) a))
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
n : ℕ
a : R
hn : n = 0
h : X ^ n - ↑C a = 0
⊢ ↑Multiset.card (nthRoots n a) ≤ n
[PROOFSTEP]
simp [Nat.zero_le, nthRoots, roots, h, dif_pos rfl, empty_eq_zero, Multiset.card_zero]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
n : ℕ
a : R
hn : n = 0
h : ¬X ^ n - ↑C a = 0
⊢ degree (X ^ n - ↑C a) ≤ ↑n
[PROOFSTEP]
rw [hn, pow_zero, ← C_1, ← RingHom.map_sub]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
n : ℕ
a : R
hn : n = 0
h : ¬X ^ n - ↑C a = 0
⊢ degree (↑C (1 - a)) ≤ ↑0
[PROOFSTEP]
exact degree_C_le
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
n : ℕ
a : R
hn : ¬n = 0
⊢ ↑Multiset.card (nthRoots n a) ≤ n
[PROOFSTEP]
rw [← WithBot.coe_le_coe]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
n : ℕ
a : R
hn : ¬n = 0
⊢ ↑(↑Multiset.card (nthRoots n a)) ≤ ↑n
[PROOFSTEP]
simp only [← Nat.cast_withBot]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
n : ℕ
a : R
hn : ¬n = 0
⊢ ↑(↑Multiset.card (nthRoots n a)) ≤ ↑n
[PROOFSTEP]
rw [← degree_X_pow_sub_C (Nat.pos_of_ne_zero hn) a]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
n : ℕ
a : R
hn : ¬n = 0
⊢ ↑(↑Multiset.card (nthRoots n a)) ≤ degree (X ^ n - ↑C a)
[PROOFSTEP]
exact card_roots (X_pow_sub_C_ne_zero (Nat.pos_of_ne_zero hn) a)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
r : R
⊢ nthRoots 2 r = 0 ↔ ¬IsSquare r
[PROOFSTEP]
simp_rw [isSquare_iff_exists_sq, eq_zero_iff_forall_not_mem, mem_nthRoots (by norm_num : 0 < 2), ← not_exists, eq_comm]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
r : R
⊢ 0 < 2
[PROOFSTEP]
norm_num
[GOAL]
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n✝ : ℕ
inst✝⁴ : CommRing R✝
inst✝³ : IsDomain R✝
p q : R✝[X]
n : ℕ
R : Type u_1
inst✝² : CommRing R
inst✝¹ : IsDomain R
inst✝ : DecidableEq R
⊢ nthRootsFinset n R = toFinset (nthRoots n 1)
[PROOFSTEP]
unfold nthRootsFinset
[GOAL]
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n✝ : ℕ
inst✝⁴ : CommRing R✝
inst✝³ : IsDomain R✝
p q : R✝[X]
n : ℕ
R : Type u_1
inst✝² : CommRing R
inst✝¹ : IsDomain R
inst✝ : DecidableEq R
⊢ toFinset (nthRoots n 1) = toFinset (nthRoots n 1)
[PROOFSTEP]
convert rfl
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
n : ℕ
h : 0 < n
x : R
⊢ x ∈ nthRootsFinset n R ↔ x ^ n = 1
[PROOFSTEP]
classical rw [nthRootsFinset_def, mem_toFinset, mem_nthRoots h]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n✝ : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
n : ℕ
h : 0 < n
x : R
⊢ x ∈ nthRootsFinset n R ↔ x ^ n = 1
[PROOFSTEP]
rw [nthRootsFinset_def, mem_toFinset, mem_nthRoots h]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
⊢ nthRootsFinset 0 R = ∅
[PROOFSTEP]
classical simp [nthRootsFinset_def]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
⊢ nthRootsFinset 0 R = ∅
[PROOFSTEP]
simp [nthRootsFinset_def]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hp : Monic p
hq : Monic q
h : natDegree q ≠ 0
⊢ Monic (Polynomial.comp p q)
[PROOFSTEP]
rw [Monic.def, leadingCoeff_comp h, Monic.def.1 hp, Monic.def.1 hq, one_pow, one_mul]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hp : Monic p
r : R
⊢ Monic (Polynomial.comp p (X + ↑C r))
[PROOFSTEP]
refine' hp.comp (monic_X_add_C _) fun ha => _
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hp : Monic p
r : R
ha : natDegree (X + ↑C r) = 0
⊢ False
[PROOFSTEP]
rw [natDegree_X_add_C] at ha 
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hp : Monic p
r : R
ha : 1 = 0
⊢ False
[PROOFSTEP]
exact one_ne_zero ha
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hp : Monic p
r : R
⊢ Monic (Polynomial.comp p (X - ↑C r))
[PROOFSTEP]
simpa using hp.comp_X_add_C (-r)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q : R[X]
c : R[X]ˣ
p : R[X]
⊢ coeff (↑c) 0 • p = ↑c * p
[PROOFSTEP]
rw [← Polynomial.C_mul', ← Polynomial.eq_C_of_degree_eq_zero (degree_coe_units c)]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
⊢ comp p q = 0 ↔ p = 0 ∨ eval (coeff q 0) p = 0 ∧ q = ↑C (coeff q 0)
[PROOFSTEP]
constructor
[GOAL]
case mp
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
⊢ comp p q = 0 → p = 0 ∨ eval (coeff q 0) p = 0 ∧ q = ↑C (coeff q 0)
[PROOFSTEP]
intro h
[GOAL]
case mp
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
h : comp p q = 0
⊢ p = 0 ∨ eval (coeff q 0) p = 0 ∧ q = ↑C (coeff q 0)
[PROOFSTEP]
have key : p.natDegree = 0 ∨ q.natDegree = 0 := by rw [← mul_eq_zero, ← natDegree_comp, h, natDegree_zero]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
h : comp p q = 0
⊢ natDegree p = 0 ∨ natDegree q = 0
[PROOFSTEP]
rw [← mul_eq_zero, ← natDegree_comp, h, natDegree_zero]
[GOAL]
case mp
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
h : comp p q = 0
key : natDegree p = 0 ∨ natDegree q = 0
⊢ p = 0 ∨ eval (coeff q 0) p = 0 ∧ q = ↑C (coeff q 0)
[PROOFSTEP]
replace key := Or.imp eq_C_of_natDegree_eq_zero eq_C_of_natDegree_eq_zero key
[GOAL]
case mp
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
h : comp p q = 0
key : p = ↑C (coeff p 0) ∨ q = ↑C (coeff q 0)
⊢ p = 0 ∨ eval (coeff q 0) p = 0 ∧ q = ↑C (coeff q 0)
[PROOFSTEP]
cases' key with key key
[GOAL]
case mp.inl
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
h : comp p q = 0
key : p = ↑C (coeff p 0)
⊢ p = 0 ∨ eval (coeff q 0) p = 0 ∧ q = ↑C (coeff q 0)
[PROOFSTEP]
rw [key, C_comp] at h 
[GOAL]
case mp.inl
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
h : ↑C (coeff p 0) = 0
key : p = ↑C (coeff p 0)
⊢ p = 0 ∨ eval (coeff q 0) p = 0 ∧ q = ↑C (coeff q 0)
[PROOFSTEP]
exact Or.inl (key.trans h)
[GOAL]
case mp.inr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
h : comp p q = 0
key : q = ↑C (coeff q 0)
⊢ p = 0 ∨ eval (coeff q 0) p = 0 ∧ q = ↑C (coeff q 0)
[PROOFSTEP]
rw [key, comp_C, C_eq_zero] at h 
[GOAL]
case mp.inr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
h : eval (coeff q 0) p = 0
key : q = ↑C (coeff q 0)
⊢ p = 0 ∨ eval (coeff q 0) p = 0 ∧ q = ↑C (coeff q 0)
[PROOFSTEP]
exact Or.inr ⟨h, key⟩
[GOAL]
case mpr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
⊢ p = 0 ∨ eval (coeff q 0) p = 0 ∧ q = ↑C (coeff q 0) → comp p q = 0
[PROOFSTEP]
exact fun h => Or.rec (fun h => by rw [h, zero_comp]) (fun h => by rw [h.2, comp_C, h.1, C_0]) h
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
h✝ : p = 0 ∨ eval (coeff q 0) p = 0 ∧ q = ↑C (coeff q 0)
h : p = 0
⊢ comp p q = 0
[PROOFSTEP]
rw [h, zero_comp]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
h✝ : p = 0 ∨ eval (coeff q 0) p = 0 ∧ q = ↑C (coeff q 0)
h : eval (coeff q 0) p = 0 ∧ q = ↑C (coeff q 0)
⊢ comp p q = 0
[PROOFSTEP]
rw [h.2, comp_C, h.1, C_0]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : Infinite R
p : R[X]
h : ∀ (x : R), eval x p = 0
⊢ p = 0
[PROOFSTEP]
classical
by_contra hp
refine @Fintype.false R _ ?_
exact ⟨p.roots.toFinset, fun x => Multiset.mem_toFinset.mpr ((mem_roots hp).mpr (h _))⟩
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : Infinite R
p : R[X]
h : ∀ (x : R), eval x p = 0
⊢ p = 0
[PROOFSTEP]
by_contra hp
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : Infinite R
p : R[X]
h : ∀ (x : R), eval x p = 0
hp : ¬p = 0
⊢ False
[PROOFSTEP]
refine @Fintype.false R _ ?_
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q : R[X]
inst✝ : Infinite R
p : R[X]
h : ∀ (x : R), eval x p = 0
hp : ¬p = 0
⊢ Fintype R
[PROOFSTEP]
exact ⟨p.roots.toFinset, fun x => Multiset.mem_toFinset.mpr ((mem_roots hp).mpr (h _))⟩
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q✝ : R[X]
inst✝ : Infinite R
p q : R[X]
ext : ∀ (r : R), eval r p = eval r q
⊢ p = q
[PROOFSTEP]
rw [← sub_eq_zero]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q✝ : R[X]
inst✝ : Infinite R
p q : R[X]
ext : ∀ (r : R), eval r p = eval r q
⊢ p - q = 0
[PROOFSTEP]
apply zero_of_eval_zero
[GOAL]
case h
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q✝ : R[X]
inst✝ : Infinite R
p q : R[X]
ext : ∀ (r : R), eval r p = eval r q
⊢ ∀ (x : R), eval x (p - q) = 0
[PROOFSTEP]
intro x
[GOAL]
case h
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q✝ : R[X]
inst✝ : Infinite R
p q : R[X]
ext : ∀ (r : R), eval r p = eval r q
x : R
⊢ eval x (p - q) = 0
[PROOFSTEP]
rw [eval_sub, sub_eq_zero, ext]
[GOAL]
R : Type u
S✝ : Type v
T : Type w
a b : R
n : ℕ
inst✝⁶ : CommRing R
inst✝⁵ : IsDomain R
p✝ q : R[X]
inst✝⁴ : CommRing T
p : T[X]
S : Type u_1
inst✝³ : CommRing S
inst✝² : IsDomain S
inst✝¹ : Algebra T S
inst✝ : DecidableEq S
⊢ rootSet p S = ↑(toFinset (roots (map (algebraMap T S) p)))
[PROOFSTEP]
rw [rootSet]
[GOAL]
R : Type u
S✝ : Type v
T : Type w
a b : R
n : ℕ
inst✝⁶ : CommRing R
inst✝⁵ : IsDomain R
p✝ q : R[X]
inst✝⁴ : CommRing T
p : T[X]
S : Type u_1
inst✝³ : CommRing S
inst✝² : IsDomain S
inst✝¹ : Algebra T S
inst✝ : DecidableEq S
⊢ ↑(toFinset (roots (map (algebraMap T S) p))) = ↑(toFinset (roots (map (algebraMap T S) p)))
[PROOFSTEP]
convert rfl
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝⁵ : CommRing R
inst✝⁴ : IsDomain R
p q : R[X]
inst✝³ : CommRing T
inst✝² : CommRing S
inst✝¹ : IsDomain S
inst✝ : Algebra T S
a : T
⊢ rootSet (↑C a) S = ∅
[PROOFSTEP]
classical rw [rootSet_def, map_C, roots_C, Multiset.toFinset_zero, Finset.coe_empty]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝⁵ : CommRing R
inst✝⁴ : IsDomain R
p q : R[X]
inst✝³ : CommRing T
inst✝² : CommRing S
inst✝¹ : IsDomain S
inst✝ : Algebra T S
a : T
⊢ rootSet (↑C a) S = ∅
[PROOFSTEP]
rw [rootSet_def, map_C, roots_C, Multiset.toFinset_zero, Finset.coe_empty]
[GOAL]
R : Type u
S✝ : Type v
T : Type w
a b : R
n : ℕ
inst✝⁵ : CommRing R
inst✝⁴ : IsDomain R
p q : R[X]
inst✝³ : CommRing T
S : Type u_1
inst✝² : CommRing S
inst✝¹ : IsDomain S
inst✝ : Algebra T S
⊢ rootSet 0 S = ∅
[PROOFSTEP]
rw [← C_0, rootSet_C]
[GOAL]
R✝ : Type u
S✝ : Type v
T : Type w
a b : R✝
n : ℕ
inst✝⁶ : CommRing R✝
inst✝⁵ : IsDomain R✝
p q : R✝[X]
inst✝⁴ : CommRing T
R : Type u_1
S : Type u_2
inst✝³ : Semiring R
inst✝² : CommRing S
inst✝¹ : IsDomain S
inst✝ : DecidableEq S
m : R →+* S
d : ℕ
U : Set R
h : Set.Finite U
⊢ Set.Finite fun f => natDegree f ≤ d ∧ ∀ (i : ℕ), coeff f i ∈ U
[PROOFSTEP]
let π : R[X] → Fin (d + 1) → R := fun f i => f.coeff i
[GOAL]
R✝ : Type u
S✝ : Type v
T : Type w
a b : R✝
n : ℕ
inst✝⁶ : CommRing R✝
inst✝⁵ : IsDomain R✝
p q : R✝[X]
inst✝⁴ : CommRing T
R : Type u_1
S : Type u_2
inst✝³ : Semiring R
inst✝² : CommRing S
inst✝¹ : IsDomain S
inst✝ : DecidableEq S
m : R →+* S
d : ℕ
U : Set R
h : Set.Finite U
π : R[X] → Fin (d + 1) → R := fun f i => coeff f ↑i
⊢ Set.Finite fun f => natDegree f ≤ d ∧ ∀ (i : ℕ), coeff f i ∈ U
[PROOFSTEP]
refine' ((Set.Finite.pi fun _ => h).subset <| _).of_finite_image (_ : Set.InjOn π _)
[GOAL]
case refine'_1
R✝ : Type u
S✝ : Type v
T : Type w
a b : R✝
n : ℕ
inst✝⁶ : CommRing R✝
inst✝⁵ : IsDomain R✝
p q : R✝[X]
inst✝⁴ : CommRing T
R : Type u_1
S : Type u_2
inst✝³ : Semiring R
inst✝² : CommRing S
inst✝¹ : IsDomain S
inst✝ : DecidableEq S
m : R →+* S
d : ℕ
U : Set R
h : Set.Finite U
π : R[X] → Fin (d + 1) → R := fun f i => coeff f ↑i
⊢ (π '' fun f => natDegree f ≤ d ∧ ∀ (i : ℕ), coeff f i ∈ U) ⊆ Set.pi Set.univ fun x => U
[PROOFSTEP]
exact Set.image_subset_iff.2 fun f hf i _ => hf.2 i
[GOAL]
case refine'_2
R✝ : Type u
S✝ : Type v
T : Type w
a b : R✝
n : ℕ
inst✝⁶ : CommRing R✝
inst✝⁵ : IsDomain R✝
p q : R✝[X]
inst✝⁴ : CommRing T
R : Type u_1
S : Type u_2
inst✝³ : Semiring R
inst✝² : CommRing S
inst✝¹ : IsDomain S
inst✝ : DecidableEq S
m : R →+* S
d : ℕ
U : Set R
h : Set.Finite U
π : R[X] → Fin (d + 1) → R := fun f i => coeff f ↑i
⊢ Set.InjOn π fun f => natDegree f ≤ d ∧ ∀ (i : ℕ), coeff f i ∈ U
[PROOFSTEP]
refine' fun x hx y hy hxy => (ext_iff_natDegree_le hx.1 hy.1).2 fun i hi => _
[GOAL]
case refine'_2
R✝ : Type u
S✝ : Type v
T : Type w
a b : R✝
n : ℕ
inst✝⁶ : CommRing R✝
inst✝⁵ : IsDomain R✝
p q : R✝[X]
inst✝⁴ : CommRing T
R : Type u_1
S : Type u_2
inst✝³ : Semiring R
inst✝² : CommRing S
inst✝¹ : IsDomain S
inst✝ : DecidableEq S
m : R →+* S
d : ℕ
U : Set R
h : Set.Finite U
π : R[X] → Fin (d + 1) → R := fun f i => coeff f ↑i
x : R[X]
hx : x ∈ fun f => natDegree f ≤ d ∧ ∀ (i : ℕ), coeff f i ∈ U
y : R[X]
hy : y ∈ fun f => natDegree f ≤ d ∧ ∀ (i : ℕ), coeff f i ∈ U
hxy : π x = π y
i : ℕ
hi : i ≤ d
⊢ coeff x i = coeff y i
[PROOFSTEP]
exact id congr_fun hxy ⟨i, Nat.lt_succ_of_le hi⟩
[GOAL]
R : Type u
S✝ : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝⁵ : CommRing R
inst✝⁴ : IsDomain R
p✝ q : R[X]
inst✝³ : CommRing T
p : T[X]
S : Type u_1
inst✝² : CommRing S
inst✝¹ : IsDomain S
inst✝ : Algebra T S
a : S
⊢ a ∈ rootSet p S ↔ map (algebraMap T S) p ≠ 0 ∧ ↑(aeval a) p = 0
[PROOFSTEP]
classical rw [rootSet_def, Finset.mem_coe, mem_toFinset, mem_roots', IsRoot.def, ← eval₂_eq_eval_map, aeval_def]
[GOAL]
R : Type u
S✝ : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝⁵ : CommRing R
inst✝⁴ : IsDomain R
p✝ q : R[X]
inst✝³ : CommRing T
p : T[X]
S : Type u_1
inst✝² : CommRing S
inst✝¹ : IsDomain S
inst✝ : Algebra T S
a : S
⊢ a ∈ rootSet p S ↔ map (algebraMap T S) p ≠ 0 ∧ ↑(aeval a) p = 0
[PROOFSTEP]
rw [rootSet_def, Finset.mem_coe, mem_toFinset, mem_roots', IsRoot.def, ← eval₂_eq_eval_map, aeval_def]
[GOAL]
R : Type u
S✝ : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝⁶ : CommRing R
inst✝⁵ : IsDomain R
p✝ q : R[X]
inst✝⁴ : CommRing T
p : T[X]
S : Type u_1
inst✝³ : CommRing S
inst✝² : IsDomain S
inst✝¹ : Algebra T S
inst✝ : NoZeroSMulDivisors T S
a : S
⊢ a ∈ rootSet p S ↔ p ≠ 0 ∧ ↑(aeval a) p = 0
[PROOFSTEP]
rw [mem_rootSet', (map_injective _ (NoZeroSMulDivisors.algebraMap_injective T S)).ne_iff' (Polynomial.map_zero _)]
[GOAL]
R : Type u
S✝ : Type v
T : Type w
a b : R
n : ℕ
inst✝⁸ : CommRing R
inst✝⁷ : IsDomain R
p✝ q : R[X]
inst✝⁶ : CommRing T
p : T[X]
S : Type u_1
S' : Type u_2
inst✝⁵ : CommRing S
inst✝⁴ : IsDomain S
inst✝³ : Algebra T S
inst✝² : CommRing S'
inst✝¹ : IsDomain S'
inst✝ : Algebra T S'
hp : map (algebraMap T S') p = 0 → map (algebraMap T S) p = 0
f : S →ₐ[T] S'
x : S
hx : x ∈ rootSet p S
⊢ ↑f x ∈ rootSet p S'
[PROOFSTEP]
rw [mem_rootSet'] at hx ⊢
[GOAL]
R : Type u
S✝ : Type v
T : Type w
a b : R
n : ℕ
inst✝⁸ : CommRing R
inst✝⁷ : IsDomain R
p✝ q : R[X]
inst✝⁶ : CommRing T
p : T[X]
S : Type u_1
S' : Type u_2
inst✝⁵ : CommRing S
inst✝⁴ : IsDomain S
inst✝³ : Algebra T S
inst✝² : CommRing S'
inst✝¹ : IsDomain S'
inst✝ : Algebra T S'
hp : map (algebraMap T S') p = 0 → map (algebraMap T S) p = 0
f : S →ₐ[T] S'
x : S
hx : map (algebraMap T S) p ≠ 0 ∧ ↑(aeval x) p = 0
⊢ map (algebraMap T S') p ≠ 0 ∧ ↑(aeval (↑f x)) p = 0
[PROOFSTEP]
rw [aeval_algHom, AlgHom.comp_apply, hx.2, _root_.map_zero]
[GOAL]
R : Type u
S✝ : Type v
T : Type w
a b : R
n : ℕ
inst✝⁸ : CommRing R
inst✝⁷ : IsDomain R
p✝ q : R[X]
inst✝⁶ : CommRing T
p : T[X]
S : Type u_1
S' : Type u_2
inst✝⁵ : CommRing S
inst✝⁴ : IsDomain S
inst✝³ : Algebra T S
inst✝² : CommRing S'
inst✝¹ : IsDomain S'
inst✝ : Algebra T S'
hp : map (algebraMap T S') p = 0 → map (algebraMap T S) p = 0
f : S →ₐ[T] S'
x : S
hx : map (algebraMap T S) p ≠ 0 ∧ ↑(aeval x) p = 0
⊢ map (algebraMap T S') p ≠ 0 ∧ 0 = 0
[PROOFSTEP]
exact ⟨mt hp hx.1, rfl⟩
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝⁵ : CommRing R
inst✝⁴ : IsDomain R
p✝ q : R[X]
inst✝³ : CommRing T
p : T[X]
inst✝² : CommRing S
inst✝¹ : IsDomain S
inst✝ : Algebra T S
a : S
h : a ∈ rootSet p S
hf : p = 0
⊢ False
[PROOFSTEP]
rwa [hf, rootSet_zero] at h 
[GOAL]
R : Type u
S✝ : Type v
T : Type w
a b : R
n : ℕ
inst✝⁹ : CommRing R
inst✝⁸ : IsDomain R
p✝ q : R[X]
inst✝⁷ : CommRing T
p : T[X]
S : Type u_1
S' : Type u_2
inst✝⁶ : CommRing S
inst✝⁵ : IsDomain S
inst✝⁴ : Algebra T S
inst✝³ : CommRing S'
inst✝² : IsDomain S'
inst✝¹ : Algebra T S'
inst✝ : NoZeroSMulDivisors T S'
f : S →ₐ[T] S'
⊢ Set.MapsTo (↑f) (rootSet p S) (rootSet p S')
[PROOFSTEP]
refine' rootSet_maps_to' (fun h₀ => _) f
[GOAL]
R : Type u
S✝ : Type v
T : Type w
a b : R
n : ℕ
inst✝⁹ : CommRing R
inst✝⁸ : IsDomain R
p✝ q : R[X]
inst✝⁷ : CommRing T
p : T[X]
S : Type u_1
S' : Type u_2
inst✝⁶ : CommRing S
inst✝⁵ : IsDomain S
inst✝⁴ : Algebra T S
inst✝³ : CommRing S'
inst✝² : IsDomain S'
inst✝¹ : Algebra T S'
inst✝ : NoZeroSMulDivisors T S'
f : S →ₐ[T] S'
h₀ : map (algebraMap T S') p = 0
⊢ map (algebraMap T S) p = 0
[PROOFSTEP]
obtain rfl : p = 0 := map_injective _ (NoZeroSMulDivisors.algebraMap_injective T S') (by rwa [Polynomial.map_zero])
[GOAL]
R : Type u
S✝ : Type v
T : Type w
a b : R
n : ℕ
inst✝⁹ : CommRing R
inst✝⁸ : IsDomain R
p✝ q : R[X]
inst✝⁷ : CommRing T
p : T[X]
S : Type u_1
S' : Type u_2
inst✝⁶ : CommRing S
inst✝⁵ : IsDomain S
inst✝⁴ : Algebra T S
inst✝³ : CommRing S'
inst✝² : IsDomain S'
inst✝¹ : Algebra T S'
inst✝ : NoZeroSMulDivisors T S'
f : S →ₐ[T] S'
h₀ : map (algebraMap T S') p = 0
⊢ map (algebraMap T S') p = map (algebraMap T S') 0
[PROOFSTEP]
rwa [Polynomial.map_zero]
[GOAL]
R : Type u
S✝ : Type v
T : Type w
a b : R
n : ℕ
inst✝⁹ : CommRing R
inst✝⁸ : IsDomain R
p q : R[X]
inst✝⁷ : CommRing T
S : Type u_1
S' : Type u_2
inst✝⁶ : CommRing S
inst✝⁵ : IsDomain S
inst✝⁴ : Algebra T S
inst✝³ : CommRing S'
inst✝² : IsDomain S'
inst✝¹ : Algebra T S'
inst✝ : NoZeroSMulDivisors T S'
f : S →ₐ[T] S'
h₀ : map (algebraMap T S') 0 = 0
⊢ map (algebraMap T S) 0 = 0
[PROOFSTEP]
exact Polynomial.map_zero _
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
u : R[X]ˣ
⊢ coeff (↑u) 0 ≠ 0
[PROOFSTEP]
conv in 0 => rw [← natDegree_coe_units u]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
u : R[X]ˣ
| 0
[PROOFSTEP]
rw [← natDegree_coe_units u]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
u : R[X]ˣ
| 0
[PROOFSTEP]
rw [← natDegree_coe_units u]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
u : R[X]ˣ
| 0
[PROOFSTEP]
rw [← natDegree_coe_units u]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
u : R[X]ˣ
⊢ coeff (↑u) (natDegree ↑u) ≠ 0
[PROOFSTEP]
rw [← leadingCoeff, Ne.def, leadingCoeff_eq_zero]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
u : R[X]ˣ
⊢ ¬↑u = 0
[PROOFSTEP]
exact Units.ne_zero _
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
h : Associated p q
⊢ degree p = degree q
[PROOFSTEP]
let ⟨u, hu⟩ := h
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
h : Associated p q
u : R[X]ˣ
hu : p * ↑u = q
⊢ degree p = degree q
[PROOFSTEP]
simp [hu.symm]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hi : Irreducible p
x : R
hx : IsRoot p x
g : R[X]
hg : p = (X - ↑C x) * g
this : IsUnit (X - ↑C x) ∨ IsUnit g
h : IsUnit (X - ↑C x)
⊢ degree p = 1
[PROOFSTEP]
have h₁ : degree (X - C x) = 1 := degree_X_sub_C x
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hi : Irreducible p
x : R
hx : IsRoot p x
g : R[X]
hg : p = (X - ↑C x) * g
this : IsUnit (X - ↑C x) ∨ IsUnit g
h : IsUnit (X - ↑C x)
h₁ : degree (X - ↑C x) = 1
⊢ degree p = 1
[PROOFSTEP]
have h₂ : degree (X - C x) = 0 := degree_eq_zero_of_isUnit h
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hi : Irreducible p
x : R
hx : IsRoot p x
g : R[X]
hg : p = (X - ↑C x) * g
this : IsUnit (X - ↑C x) ∨ IsUnit g
h : IsUnit (X - ↑C x)
h₁ : degree (X - ↑C x) = 1
h₂ : degree (X - ↑C x) = 0
⊢ degree p = 1
[PROOFSTEP]
rw [h₁] at h₂ 
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hi : Irreducible p
x : R
hx : IsRoot p x
g : R[X]
hg : p = (X - ↑C x) * g
this : IsUnit (X - ↑C x) ∨ IsUnit g
h : IsUnit (X - ↑C x)
h₁ : degree (X - ↑C x) = 1
h₂ : 1 = 0
⊢ degree p = 1
[PROOFSTEP]
exact absurd h₂ (by decide)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hi : Irreducible p
x : R
hx : IsRoot p x
g : R[X]
hg : p = (X - ↑C x) * g
this : IsUnit (X - ↑C x) ∨ IsUnit g
h : IsUnit (X - ↑C x)
h₁ : degree (X - ↑C x) = 1
h₂ : 1 = 0
⊢ ¬1 = 0
[PROOFSTEP]
decide
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hi : Irreducible p
x : R
hx : IsRoot p x
g : R[X]
hg : p = (X - ↑C x) * g
this : IsUnit (X - ↑C x) ∨ IsUnit g
hgu : IsUnit g
⊢ degree p = 1
[PROOFSTEP]
rw [hg, degree_mul, degree_X_sub_C, degree_eq_zero_of_isUnit hgu, add_zero]
[GOAL]
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u
inst✝ : CommRing R
p q : R[X]
hmonic : Monic q
hdegree : degree q ≤ degree p
⊢ leadingCoeff (p /ₘ q) = leadingCoeff p
[PROOFSTEP]
nontriviality
[GOAL]
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u
inst✝ : CommRing R
p q : R[X]
hmonic : Monic q
hdegree : degree q ≤ degree p
✝ : Nontrivial R
⊢ leadingCoeff (p /ₘ q) = leadingCoeff p
[PROOFSTEP]
have h : q.leadingCoeff * (p /ₘ q).leadingCoeff ≠ 0 := by
  simpa [divByMonic_eq_zero_iff hmonic, hmonic.leadingCoeff, Nat.WithBot.one_le_iff_zero_lt] using hdegree
[GOAL]
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u
inst✝ : CommRing R
p q : R[X]
hmonic : Monic q
hdegree : degree q ≤ degree p
✝ : Nontrivial R
⊢ leadingCoeff q * leadingCoeff (p /ₘ q) ≠ 0
[PROOFSTEP]
simpa [divByMonic_eq_zero_iff hmonic, hmonic.leadingCoeff, Nat.WithBot.one_le_iff_zero_lt] using hdegree
[GOAL]
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u
inst✝ : CommRing R
p q : R[X]
hmonic : Monic q
hdegree : degree q ≤ degree p
✝ : Nontrivial R
h : leadingCoeff q * leadingCoeff (p /ₘ q) ≠ 0
⊢ leadingCoeff (p /ₘ q) = leadingCoeff p
[PROOFSTEP]
nth_rw 2 [← modByMonic_add_div p hmonic]
[GOAL]
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u
inst✝ : CommRing R
p q : R[X]
hmonic : Monic q
hdegree : degree q ≤ degree p
✝ : Nontrivial R
h : leadingCoeff q * leadingCoeff (p /ₘ q) ≠ 0
⊢ leadingCoeff (p /ₘ q) = leadingCoeff (p %ₘ q + q * (p /ₘ q))
[PROOFSTEP]
rw [leadingCoeff_add_of_degree_lt, leadingCoeff_monic_mul hmonic]
[GOAL]
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u
inst✝ : CommRing R
p q : R[X]
hmonic : Monic q
hdegree : degree q ≤ degree p
✝ : Nontrivial R
h : leadingCoeff q * leadingCoeff (p /ₘ q) ≠ 0
⊢ degree (p %ₘ q) < degree (q * (p /ₘ q))
[PROOFSTEP]
rw [degree_mul' h, degree_add_divByMonic hmonic hdegree]
[GOAL]
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u
inst✝ : CommRing R
p q : R[X]
hmonic : Monic q
hdegree : degree q ≤ degree p
✝ : Nontrivial R
h : leadingCoeff q * leadingCoeff (p /ₘ q) ≠ 0
⊢ degree (p %ₘ q) < degree p
[PROOFSTEP]
exact (degree_modByMonic_lt p hmonic).trans_le hdegree
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
hp : degree p ≠ 0
a : R
⊢ leadingCoeff (p /ₘ (X - ↑C a)) = leadingCoeff p
[PROOFSTEP]
nontriviality
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q p : R[X]
hp : degree p ≠ 0
a : R
inst✝ : Nontrivial R
⊢ leadingCoeff (p /ₘ (X - ↑C a)) = leadingCoeff p
[PROOFSTEP]
cases' hp.lt_or_lt with hd hd
[GOAL]
case inl
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q p : R[X]
hp : degree p ≠ 0
a : R
inst✝ : Nontrivial R
hd : degree p < 0
⊢ leadingCoeff (p /ₘ (X - ↑C a)) = leadingCoeff p
[PROOFSTEP]
rw [degree_eq_bot.mp <| (Nat.WithBot.lt_zero_iff _).mp hd, zero_divByMonic]
[GOAL]
case inr
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q p : R[X]
hp : degree p ≠ 0
a : R
inst✝ : Nontrivial R
hd : 0 < degree p
⊢ leadingCoeff (p /ₘ (X - ↑C a)) = leadingCoeff p
[PROOFSTEP]
refine' leadingCoeff_divByMonic_of_monic (monic_X_sub_C a) _
[GOAL]
case inr
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p✝ q p : R[X]
hp : degree p ≠ 0
a : R
inst✝ : Nontrivial R
hd : 0 < degree p
⊢ degree (X - ↑C a) ≤ degree p
[PROOFSTEP]
rwa [degree_X_sub_C, Nat.WithBot.one_le_iff_zero_lt]
[GOAL]
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u_1
inst✝ : CommRing R
p q : R[X]
hp : Monic p
hdiv : p ∣ q
hdeg : natDegree q ≤ natDegree p
⊢ q = ↑C (leadingCoeff q) * p
[PROOFSTEP]
obtain ⟨r, hr⟩ := hdiv
[GOAL]
case intro
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u_1
inst✝ : CommRing R
p q : R[X]
hp : Monic p
hdeg : natDegree q ≤ natDegree p
r : R[X]
hr : q = p * r
⊢ q = ↑C (leadingCoeff q) * p
[PROOFSTEP]
obtain rfl | hq := eq_or_ne q 0
[GOAL]
case intro.inl
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q : R✝[X]
R : Type u_1
inst✝ : CommRing R
p : R[X]
hp : Monic p
r : R[X]
hdeg : natDegree 0 ≤ natDegree p
hr : 0 = p * r
⊢ 0 = ↑C (leadingCoeff 0) * p
[PROOFSTEP]
simp
[GOAL]
case intro.inr
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u_1
inst✝ : CommRing R
p q : R[X]
hp : Monic p
hdeg : natDegree q ≤ natDegree p
r : R[X]
hr : q = p * r
hq : q ≠ 0
⊢ q = ↑C (leadingCoeff q) * p
[PROOFSTEP]
have rzero : r ≠ 0 := fun h => by simp [h, hq] at hr 
[GOAL]
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u_1
inst✝ : CommRing R
p q : R[X]
hp : Monic p
hdeg : natDegree q ≤ natDegree p
r : R[X]
hr : q = p * r
hq : q ≠ 0
h : r = 0
⊢ False
[PROOFSTEP]
simp [h, hq] at hr 
[GOAL]
case intro.inr
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u_1
inst✝ : CommRing R
p q : R[X]
hp : Monic p
hdeg : natDegree q ≤ natDegree p
r : R[X]
hr : q = p * r
hq : q ≠ 0
rzero : r ≠ 0
⊢ q = ↑C (leadingCoeff q) * p
[PROOFSTEP]
rw [hr, natDegree_mul'] at hdeg 
[GOAL]
case intro.inr
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u_1
inst✝ : CommRing R
p q : R[X]
hp : Monic p
r : R[X]
hdeg : natDegree p + natDegree r ≤ natDegree p
hr : q = p * r
hq : q ≠ 0
rzero : r ≠ 0
⊢ q = ↑C (leadingCoeff q) * p
case intro.inr
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u_1
inst✝ : CommRing R
p q : R[X]
hp : Monic p
r : R[X]
hdeg : natDegree (p * r) ≤ natDegree p
hr : q = p * r
hq : q ≠ 0
rzero : r ≠ 0
⊢ leadingCoeff p * leadingCoeff r ≠ 0
[PROOFSTEP]
swap
[GOAL]
case intro.inr
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u_1
inst✝ : CommRing R
p q : R[X]
hp : Monic p
r : R[X]
hdeg : natDegree (p * r) ≤ natDegree p
hr : q = p * r
hq : q ≠ 0
rzero : r ≠ 0
⊢ leadingCoeff p * leadingCoeff r ≠ 0
[PROOFSTEP]
rw [hp.leadingCoeff, one_mul, leadingCoeff_ne_zero]
[GOAL]
case intro.inr
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u_1
inst✝ : CommRing R
p q : R[X]
hp : Monic p
r : R[X]
hdeg : natDegree (p * r) ≤ natDegree p
hr : q = p * r
hq : q ≠ 0
rzero : r ≠ 0
⊢ r ≠ 0
[PROOFSTEP]
exact rzero
[GOAL]
case intro.inr
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u_1
inst✝ : CommRing R
p q : R[X]
hp : Monic p
r : R[X]
hdeg : natDegree p + natDegree r ≤ natDegree p
hr : q = p * r
hq : q ≠ 0
rzero : r ≠ 0
⊢ q = ↑C (leadingCoeff q) * p
[PROOFSTEP]
rw [mul_comm, @eq_C_of_natDegree_eq_zero _ _ r] at hr 
[GOAL]
case intro.inr
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u_1
inst✝ : CommRing R
p q : R[X]
hp : Monic p
r : R[X]
hdeg : natDegree p + natDegree r ≤ natDegree p
hr : q = ↑C (coeff r 0) * p
hq : q ≠ 0
rzero : r ≠ 0
⊢ q = ↑C (leadingCoeff q) * p
[PROOFSTEP]
convert hr
[GOAL]
case h.e'_3.h.e'_5.h.e'_6
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u_1
inst✝ : CommRing R
p q : R[X]
hp : Monic p
r : R[X]
hdeg : natDegree p + natDegree r ≤ natDegree p
hr : q = ↑C (coeff r 0) * p
hq : q ≠ 0
rzero : r ≠ 0
⊢ leadingCoeff q = coeff r 0
[PROOFSTEP]
convert leadingCoeff_C (coeff r 0) using 1
[GOAL]
case h.e'_2
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u_1
inst✝ : CommRing R
p q : R[X]
hp : Monic p
r : R[X]
hdeg : natDegree p + natDegree r ≤ natDegree p
hr : q = ↑C (coeff r 0) * p
hq : q ≠ 0
rzero : r ≠ 0
⊢ leadingCoeff q = leadingCoeff (↑C (coeff r 0))
[PROOFSTEP]
rw [hr, leadingCoeff_mul_monic hp]
[GOAL]
case intro.inr
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u_1
inst✝ : CommRing R
p q : R[X]
hp : Monic p
r : R[X]
hdeg : natDegree p + natDegree r ≤ natDegree p
hr : q = r * p
hq : q ≠ 0
rzero : r ≠ 0
⊢ natDegree r = 0
[PROOFSTEP]
exact (add_right_inj _).1 (le_antisymm hdeg <| Nat.le.intro rfl)
[GOAL]
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u_1
inst✝ : CommRing R
p q : R[X]
hp : Monic p
hq : Monic q
hdiv : p ∣ q
hdeg : natDegree q ≤ natDegree p
⊢ q = p
[PROOFSTEP]
convert eq_leadingCoeff_mul_of_monic_of_dvd_of_natDegree_le hp hdiv hdeg
[GOAL]
case h.e'_3
R✝ : Type u
S : Type v
T : Type w
a b : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p✝ q✝ : R✝[X]
R : Type u_1
inst✝ : CommRing R
p q : R[X]
hp : Monic p
hq : Monic q
hdiv : p ∣ q
hdeg : natDegree q ≤ natDegree p
⊢ p = ↑C (leadingCoeff q) * p
[PROOFSTEP]
rw [hq.leadingCoeff, C_1, one_mul]
[GOAL]
R✝ : Type u
S : Type v
T : Type w
a✝ b✝ : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p q : R✝[X]
R : Type u_1
inst✝ : CommRing R
a b : R
h : IsUnit (a - b)
⊢ -↑C ↑(IsUnit.unit h)⁻¹ * (X - ↑C a) + ↑C ↑(IsUnit.unit h)⁻¹ * (X - ↑C b) = 1
[PROOFSTEP]
rw [neg_mul_comm, ← left_distrib, neg_add_eq_sub, sub_sub_sub_cancel_left, ← C_sub, ← C_mul]
[GOAL]
R✝ : Type u
S : Type v
T : Type w
a✝ b✝ : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p q : R✝[X]
R : Type u_1
inst✝ : CommRing R
a b : R
h : IsUnit (a - b)
⊢ ↑C (↑(IsUnit.unit h)⁻¹ * (a - b)) = 1
[PROOFSTEP]
rw [← C_1]
[GOAL]
R✝ : Type u
S : Type v
T : Type w
a✝ b✝ : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p q : R✝[X]
R : Type u_1
inst✝ : CommRing R
a b : R
h : IsUnit (a - b)
⊢ ↑C (↑(IsUnit.unit h)⁻¹ * (a - b)) = ↑C 1
[PROOFSTEP]
congr
[GOAL]
case h.e_6.h
R✝ : Type u
S : Type v
T : Type w
a✝ b✝ : R✝
n : ℕ
inst✝² : CommRing R✝
inst✝¹ : IsDomain R✝
p q : R✝[X]
R : Type u_1
inst✝ : CommRing R
a b : R
h : IsUnit (a - b)
⊢ ↑(IsUnit.unit h)⁻¹ * (a - b) = 1
[PROOFSTEP]
exact h.val_inv_mul
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : CommRing R
inst✝¹ : IsDomain R
p q : R[X]
inst✝ : DecidableEq R
⊢ Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) =
    Finset.prod (Multiset.toFinset (roots p)) fun a => (X - ↑C a) ^ rootMultiplicity a p
[PROOFSTEP]
simp only [count_roots, Finset.prod_multiset_map_count]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
⊢ Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) ∣ p
[PROOFSTEP]
classical
rw [← map_dvd_map _ (IsFractionRing.injective R <| FractionRing R) monic_prod_multiset_X_sub_C]
rw [prod_multiset_root_eq_finset_root, Polynomial.map_prod]
refine' Finset.prod_dvd_of_coprime (fun a _ b _ h => _) fun a _ => _
· simp_rw [Polynomial.map_pow, Polynomial.map_sub, map_C, map_X]
  exact (pairwise_coprime_X_sub_C (IsFractionRing.injective R <| FractionRing R) h).pow
· exact Polynomial.map_dvd _ (pow_rootMultiplicity_dvd p a)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
⊢ Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) ∣ p
[PROOFSTEP]
rw [← map_dvd_map _ (IsFractionRing.injective R <| FractionRing R) monic_prod_multiset_X_sub_C]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
⊢ map (algebraMap R (FractionRing R)) (Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p))) ∣
    map (algebraMap R (FractionRing R)) p
[PROOFSTEP]
rw [prod_multiset_root_eq_finset_root, Polynomial.map_prod]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
⊢ (Finset.prod (Multiset.toFinset (roots p)) fun i =>
      map (algebraMap R (FractionRing R)) ((X - ↑C i) ^ rootMultiplicity i p)) ∣
    map (algebraMap R (FractionRing R)) p
[PROOFSTEP]
refine' Finset.prod_dvd_of_coprime (fun a _ b _ h => _) fun a _ => _
[GOAL]
case refine'_1
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
a : R
x✝¹ : a ∈ ↑(Multiset.toFinset (roots p))
b : R
x✝ : b ∈ ↑(Multiset.toFinset (roots p))
h : a ≠ b
⊢ (IsCoprime on fun i => map (algebraMap R (FractionRing R)) ((X - ↑C i) ^ rootMultiplicity i p)) a b
[PROOFSTEP]
simp_rw [Polynomial.map_pow, Polynomial.map_sub, map_C, map_X]
[GOAL]
case refine'_1
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
a : R
x✝¹ : a ∈ ↑(Multiset.toFinset (roots p))
b : R
x✝ : b ∈ ↑(Multiset.toFinset (roots p))
h : a ≠ b
⊢ (IsCoprime on fun i => (X - ↑C (↑(algebraMap R (FractionRing R)) i)) ^ rootMultiplicity i p) a b
[PROOFSTEP]
exact (pairwise_coprime_X_sub_C (IsFractionRing.injective R <| FractionRing R) h).pow
[GOAL]
case refine'_2
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
a : R
x✝ : a ∈ Multiset.toFinset (roots p)
⊢ map (algebraMap R (FractionRing R)) ((X - ↑C a) ^ rootMultiplicity a p) ∣ map (algebraMap R (FractionRing R)) p
[PROOFSTEP]
exact Polynomial.map_dvd _ (pow_rootMultiplicity_dvd p a)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
hp : p ≠ 0
s : Multiset R
⊢ Multiset.prod (Multiset.map (fun a => X - ↑C a) s) ∣ p ↔ s ≤ roots p
[PROOFSTEP]
classical exact
  ⟨fun h =>
    Multiset.le_iff_count.2 fun r =>
      by
      rw [count_roots, le_rootMultiplicity_iff hp, ← Multiset.prod_replicate, ← Multiset.map_replicate fun a => X - C a,
        ← Multiset.filter_eq]
      exact (Multiset.prod_dvd_prod_of_le <| Multiset.map_le_map <| s.filter_le _).trans h,
    fun h => (Multiset.prod_dvd_prod_of_le <| Multiset.map_le_map h).trans p.prod_multiset_X_sub_C_dvd⟩
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
hp : p ≠ 0
s : Multiset R
⊢ Multiset.prod (Multiset.map (fun a => X - ↑C a) s) ∣ p ↔ s ≤ roots p
[PROOFSTEP]
exact
  ⟨fun h =>
    Multiset.le_iff_count.2 fun r =>
      by
      rw [count_roots, le_rootMultiplicity_iff hp, ← Multiset.prod_replicate, ← Multiset.map_replicate fun a => X - C a,
        ← Multiset.filter_eq]
      exact (Multiset.prod_dvd_prod_of_le <| Multiset.map_le_map <| s.filter_le _).trans h,
    fun h => (Multiset.prod_dvd_prod_of_le <| Multiset.map_le_map h).trans p.prod_multiset_X_sub_C_dvd⟩
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
hp : p ≠ 0
s : Multiset R
h : Multiset.prod (Multiset.map (fun a => X - ↑C a) s) ∣ p
r : R
⊢ Multiset.count r s ≤ Multiset.count r (roots p)
[PROOFSTEP]
rw [count_roots, le_rootMultiplicity_iff hp, ← Multiset.prod_replicate, ← Multiset.map_replicate fun a => X - C a, ←
  Multiset.filter_eq]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
hp : p ≠ 0
s : Multiset R
h : Multiset.prod (Multiset.map (fun a => X - ↑C a) s) ∣ p
r : R
⊢ Multiset.prod (Multiset.map (fun a => X - ↑C a) (Multiset.filter (Eq r) s)) ∣ p
[PROOFSTEP]
exact (Multiset.prod_dvd_prod_of_le <| Multiset.map_le_map <| s.filter_le _).trans h
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
⊢ ∃ q,
    Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) * q = p ∧
      ↑Multiset.card (roots p) + natDegree q = natDegree p ∧ roots q = 0
[PROOFSTEP]
obtain ⟨q, he⟩ := p.prod_multiset_X_sub_C_dvd
[GOAL]
case intro
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
he : p = Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) * q
⊢ ∃ q,
    Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) * q = p ∧
      ↑Multiset.card (roots p) + natDegree q = natDegree p ∧ roots q = 0
[PROOFSTEP]
use q, he.symm
[GOAL]
case right
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
he : p = Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) * q
⊢ ↑Multiset.card (roots p) + natDegree q = natDegree p ∧ roots q = 0
[PROOFSTEP]
obtain rfl | hq := eq_or_ne q 0
[GOAL]
case right.inl
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
he : p = Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) * 0
⊢ ↑Multiset.card (roots p) + natDegree 0 = natDegree p ∧ roots 0 = 0
[PROOFSTEP]
rw [mul_zero] at he 
[GOAL]
case right.inl
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q p : R[X]
he : p = 0
⊢ ↑Multiset.card (roots p) + natDegree 0 = natDegree p ∧ roots 0 = 0
[PROOFSTEP]
subst he
[GOAL]
case right.inl
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
⊢ ↑Multiset.card (roots 0) + natDegree 0 = natDegree 0 ∧ roots 0 = 0
[PROOFSTEP]
simp
[GOAL]
case right.inr
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
he : p = Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) * q
hq : q ≠ 0
⊢ ↑Multiset.card (roots p) + natDegree q = natDegree p ∧ roots q = 0
[PROOFSTEP]
constructor
[GOAL]
case right.inr.left
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
he : p = Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) * q
hq : q ≠ 0
⊢ ↑Multiset.card (roots p) + natDegree q = natDegree p
[PROOFSTEP]
conv_rhs => rw [he]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
he : p = Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) * q
hq : q ≠ 0
| natDegree p
[PROOFSTEP]
rw [he]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
he : p = Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) * q
hq : q ≠ 0
| natDegree p
[PROOFSTEP]
rw [he]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
he : p = Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) * q
hq : q ≠ 0
| natDegree p
[PROOFSTEP]
rw [he]
[GOAL]
case right.inr.left
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
he : p = Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) * q
hq : q ≠ 0
⊢ ↑Multiset.card (roots p) + natDegree q = natDegree (Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) * q)
[PROOFSTEP]
rw [monic_prod_multiset_X_sub_C.natDegree_mul' hq, natDegree_multiset_prod_X_sub_C_eq_card]
[GOAL]
case right.inr.right
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
he : p = Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) * q
hq : q ≠ 0
⊢ roots q = 0
[PROOFSTEP]
replace he := congr_arg roots he.symm
[GOAL]
case right.inr.right
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
hq : q ≠ 0
he : roots (Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) * q) = roots p
⊢ roots q = 0
[PROOFSTEP]
rw [roots_mul, roots_multiset_prod_X_sub_C] at he 
[GOAL]
case right.inr.right
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
hq : q ≠ 0
he : roots p + roots q = roots p
⊢ roots q = 0
case right.inr.right
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p✝ q✝ p q : R[X]
hq : q ≠ 0
he : roots (Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) * q) = roots p
⊢ Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) * q ≠ 0
[PROOFSTEP]
exacts [add_right_eq_self.1 he, mul_ne_zero monic_prod_multiset_X_sub_C.ne_zero hq]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hp : Monic p
hroots : ↑Multiset.card (roots p) = natDegree p
⊢ Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) = p
[PROOFSTEP]
convert C_leadingCoeff_mul_prod_multiset_X_sub_C hroots
[GOAL]
case h.e'_2
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝¹ : CommRing R
inst✝ : IsDomain R
p q : R[X]
hp : Monic p
hroots : ↑Multiset.card (roots p) = natDegree p
⊢ Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)) =
    ↑C (leadingCoeff p) * Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p))
[PROOFSTEP]
rw [hp.leadingCoeff, C_1, one_mul]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝¹ : CommRing A
inst✝ : CommRing B
p : A[X]
f : A →+* B
hmap : map f p ≠ 0
a : A
⊢ rootMultiplicity a p ≤ rootMultiplicity (↑f a) (map f p)
[PROOFSTEP]
rw [le_rootMultiplicity_iff hmap]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝¹ : CommRing A
inst✝ : CommRing B
p : A[X]
f : A →+* B
hmap : map f p ≠ 0
a : A
⊢ (X - ↑C (↑f a)) ^ rootMultiplicity a p ∣ map f p
[PROOFSTEP]
refine' _root_.trans _ ((mapRingHom f).map_dvd (pow_rootMultiplicity_dvd p a))
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝¹ : CommRing A
inst✝ : CommRing B
p : A[X]
f : A →+* B
hmap : map f p ≠ 0
a : A
⊢ (X - ↑C (↑f a)) ^ rootMultiplicity a p ∣ ↑(mapRingHom f) ((X - ↑C a) ^ rootMultiplicity a p)
[PROOFSTEP]
rw [map_pow, map_sub, coe_mapRingHom, map_X, map_C]
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝¹ : CommRing A
inst✝ : CommRing B
p : A[X]
f : A →+* B
hf : Function.Injective ↑f
a : A
⊢ rootMultiplicity a p = rootMultiplicity (↑f a) (map f p)
[PROOFSTEP]
by_cases hp0 : p = 0
[GOAL]
case pos
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝¹ : CommRing A
inst✝ : CommRing B
p : A[X]
f : A →+* B
hf : Function.Injective ↑f
a : A
hp0 : p = 0
⊢ rootMultiplicity a p = rootMultiplicity (↑f a) (map f p)
[PROOFSTEP]
simp only [hp0, rootMultiplicity_zero, Polynomial.map_zero]
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝¹ : CommRing A
inst✝ : CommRing B
p : A[X]
f : A →+* B
hf : Function.Injective ↑f
a : A
hp0 : ¬p = 0
⊢ rootMultiplicity a p = rootMultiplicity (↑f a) (map f p)
[PROOFSTEP]
apply le_antisymm (le_rootMultiplicity_map ((Polynomial.map_ne_zero_iff hf).mpr hp0) a)
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝¹ : CommRing A
inst✝ : CommRing B
p : A[X]
f : A →+* B
hf : Function.Injective ↑f
a : A
hp0 : ¬p = 0
⊢ rootMultiplicity (↑f a) (map f p) ≤ rootMultiplicity a p
[PROOFSTEP]
rw [le_rootMultiplicity_iff hp0, ← map_dvd_map f hf ((monic_X_sub_C a).pow _), Polynomial.map_pow, Polynomial.map_sub,
  map_X, map_C]
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a✝ b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝¹ : CommRing A
inst✝ : CommRing B
p : A[X]
f : A →+* B
hf : Function.Injective ↑f
a : A
hp0 : ¬p = 0
⊢ (X - ↑C (↑f a)) ^ rootMultiplicity (↑f a) (map f p) ∣ map f p
[PROOFSTEP]
apply pow_rootMultiplicity_dvd
[GOAL]
R : Type u
S : Type v
T : Type w
a b✝ : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : DecidableEq B
p : A[X]
f : A →+* B
hmap : map f p ≠ 0
b : B
⊢ Multiset.count b (Multiset.map (↑f) (roots p)) ≤ rootMultiplicity b (map f p)
[PROOFSTEP]
rw [le_rootMultiplicity_iff hmap, ← Multiset.prod_replicate, ← Multiset.map_replicate fun a => X - C a]
[GOAL]
R : Type u
S : Type v
T : Type w
a b✝ : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : DecidableEq B
p : A[X]
f : A →+* B
hmap : map f p ≠ 0
b : B
⊢ Multiset.prod
      (Multiset.map (fun a => X - ↑C a) (Multiset.replicate (Multiset.count b (Multiset.map (↑f) (roots p))) b)) ∣
    map f p
[PROOFSTEP]
rw [← Multiset.filter_eq]
[GOAL]
R : Type u
S : Type v
T : Type w
a b✝ : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : DecidableEq B
p : A[X]
f : A →+* B
hmap : map f p ≠ 0
b : B
⊢ Multiset.prod (Multiset.map (fun a => X - ↑C a) (Multiset.filter (Eq b) (Multiset.map (↑f) (roots p)))) ∣ map f p
[PROOFSTEP]
refine (Multiset.prod_dvd_prod_of_le <| Multiset.map_le_map <| Multiset.filter_le (Eq b) _).trans ?_
[GOAL]
R : Type u
S : Type v
T : Type w
a b✝ : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : DecidableEq B
p : A[X]
f : A →+* B
hmap : map f p ≠ 0
b : B
⊢ Multiset.prod (Multiset.map (fun a => X - ↑C a) (Multiset.map (↑f) (roots p))) ∣ map f p
[PROOFSTEP]
convert Polynomial.map_dvd f p.prod_multiset_X_sub_C_dvd
[GOAL]
case h.e'_3
R : Type u
S : Type v
T : Type w
a b✝ : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : DecidableEq B
p : A[X]
f : A →+* B
hmap : map f p ≠ 0
b : B
⊢ Multiset.prod (Multiset.map (fun a => X - ↑C a) (Multiset.map (↑f) (roots p))) =
    map f (Multiset.prod (Multiset.map (fun a => X - ↑C a) (roots p)))
[PROOFSTEP]
simp only [Polynomial.map_multiset_prod, Multiset.map_map]
[GOAL]
case h.e'_3
R : Type u
S : Type v
T : Type w
a b✝ : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : DecidableEq B
p : A[X]
f : A →+* B
hmap : map f p ≠ 0
b : B
⊢ Multiset.prod (Multiset.map ((fun x => X - ↑C x) ∘ fun x => ↑f x) (roots p)) =
    Multiset.prod (Multiset.map (map f ∘ fun x => X - ↑C x) (roots p))
[PROOFSTEP]
congr
[GOAL]
case h.e'_3.e_a.e_f
R : Type u
S : Type v
T : Type w
a b✝ : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : DecidableEq B
p : A[X]
f : A →+* B
hmap : map f p ≠ 0
b : B
⊢ ((fun x => X - ↑C x) ∘ fun x => ↑f x) = map f ∘ fun x => X - ↑C x
[PROOFSTEP]
ext1
[GOAL]
case h.e'_3.e_a.e_f.h
R : Type u
S : Type v
T : Type w
a b✝ : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : DecidableEq B
p : A[X]
f : A →+* B
hmap : map f p ≠ 0
b : B
x✝ : A
⊢ ((fun x => X - ↑C x) ∘ fun x => ↑f x) x✝ = (map f ∘ fun x => X - ↑C x) x✝
[PROOFSTEP]
simp only [Function.comp_apply, Polynomial.map_sub, map_X, map_C]
[GOAL]
R : Type u
S : Type v
T : Type w
a b✝ : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : DecidableEq B
p : A[X]
f : A →+* B
hf : Function.Injective ↑f
b : B
⊢ Multiset.count b (Multiset.map (↑f) (roots p)) ≤ rootMultiplicity b (map f p)
[PROOFSTEP]
by_cases hp0 : p = 0
[GOAL]
case pos
R : Type u
S : Type v
T : Type w
a b✝ : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : DecidableEq B
p : A[X]
f : A →+* B
hf : Function.Injective ↑f
b : B
hp0 : p = 0
⊢ Multiset.count b (Multiset.map (↑f) (roots p)) ≤ rootMultiplicity b (map f p)
[PROOFSTEP]
simp only [hp0, roots_zero, Multiset.map_zero, Multiset.count_zero, Polynomial.map_zero, rootMultiplicity_zero]
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a b✝ : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : DecidableEq B
p : A[X]
f : A →+* B
hf : Function.Injective ↑f
b : B
hp0 : ¬p = 0
⊢ Multiset.count b (Multiset.map (↑f) (roots p)) ≤ rootMultiplicity b (map f p)
[PROOFSTEP]
exact count_map_roots ((Polynomial.map_ne_zero_iff hf).mpr hp0) b
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : IsDomain B
p : A[X]
f : A →+* B
h : map f p ≠ 0
⊢ Multiset.map (↑f) (roots p) ≤ roots (map f p)
[PROOFSTEP]
classical exact
  Multiset.le_iff_count.2 fun b => by
    rw [count_roots]
    apply count_map_roots h
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : IsDomain B
p : A[X]
f : A →+* B
h : map f p ≠ 0
⊢ Multiset.map (↑f) (roots p) ≤ roots (map f p)
[PROOFSTEP]
exact
  Multiset.le_iff_count.2 fun b => by
    rw [count_roots]
    apply count_map_roots h
[GOAL]
R : Type u
S : Type v
T : Type w
a b✝ : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : IsDomain B
p : A[X]
f : A →+* B
h : map f p ≠ 0
b : B
⊢ Multiset.count b (Multiset.map (↑f) (roots p)) ≤ Multiset.count b (roots (map f p))
[PROOFSTEP]
rw [count_roots]
[GOAL]
R : Type u
S : Type v
T : Type w
a b✝ : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : IsDomain B
p : A[X]
f : A →+* B
h : map f p ≠ 0
b : B
⊢ Multiset.count b (Multiset.map (↑f) (roots p)) ≤ rootMultiplicity b (map f p)
[PROOFSTEP]
apply count_map_roots h
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : IsDomain B
p : A[X]
f : A →+* B
hf : Function.Injective ↑f
⊢ Multiset.map (↑f) (roots p) ≤ roots (map f p)
[PROOFSTEP]
by_cases hp0 : p = 0
[GOAL]
case pos
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : IsDomain B
p : A[X]
f : A →+* B
hf : Function.Injective ↑f
hp0 : p = 0
⊢ Multiset.map (↑f) (roots p) ≤ roots (map f p)
[PROOFSTEP]
simp only [hp0, roots_zero, Multiset.map_zero, Polynomial.map_zero]
[GOAL]
case pos
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : IsDomain B
p : A[X]
f : A →+* B
hf : Function.Injective ↑f
hp0 : p = 0
⊢ 0 ≤ 0
[PROOFSTEP]
rfl
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : IsDomain B
p : A[X]
f : A →+* B
hf : Function.Injective ↑f
hp0 : ¬p = 0
⊢ Multiset.map (↑f) (roots p) ≤ roots (map f p)
[PROOFSTEP]
exact map_roots_le ((Polynomial.map_ne_zero_iff hf).mpr hp0)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : IsDomain B
p : A[X]
f : A →+* B
h : map f p ≠ 0
⊢ ↑Multiset.card (roots p) ≤ ↑Multiset.card (roots (map f p))
[PROOFSTEP]
rw [← p.roots.card_map f]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : IsDomain B
p : A[X]
f : A →+* B
h : map f p ≠ 0
⊢ ↑Multiset.card (Multiset.map (↑f) (roots p)) ≤ ↑Multiset.card (roots (map f p))
[PROOFSTEP]
exact Multiset.card_le_of_le (map_roots_le h)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : IsDomain B
p : A[X]
f : A →+* B
hf : Function.Injective ↑f
⊢ ↑Multiset.card (roots p) ≤ ↑Multiset.card (roots (map f p))
[PROOFSTEP]
by_cases hp0 : p = 0
[GOAL]
case pos
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : IsDomain B
p : A[X]
f : A →+* B
hf : Function.Injective ↑f
hp0 : p = 0
⊢ ↑Multiset.card (roots p) ≤ ↑Multiset.card (roots (map f p))
[PROOFSTEP]
simp only [hp0, roots_zero, Polynomial.map_zero, Multiset.card_zero]
[GOAL]
case pos
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : IsDomain B
p : A[X]
f : A →+* B
hf : Function.Injective ↑f
hp0 : p = 0
⊢ 0 ≤ 0
[PROOFSTEP]
rfl
[GOAL]
case neg
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : IsDomain B
p : A[X]
f : A →+* B
hf : Function.Injective ↑f
hp0 : ¬p = 0
⊢ ↑Multiset.card (roots p) ≤ ↑Multiset.card (roots (map f p))
[PROOFSTEP]
exact card_roots_le_map ((Polynomial.map_ne_zero_iff hf).mpr hp0)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : IsDomain B
p : A[X]
f : A →+* B
hf : Function.Injective ↑f
hroots : ↑Multiset.card (roots p) = natDegree p
⊢ Multiset.map (↑f) (roots p) = roots (map f p)
[PROOFSTEP]
apply Multiset.eq_of_le_of_card_le (map_roots_le_of_injective p hf)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
A : Type u_1
B : Type u_2
inst✝³ : CommRing A
inst✝² : CommRing B
inst✝¹ : IsDomain A
inst✝ : IsDomain B
p : A[X]
f : A →+* B
hf : Function.Injective ↑f
hroots : ↑Multiset.card (roots p) = natDegree p
⊢ ↑Multiset.card (roots (map f p)) ≤ ↑Multiset.card (Multiset.map (↑f) (roots p))
[PROOFSTEP]
simpa only [Multiset.card_map, hroots] using (card_roots' _).trans (natDegree_map_le f p)
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : Semiring R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
hf : IsUnit (leadingCoeff f)
H : IsUnit (map φ f)
⊢ IsUnit f
[PROOFSTEP]
have dz := degree_eq_zero_of_isUnit H
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : Semiring R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
hf : IsUnit (leadingCoeff f)
H : IsUnit (map φ f)
dz : degree (map φ f) = 0
⊢ IsUnit f
[PROOFSTEP]
rw [degree_map_eq_of_leadingCoeff_ne_zero] at dz 
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : Semiring R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
hf : IsUnit (leadingCoeff f)
H : IsUnit (map φ f)
dz : degree f = 0
⊢ IsUnit f
[PROOFSTEP]
rw [eq_C_of_degree_eq_zero dz]
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : Semiring R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
hf : IsUnit (leadingCoeff f)
H : IsUnit (map φ f)
dz : degree f = 0
⊢ IsUnit (↑C (coeff f 0))
[PROOFSTEP]
refine' IsUnit.map C _
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : Semiring R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
hf : IsUnit (leadingCoeff f)
H : IsUnit (map φ f)
dz : degree f = 0
⊢ IsUnit (coeff f 0)
[PROOFSTEP]
convert hf
[GOAL]
case h.e'_3
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : Semiring R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
hf : IsUnit (leadingCoeff f)
H : IsUnit (map φ f)
dz : degree f = 0
⊢ coeff f 0 = leadingCoeff f
[PROOFSTEP]
change coeff f 0 = coeff f (natDegree f)
[GOAL]
case h.e'_3
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : Semiring R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
hf : IsUnit (leadingCoeff f)
H : IsUnit (map φ f)
dz : degree f = 0
⊢ coeff f 0 = coeff f (natDegree f)
[PROOFSTEP]
rw [(degree_eq_iff_natDegree_eq _).1 dz]
[GOAL]
case h.e'_3
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : Semiring R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
hf : IsUnit (leadingCoeff f)
H : IsUnit (map φ f)
dz : degree f = 0
⊢ coeff f 0 = coeff f Zero.zero
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : Semiring R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
hf : IsUnit (leadingCoeff f)
H : IsUnit (map φ f)
dz : degree f = 0
⊢ f ≠ 0
[PROOFSTEP]
rfl
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : Semiring R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
hf : IsUnit (leadingCoeff f)
H : IsUnit (map φ f)
dz : degree f = 0
⊢ f ≠ 0
[PROOFSTEP]
rintro rfl
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : Semiring R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
hf : IsUnit (leadingCoeff 0)
H : IsUnit (map φ 0)
dz : degree 0 = 0
⊢ False
[PROOFSTEP]
simp at H 
[GOAL]
case hf
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : Semiring R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
hf : IsUnit (leadingCoeff f)
H : IsUnit (map φ f)
dz : degree (map φ f) = 0
⊢ ↑φ (leadingCoeff f) ≠ 0
[PROOFSTEP]
intro h
[GOAL]
case hf
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : Semiring R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
hf : IsUnit (leadingCoeff f)
H : IsUnit (map φ f)
dz : degree (map φ f) = 0
h : ↑φ (leadingCoeff f) = 0
⊢ False
[PROOFSTEP]
have u : IsUnit (φ f.leadingCoeff) := IsUnit.map φ hf
[GOAL]
case hf
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : Semiring R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
hf : IsUnit (leadingCoeff f)
H : IsUnit (map φ f)
dz : degree (map φ f) = 0
h : ↑φ (leadingCoeff f) = 0
u : IsUnit (↑φ (leadingCoeff f))
⊢ False
[PROOFSTEP]
rw [h] at u 
[GOAL]
case hf
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝² : Semiring R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
hf : IsUnit (leadingCoeff f)
H : IsUnit (map φ f)
dz : degree (map φ f) = 0
h : ↑φ (leadingCoeff f) = 0
u : IsUnit 0
⊢ False
[PROOFSTEP]
simp at u 
[GOAL]
R : Type u
S : Type v
T : Type w
a b : R
n : ℕ
inst✝³ : CommRing R
inst✝² : IsDomain R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
h_mon : Monic f
h_irr : Irreducible (Polynomial.map φ f)
⊢ Irreducible f
[PROOFSTEP]
refine' ⟨h_irr.not_unit ∘ IsUnit.map (mapRingHom φ), fun a b h => _⟩
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝³ : CommRing R
inst✝² : IsDomain R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
h_mon : Monic f
h_irr : Irreducible (Polynomial.map φ f)
a b : R[X]
h : f = a * b
⊢ IsUnit a ∨ IsUnit b
[PROOFSTEP]
dsimp [Monic] at h_mon 
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝³ : CommRing R
inst✝² : IsDomain R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
h_mon : Polynomial.leadingCoeff f = 1
h_irr : Irreducible (Polynomial.map φ f)
a b : R[X]
h : f = a * b
⊢ IsUnit a ∨ IsUnit b
[PROOFSTEP]
have q := (leadingCoeff_mul a b).symm
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝³ : CommRing R
inst✝² : IsDomain R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
h_mon : Polynomial.leadingCoeff f = 1
h_irr : Irreducible (Polynomial.map φ f)
a b : R[X]
h : f = a * b
q : Polynomial.leadingCoeff a * Polynomial.leadingCoeff b = Polynomial.leadingCoeff (a * b)
⊢ IsUnit a ∨ IsUnit b
[PROOFSTEP]
rw [← h, h_mon] at q 
[GOAL]
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝³ : CommRing R
inst✝² : IsDomain R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
h_mon : Polynomial.leadingCoeff f = 1
h_irr : Irreducible (Polynomial.map φ f)
a b : R[X]
h : f = a * b
q : Polynomial.leadingCoeff a * Polynomial.leadingCoeff b = 1
⊢ IsUnit a ∨ IsUnit b
[PROOFSTEP]
refine' (h_irr.isUnit_or_isUnit <| (congr_arg (Polynomial.map φ) h).trans (Polynomial.map_mul φ)).imp _ _
[GOAL]
case refine'_1
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝³ : CommRing R
inst✝² : IsDomain R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
h_mon : Polynomial.leadingCoeff f = 1
h_irr : Irreducible (Polynomial.map φ f)
a b : R[X]
h : f = a * b
q : Polynomial.leadingCoeff a * Polynomial.leadingCoeff b = 1
⊢ IsUnit (Polynomial.map φ a) → IsUnit a
[PROOFSTEP]
apply isUnit_of_isUnit_leadingCoeff_of_isUnit_map
[GOAL]
case refine'_2
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝³ : CommRing R
inst✝² : IsDomain R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
h_mon : Polynomial.leadingCoeff f = 1
h_irr : Irreducible (Polynomial.map φ f)
a b : R[X]
h : f = a * b
q : Polynomial.leadingCoeff a * Polynomial.leadingCoeff b = 1
⊢ IsUnit (Polynomial.map φ b) → IsUnit b
[PROOFSTEP]
apply isUnit_of_isUnit_leadingCoeff_of_isUnit_map
[GOAL]
case refine'_1.hf
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝³ : CommRing R
inst✝² : IsDomain R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
h_mon : Polynomial.leadingCoeff f = 1
h_irr : Irreducible (Polynomial.map φ f)
a b : R[X]
h : f = a * b
q : Polynomial.leadingCoeff a * Polynomial.leadingCoeff b = 1
⊢ IsUnit (Polynomial.leadingCoeff a)
[PROOFSTEP]
apply isUnit_of_mul_eq_one
[GOAL]
case refine'_2.hf
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝³ : CommRing R
inst✝² : IsDomain R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
h_mon : Polynomial.leadingCoeff f = 1
h_irr : Irreducible (Polynomial.map φ f)
a b : R[X]
h : f = a * b
q : Polynomial.leadingCoeff a * Polynomial.leadingCoeff b = 1
⊢ IsUnit (Polynomial.leadingCoeff b)
[PROOFSTEP]
apply isUnit_of_mul_eq_one
[GOAL]
case refine'_1.hf.h
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝³ : CommRing R
inst✝² : IsDomain R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
h_mon : Polynomial.leadingCoeff f = 1
h_irr : Irreducible (Polynomial.map φ f)
a b : R[X]
h : f = a * b
q : Polynomial.leadingCoeff a * Polynomial.leadingCoeff b = 1
⊢ Polynomial.leadingCoeff a * ?refine'_1.hf.b = 1
[PROOFSTEP]
exact q
[GOAL]
case refine'_2.hf.h
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝³ : CommRing R
inst✝² : IsDomain R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
h_mon : Polynomial.leadingCoeff f = 1
h_irr : Irreducible (Polynomial.map φ f)
a b : R[X]
h : f = a * b
q : Polynomial.leadingCoeff a * Polynomial.leadingCoeff b = 1
⊢ Polynomial.leadingCoeff b * ?refine'_2.hf.b = 1
[PROOFSTEP]
rw [mul_comm]
[GOAL]
case refine'_2.hf.h
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝³ : CommRing R
inst✝² : IsDomain R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
h_mon : Polynomial.leadingCoeff f = 1
h_irr : Irreducible (Polynomial.map φ f)
a b : R[X]
h : f = a * b
q : Polynomial.leadingCoeff a * Polynomial.leadingCoeff b = 1
⊢ ?refine'_2.hf.h.b * Polynomial.leadingCoeff b = 1
case refine'_2.hf.h.b
R : Type u
S : Type v
T : Type w
a✝ b✝ : R
n : ℕ
inst✝³ : CommRing R
inst✝² : IsDomain R
inst✝¹ : CommRing S
inst✝ : IsDomain S
φ : R →+* S
f : R[X]
h_mon : Polynomial.leadingCoeff f = 1
h_irr : Irreducible (Polynomial.map φ f)
a b : R[X]
h : f = a * b
q : Polynomial.leadingCoeff a * Polynomial.leadingCoeff b = 1
⊢ R
[PROOFSTEP]
exact q
