Theory Berlekamp_Zassenhaus.Unique_Factorization_Poly

(*  
    Author:      René Thiemann 
                 Akihisa Yamada
    License:     BSD
*)
section ‹Unique Factorization Domain for Polynomials›

text ‹In this theory we prove that the polynomials over a unique factorization domain (UFD) form a UFD.›

theory Unique_Factorization_Poly
imports
  Unique_Factorization
  Polynomial_Factorization.Missing_Polynomial_Factorial 
  Subresultants.More_Homomorphisms 
  "HOL-Computational_Algebra.Field_as_Ring"
begin

hide_const (open) module.smult
hide_const (open) Divisibility.irreducible

instantiation fract :: (idom) "{normalization_euclidean_semiring, euclidean_ring}"
begin

definition [simp]: "normalize_fract ≡ (normalize_field :: 'a fract ⇒ _)"
definition [simp]: "unit_factor_fract = (unit_factor_field :: 'a fract ⇒ _)"
definition [simp]: "euclidean_size_fract = (euclidean_size_field :: 'a fract ⇒ _)"
definition [simp]: "modulo_fract = (mod_field :: 'a fract ⇒ _)"

instance by standard (simp_all add: dvd_field_iff divide_simps)

end

instantiation fract :: (idom) euclidean_ring_gcd
begin

definition gcd_fract :: "'a fract ⇒ 'a fract ⇒ 'a fract" where
  "gcd_fract ≡ Euclidean_Algorithm.gcd"
definition lcm_fract :: "'a fract ⇒ 'a fract ⇒ 'a fract" where
  "lcm_fract ≡ Euclidean_Algorithm.lcm"
definition Gcd_fract :: "'a fract set ⇒ 'a fract" where
 "Gcd_fract ≡ Euclidean_Algorithm.Gcd"
definition Lcm_fract :: "'a fract set ⇒ 'a fract" where
 "Lcm_fract ≡ Euclidean_Algorithm.Lcm"

instance
  by (standard, simp_all add: gcd_fract_def lcm_fract_def Gcd_fract_def Lcm_fract_def)

end
(*field + unique_euclidean_ring + euclidean_ring_gcd + normalization_semidom_multiplicative*)

instantiation fract :: (idom) unique_euclidean_ring
begin

definition [simp]: "division_segment_fract (x :: 'a fract) = (1 :: 'a fract)"

instance by standard (auto split: if_splits)
end

instance fract :: (idom) field_gcd by standard auto


definition divides_ff :: "'a::idom fract ⇒ 'a fract ⇒ bool"
  where "divides_ff x y ≡ ∃ r. y = x * to_fract r"

lemma ff_list_pairs: 
  "∃ xs. X = map (λ (x,y). Fraction_Field.Fract x y) xs ∧ 0 ∉ snd ` set xs"
proof (induct X)
  case (Cons a X)
  from Cons(1) obtain xs where X: "X = map (λ (x,y). Fraction_Field.Fract x y)  xs" and xs: "0 ∉ snd ` set xs"
    by auto
  obtain x y where a: "a = Fraction_Field.Fract x y" and y: "y ≠ 0" by (cases a, auto)
  show ?case unfolding X a using xs y
    by (intro exI[of _ "(x,y) # xs"], auto)
qed auto

lemma divides_ff_to_fract[simp]: "divides_ff (to_fract x) (to_fract y) ⟷ x dvd y"
  unfolding divides_ff_def dvd_def
  by (simp add: to_fract_def eq_fract(1) mult.commute)

lemma
  shows divides_ff_mult_cancel_left[simp]: "divides_ff (z * x) (z * y) ⟷ z = 0 ∨ divides_ff x y"
    and divides_ff_mult_cancel_right[simp]: "divides_ff (x * z) (y * z) ⟷ z = 0 ∨ divides_ff x y"
  unfolding divides_ff_def by auto

definition gcd_ff_list :: "'a::ufd fract list ⇒ 'a fract ⇒ bool" where
  "gcd_ff_list X g = (
     (∀ x ∈ set X. divides_ff g x) ∧ 
     (∀ d. (∀ x ∈ set X. divides_ff d x) ⟶ divides_ff d g))"

lemma gcd_ff_list_exists: "∃ g. gcd_ff_list (X :: 'a::ufd fract list) g"
proof -
  interpret some_gcd: idom_gcd "(*)" "1 :: 'a" "(+)" 0 "(-)" uminus some_gcd
    rewrites "dvd.dvd ((*)) = (dvd)" by (unfold_locales, auto simp: dvd_rewrites)
  from ff_list_pairs[of X] obtain xs where X: "X = map (λ (x,y). Fraction_Field.Fract x y) xs"
    and xs: "0 ∉ snd ` set xs" by auto
  define r where "r ≡ prod_list (map snd xs)"
  have r: "r ≠ 0" unfolding r_def prod_list_zero_iff using xs by auto
  define ys where "ys ≡ map (λ (x,y). x * prod_list (remove1 y (map snd xs))) xs"
  {
    fix i
    assume "i < length X"
    hence i: "i < length xs" unfolding X by auto
    obtain x y where xsi: "xs ! i = (x,y)" by force
    with i have "(x,y) ∈ set xs" unfolding set_conv_nth by force
    hence y_mem: "y ∈ set (map snd xs)" by force
    with xs have y: "y ≠ 0" by force
    from i have id1: "ys ! i = x * prod_list (remove1 y (map snd xs))" unfolding ys_def using xsi by auto
    from i xsi have id2: "X ! i = Fraction_Field.Fract x y" unfolding X by auto
    have lp: "prod_list (remove1 y (map snd xs)) * y = r" unfolding r_def
      by (rule prod_list_remove1[OF y_mem])
    have "ys ! i ∈ set ys" using i unfolding ys_def by auto
    moreover have "to_fract (ys ! i) = to_fract r * (X ! i)"
      unfolding id1 id2 to_fract_def mult_fract
      by (subst eq_fract(1), force, force simp: y, simp add: lp)
    ultimately have "ys ! i ∈ set ys" "to_fract (ys ! i) = to_fract r * (X ! i)" .
  } note ys = this
  define G where "G ≡ some_gcd.listgcd ys"
  define g where "g ≡ to_fract G * Fraction_Field.Fract 1 r"
  have len: "length X = length ys" unfolding X ys_def by auto
  show ?thesis
  proof (rule exI[of _ g], unfold gcd_ff_list_def, intro ballI conjI impI allI)
    fix x
    assume "x ∈ set X"
    then obtain i where i: "i < length X" and x: "x = X ! i" unfolding set_conv_nth by auto
    from ys[OF i] have id: "to_fract (ys ! i) = to_fract r * x" 
      and ysi: "ys ! i ∈ set ys" unfolding x by auto
    from some_gcd.listgcd[OF ysi] have "G dvd ys ! i" unfolding G_def .
    then obtain d where ysi: "ys ! i = G * d" unfolding dvd_def by auto
    have "to_fract d * (to_fract G * Fraction_Field.Fract 1 r) = x * (to_fract r * Fraction_Field.Fract 1 r)" 
      using id[unfolded ysi]
      by (simp add: ac_simps)
    also have "… = x" using r unfolding to_fract_def by (simp add: eq_fract One_fract_def)
    finally have "to_fract d * (to_fract G * Fraction_Field.Fract 1 r) = x" by simp
    thus "divides_ff g x" unfolding divides_ff_def g_def 
      by (intro exI[of _ d], auto)
  next
    fix d
    assume "∀x ∈ set X. divides_ff d x"
    hence "Ball ((λ x. to_fract r * x) ` set X) ( divides_ff (to_fract r * d))" by simp
    also have "(λ x. to_fract r * x) ` set X = to_fract ` set ys"
      unfolding set_conv_nth using ys len by force
    finally have dvd: "Ball (set ys) (λ y. divides_ff (to_fract r * d) (to_fract y))" by auto
    obtain nd dd where d: "d = Fraction_Field.Fract nd dd" and dd: "dd ≠ 0" by (cases d, auto)
    {
      fix y
      assume "y ∈ set ys"
      hence "divides_ff (to_fract r * d) (to_fract y)" using dvd by auto
      from this[unfolded divides_ff_def d to_fract_def mult_fract]
      obtain ra where "Fraction_Field.Fract y 1 = Fraction_Field.Fract (r * nd * ra) dd" by auto
      hence "y * dd = ra * (r * nd)" by (simp add: eq_fract dd)
      hence "r * nd dvd y * dd" by auto
    }
    hence "r * nd dvd some_gcd.listgcd ys * dd" by (rule some_gcd.listgcd_greatest_mult)
    hence "divides_ff (to_fract r * d) (to_fract G)" unfolding to_fract_def d mult_fract
      G_def divides_ff_def by (auto simp add: eq_fract dd dvd_def)
    also have "to_fract G = to_fract r * g" unfolding g_def using r
      by (auto simp: to_fract_def eq_fract)
    finally show "divides_ff d g" using r by simp
  qed
qed

definition some_gcd_ff_list :: "'a :: ufd fract list ⇒ 'a fract" where
  "some_gcd_ff_list xs = (SOME g. gcd_ff_list xs g)"

lemma some_gcd_ff_list: "gcd_ff_list xs (some_gcd_ff_list xs)"
  unfolding some_gcd_ff_list_def using gcd_ff_list_exists[of xs]
  by (rule someI_ex)

lemma some_gcd_ff_list_divides: "x ∈ set xs ⟹ divides_ff (some_gcd_ff_list xs) x"
  using some_gcd_ff_list[of xs] unfolding gcd_ff_list_def by auto

lemma some_gcd_ff_list_greatest: "(∀x ∈ set xs. divides_ff d x) ⟹ divides_ff d (some_gcd_ff_list xs)"
  using some_gcd_ff_list[of xs] unfolding gcd_ff_list_def by auto

lemma divides_ff_refl[simp]: "divides_ff x x"
  unfolding divides_ff_def
  by (rule exI[of _ 1], auto simp: to_fract_def One_fract_def)

lemma divides_ff_trans:
  "divides_ff x y ⟹ divides_ff y z ⟹ divides_ff x z"
  unfolding divides_ff_def
  by (auto simp del: to_fract_hom.hom_mult simp add: to_fract_hom.hom_mult[symmetric])

lemma divides_ff_mult_right: "a ≠ 0 ⟹ divides_ff (x * inverse a) y ⟹ divides_ff x (a * y)"
  unfolding divides_ff_def divide_inverse[symmetric] by auto

definition eq_dff :: "'a :: ufd fract ⇒ 'a fract ⇒ bool" (infix "=dff" 50) where
  "x =dff y ⟷ divides_ff x y ∧ divides_ff y x"

lemma eq_dffI[intro]: "divides_ff x y ⟹ divides_ff y x ⟹ x =dff y" 
  unfolding eq_dff_def by auto

lemma eq_dff_refl[simp]: "x =dff x"
  by (intro eq_dffI, auto)

lemma eq_dff_sym: "x =dff y ⟹ y =dff x" unfolding eq_dff_def by auto

lemma eq_dff_trans[trans]: "x =dff y ⟹ y =dff z ⟹ x =dff z"
  unfolding eq_dff_def using divides_ff_trans by auto

lemma eq_dff_cancel_right[simp]: "x * y =dff x * z ⟷ x = 0 ∨ y =dff z" 
  unfolding eq_dff_def by auto

lemma eq_dff_mult_right_trans[trans]: "x =dff y * z ⟹ z =dff u ⟹ x =dff y * u"
  using eq_dff_trans by force

lemma some_gcd_ff_list_smult: "a ≠ 0 ⟹ some_gcd_ff_list (map ((*) a) xs) =dff a * some_gcd_ff_list xs"
proof 
  let ?g = "some_gcd_ff_list (map ((*) a) xs)"
  show "divides_ff (a * some_gcd_ff_list xs) ?g"
    by (rule some_gcd_ff_list_greatest, insert some_gcd_ff_list_divides[of _ xs], auto simp: divides_ff_def)
  assume a: "a ≠ 0"
  show "divides_ff ?g (a * some_gcd_ff_list xs)"
  proof (rule divides_ff_mult_right[OF a some_gcd_ff_list_greatest], intro ballI)
    fix x
    assume x: "x ∈ set xs"
    have "divides_ff (?g * inverse a) x = divides_ff (inverse a * ?g) (inverse a * (a * x))"
      using a by (simp add: field_simps)
    also have "…" using a x by (auto intro: some_gcd_ff_list_divides)
    finally show "divides_ff (?g * inverse a) x" .
  qed
qed

definition content_ff :: "'a::ufd fract poly ⇒ 'a fract" where 
  "content_ff p = some_gcd_ff_list (coeffs p)"

lemma content_ff_iff: "divides_ff x (content_ff p) ⟷ (∀ c ∈ set (coeffs p). divides_ff x c)" (is "?l = ?r")
proof
  assume ?l
  from divides_ff_trans[OF this, unfolded content_ff_def, OF some_gcd_ff_list_divides] show ?r ..
next
  assume ?r
  thus ?l unfolding content_ff_def by (intro some_gcd_ff_list_greatest, auto)
qed

lemma content_ff_divides_ff: "x ∈ set (coeffs p) ⟹ divides_ff (content_ff p) x"
  unfolding content_ff_def by (rule some_gcd_ff_list_divides)

lemma content_ff_0[simp]: "content_ff 0 = 0"
  using content_ff_iff[of 0 0] by (auto simp: divides_ff_def)

lemma content_ff_0_iff[simp]: "(content_ff p = 0) = (p = 0)"
proof (cases "p = 0")
  case False
  define a where "a ≡ last (coeffs p)"
  define xs where "xs ≡ coeffs p"
  from False
  have mem: "a ∈ set (coeffs p)" and a: "a ≠ 0"
    unfolding a_def last_coeffs_eq_coeff_degree[OF False] coeffs_def by auto
  from content_ff_divides_ff[OF mem] have "divides_ff (content_ff p) a" .
  with a have "content_ff p ≠ 0" unfolding divides_ff_def by auto
  with False show ?thesis by auto
qed auto

lemma content_ff_eq_dff_nonzero: "content_ff p =dff x ⟹ x ≠ 0 ⟹ p ≠ 0"
  using divides_ff_def eq_dff_def by force

lemma content_ff_smult: "content_ff (smult (a::'a::ufd fract) p) =dff a * content_ff p"
proof (cases "a = 0")
  case False note a = this
  have id: "coeffs (smult a p) = map ((*) a) (coeffs p)"
    unfolding coeffs_smult using a by (simp add: Polynomial.coeffs_smult)
  show ?thesis unfolding content_ff_def id using some_gcd_ff_list_smult[OF a] .
qed simp

definition normalize_content_ff
  where "normalize_content_ff (p::'a::ufd fract poly) ≡ smult (inverse (content_ff p)) p"

lemma smult_normalize_content_ff: "smult (content_ff p) (normalize_content_ff p) = p"  
  unfolding normalize_content_ff_def
  by (cases "p = 0", auto)

lemma content_ff_normalize_content_ff_1: assumes p0: "p ≠ 0" 
  shows "content_ff (normalize_content_ff p) =dff 1"
proof -
  have "content_ff p = content_ff (smult (content_ff p) (normalize_content_ff p))" unfolding smult_normalize_content_ff ..
  also have "… =dff content_ff p * content_ff (normalize_content_ff p)" by (rule content_ff_smult)
  finally show ?thesis unfolding eq_dff_def divides_ff_def using p0 by auto
qed

lemma content_ff_to_fract: assumes "set (coeffs p) ⊆ range to_fract"
  shows "content_ff p ∈ range to_fract"
proof -
  have "divides_ff 1 (content_ff p)" using assms
    unfolding content_ff_iff unfolding divides_ff_def[abs_def] by auto
  thus ?thesis unfolding divides_ff_def by auto
qed

lemma content_ff_map_poly_to_fract: "content_ff (map_poly to_fract (p :: 'a :: ufd poly)) ∈ range to_fract"
  by (rule content_ff_to_fract, subst coeffs_map_poly, auto)

lemma range_coeffs_to_fract: assumes "set (coeffs p) ⊆ range to_fract" 
  shows "∃ m. coeff p i = to_fract m"
proof -
  from assms(1) to_fract_0 have "coeff p i ∈ range to_fract" using range_coeff [of p]
    by auto (metis contra_subsetD to_fract_hom.hom_zero insertE range_eqI)
  thus ?thesis by auto
qed

lemma divides_ff_coeff: assumes "set (coeffs p) ⊆ range to_fract" and "divides_ff (to_fract n) (coeff p i)"
  shows "∃ m. coeff p i = to_fract n * to_fract m"
proof -
  from range_coeffs_to_fract[OF assms(1)]  obtain k where pi: "coeff p i = to_fract k" by auto
  from assms(2)[unfolded this] have "n dvd k" by simp
  then obtain j where k: "k = n * j" unfolding Rings.dvd_def by auto
  show ?thesis unfolding pi k by auto
qed

definition inv_embed :: "'a :: ufd fract ⇒ 'a" where
  "inv_embed = the_inv to_fract"

lemma inv_embed[simp]: "inv_embed (to_fract x) = x"
  unfolding inv_embed_def
  by (rule the_inv_f_f, auto simp: inj_on_def)

lemma inv_embed_0[simp]: "inv_embed 0 = 0" unfolding to_fract_0[symmetric] inv_embed by simp

lemma range_to_fract_embed_poly: assumes "set (coeffs p) ⊆ range to_fract"
  shows "p = map_poly to_fract (map_poly inv_embed p)"
proof -
  have "p = map_poly (to_fract o inv_embed) p"
    by (rule sym, rule map_poly_idI, insert assms, auto)
  also have "… = map_poly to_fract (map_poly inv_embed p)" 
    by (subst map_poly_map_poly, auto)
  finally show ?thesis .
qed

lemma content_ff_to_fract_coeffs_to_fract: assumes "content_ff p ∈ range to_fract"
  shows "set (coeffs p) ⊆ range to_fract"
proof 
  fix x
  assume "x ∈ set (coeffs p)"
  from content_ff_divides_ff[OF this] assms[unfolded eq_dff_def] show "x ∈ range to_fract"
    unfolding divides_ff_def by (auto simp del: to_fract_hom.hom_mult simp: to_fract_hom.hom_mult[symmetric])
qed

lemma content_ff_1_coeffs_to_fract: assumes "content_ff p =dff 1"
  shows "set (coeffs p) ⊆ range to_fract"
proof 
  fix x
  assume "x ∈ set (coeffs p)"
  from content_ff_divides_ff[OF this] assms[unfolded eq_dff_def] show "x ∈ range to_fract"
    unfolding divides_ff_def by (auto simp del: to_fract_hom.hom_mult simp: to_fract_hom.hom_mult[symmetric])
qed

lemma gauss_lemma:
  fixes p q :: "'a :: ufd fract poly"
  shows "content_ff (p * q) =dff content_ff p * content_ff q"
proof (cases "p = 0 ∨ q = 0")
  case False
  hence p: "p ≠ 0" and q: "q ≠ 0" by auto
  let ?c = "content_ff :: 'a fract poly ⇒ 'a fract"
  {
    fix p q :: "'a fract poly"
    assume cp1: "?c p =dff 1" and cq1: "?c q =dff 1"
    define ip where "ip ≡ map_poly inv_embed p"
    define iq where "iq ≡ map_poly inv_embed q"
    interpret map_poly_hom: map_poly_comm_ring_hom to_fract..
    from content_ff_1_coeffs_to_fract[OF cp1] have cp: "set (coeffs p) ⊆ range to_fract" .
    from content_ff_1_coeffs_to_fract[OF cq1] have cq: "set (coeffs q) ⊆ range to_fract" .
    have ip: "p = map_poly to_fract ip" unfolding ip_def
      by (rule range_to_fract_embed_poly[OF cp])
    have iq: "q = map_poly to_fract iq" unfolding iq_def
      by (rule range_to_fract_embed_poly[OF cq])
    have cpq0: "?c (p * q) ≠ 0"
      unfolding content_ff_0_iff using cp1 cq1 content_ff_eq_dff_nonzero[of _ 1] by auto
    have cpq: "set (coeffs (p * q)) ⊆ range to_fract" unfolding ip iq
    unfolding map_poly_hom.hom_mult[symmetric] to_fract_hom.coeffs_map_poly_hom by auto
    have ctnt: "?c (p * q) ∈ range to_fract" using content_ff_to_fract[OF cpq] .
    then obtain cpq where id: "?c (p * q) = to_fract cpq" by auto
    have dvd: "divides_ff 1 (?c (p * q))" using ctnt unfolding divides_ff_def by auto
    from cpq0[unfolded id] have cpq0: "cpq ≠ 0" unfolding to_fract_def Zero_fract_def by auto
    hence cpqM: "cpq ∈ carrier mk_monoid" by auto
    have "?c (p * q) =dff 1"
    proof (rule ccontr)
      assume "¬ ?c (p * q) =dff 1"
      with dvd have "¬ divides_ff (?c (p * q)) 1"
        unfolding eq_dff_def by auto
      from this[unfolded id divides_ff_def] have cpq: "⋀ r. cpq * r ≠ 1" 
        by (auto simp: to_fract_def One_fract_def eq_fract)
      then have cpq1: "¬ cpq dvd 1" by (auto elim:dvdE simp:ac_simps)
      from mset_factors_exist[OF cpq0 cpq1]
      obtain F where F: "mset_factors F cpq" by auto
      have "F ≠ {#}" using F by auto
      then obtain f where f: "f ∈# F" by auto
      with F have irrf: "irreducible f" and f0: "f ≠ 0" by (auto dest: mset_factorsD)
      from irrf have pf: "prime_elem f" by simp
      note * = this[unfolded prime_elem_def]
      from * have no_unit: "¬ f dvd 1" by auto
      from * f0 have prime: "⋀ a b. f dvd a * b ⟹ f dvd a ∨ f dvd b" unfolding dvd_def by force
      let ?f = "to_fract f"
      from F f
      have fdvd: "f dvd cpq" by (auto intro:mset_factors_imp_dvd)
      hence "divides_ff ?f (to_fract cpq)" by simp
      from divides_ff_trans[OF this, folded id, OF content_ff_divides_ff] 
      have dvd: "⋀ z. z ∈ set (coeffs (p * q)) ⟹ divides_ff ?f z" .
      {
        fix p :: "'a fract poly"
        assume cp: "?c p =dff 1" 
        let ?P = "λ i. ¬ divides_ff ?f (coeff p i)"
        {
          assume "∀ c ∈ set (coeffs p). divides_ff ?f c"           
          hence n: "divides_ff ?f (?c p)" unfolding content_ff_iff by auto
          from divides_ff_trans[OF this] cp[unfolded eq_dff_def] have "divides_ff ?f 1" by auto
          also have "1 = to_fract 1" by simp
          finally have "f dvd 1" by (unfold divides_ff_to_fract)
          hence False using no_unit unfolding dvd_def by (auto simp: ac_simps)
        }
        then obtain cp where cp: "cp ∈ set (coeffs p)" and ncp: "¬ divides_ff ?f cp" by auto
        hence "cp ∈ range (coeff p)" unfolding range_coeff by auto
        with ncp have "∃ i. ?P i" by auto
        from LeastI_ex[OF this] not_less_Least[of _ ?P]
        have "∃ i. ?P i ∧ (∀ j. j < i ⟶ divides_ff ?f (coeff p j))" by blast
      } note cont = this
      from cont[OF cp1] obtain r where 
        r: "¬ divides_ff ?f (coeff p r)" and r': "⋀ i. i < r ⟹ divides_ff ?f (coeff p i)" by auto
      have "∀ i. ∃ k. i < r ⟶ coeff p i = ?f * to_fract k" using divides_ff_coeff[OF cp r'] by blast
      from choice[OF this] obtain rr where r': "⋀ i. i < r ⟹ coeff p i = ?f * to_fract (rr i)" by blast
      let ?r = "coeff p r"
      from cont[OF cq1] obtain s where 
        s: "¬ divides_ff ?f (coeff q s)" and s': "⋀ i. i < s ⟹ divides_ff ?f (coeff q i)" by auto
      have "∀ i. ∃ k. i < s ⟶ coeff q i = ?f * to_fract k" using divides_ff_coeff[OF cq s'] by blast
      from choice[OF this] obtain ss where s': "⋀ i. i < s ⟹ coeff q i = ?f * to_fract (ss i)" by blast
      from range_coeffs_to_fract[OF cp] have "∀ i. ∃ m. coeff p i = to_fract m" ..
      from choice[OF this] obtain pi where pi: "⋀ i. coeff p i = to_fract (pi i)" by blast
      from range_coeffs_to_fract[OF cq] have "∀ i. ∃ m. coeff q i = to_fract m" ..
      from choice[OF this] obtain qi where qi: "⋀ i. coeff q i = to_fract (qi i)" by blast
      let ?s = "coeff q s"
      let ?g = "λ i. coeff p i * coeff q (r + s - i)"
      define a where "a = (∑i∈{..<r}. (rr i * qi (r + s - i)))"
      define b where "b = (∑ i ∈ {Suc r..r + s}. pi i * (ss (r + s - i)))" 
      have "coeff (p * q) (r + s) = (∑i≤r + s. ?g i)" unfolding coeff_mult ..
      also have "{..r+s} = {..< r} ∪ {r .. r+s}" by auto
      also have "(∑i∈{..<r} ∪ {r..r + s}. ?g i)
        = (∑i∈{..<r}. ?g i) + (∑ i ∈ {r..r + s}. ?g i)" 
        by (rule sum.union_disjoint, auto)
      also have "(∑i∈{..<r}. ?g i) = (∑i∈{..<r}. ?f * (to_fract (rr i) * to_fract (qi (r + s - i))))"
        by (rule sum.cong[OF refl], insert r' qi, auto)
      also have "… = to_fract (f * a)" by (simp add: a_def sum_distrib_left)
      also have "(∑ i ∈ {r..r + s}. ?g i) = ?g r + (∑ i ∈ {Suc r..r + s}. ?g i)"
        by (subst sum.remove[of _ r], auto intro: sum.cong)
      also have "(∑ i ∈ {Suc r..r + s}. ?g i) = (∑ i ∈ {Suc r..r + s}. ?f * (to_fract (pi i) * to_fract (ss (r + s - i))))"
        by (rule sum.cong[OF refl], insert s' pi, auto)
      also have "… = to_fract (f * b)" by (simp add: sum_distrib_left b_def)
      finally have cpq: "coeff (p * q) (r + s) = to_fract (f * (a + b)) + ?r * ?s" by (simp add: field_simps)
      {
        fix i
        from dvd[of "coeff (p * q) i"] have "divides_ff ?f (coeff (p * q) i)" using range_coeff[of "p * q"] 
          by (cases "coeff (p * q) i = 0", auto simp: divides_ff_def)
      }
      from this[of "r + s", unfolded cpq] have "divides_ff ?f (to_fract (f * (a + b) + pi r * qi s))" 
        unfolding pi qi by simp
      from this[unfolded divides_ff_to_fract] have "f dvd pi r * qi s"
        by (metis dvd_add_times_triv_left_iff mult.commute)
      from prime[OF this] have "f dvd pi r ∨ f dvd qi s" by auto
      with r s show False unfolding pi qi by auto
    qed
  } note main = this
  define n where "n ≡ normalize_content_ff :: 'a fract poly ⇒ 'a fract poly"
  let ?s = "λ p. smult (content_ff p) (n p)"
  have "?c (p * q) = ?c (?s p * ?s q)" unfolding smult_normalize_content_ff n_def by simp
  also have "?s p * ?s q = smult (?c p * ?c q) (n p * n q)" by (simp add: mult.commute)
  also have "?c (…) =dff (?c p * ?c q) * ?c (n p * n q)" by (rule content_ff_smult)
  also have "?c (n p * n q) =dff 1" unfolding n_def
    by (rule main, insert p q, auto simp: content_ff_normalize_content_ff_1)
  finally show ?thesis by simp
qed auto

abbreviation (input) "content_ff_ff p ≡ content_ff (map_poly to_fract p)"

lemma factorization_to_fract:
  assumes q: "q ≠ 0" and factor: "map_poly to_fract (p :: 'a :: ufd poly) = q * r"
  shows "∃ q' r' c. c ≠ 0 ∧ q = smult c (map_poly to_fract q') ∧
    r = smult (inverse c) (map_poly to_fract r') ∧
    content_ff_ff q' =dff 1 ∧ p = q' * r'"
proof -
  let ?c = content_ff
  let ?p = "map_poly to_fract p"
  interpret map_poly_inj_comm_ring_hom "to_fract :: 'a ⇒ _"..
  define cq where "cq ≡ normalize_content_ff q"
  define cr where "cr ≡ smult (content_ff q) r"
  define q' where "q' ≡ map_poly inv_embed cq"
  define r' where "r' ≡ map_poly inv_embed cr"
  from content_ff_map_poly_to_fract have cp_ff: "?c ?p ∈ range to_fract" by auto
  from smult_normalize_content_ff[of q] have cqs: "q = smult (content_ff q) cq" unfolding cq_def ..
  from content_ff_normalize_content_ff_1[OF q] have c_cq: "content_ff cq =dff 1" unfolding cq_def .
  from content_ff_1_coeffs_to_fract[OF this] have cq_ff: "set (coeffs cq) ⊆ range to_fract" .
  have factor: "?p = cq * cr" unfolding factor cr_def using cqs
    by (metis mult_smult_left mult_smult_right)
  from gauss_lemma[of cq cr] have cp: "?c ?p =dff ?c cq * ?c cr" unfolding factor .
  with c_cq have "?c ?p =dff ?c cr"
    by (metis eq_dff_mult_right_trans mult.commute mult.right_neutral)
  with cp_ff have "?c cr ∈ range to_fract"
    by (metis divides_ff_def to_fract_hom.hom_mult eq_dff_def image_iff range_eqI)
  from content_ff_to_fract_coeffs_to_fract[OF this] have cr_ff: "set (coeffs cr) ⊆ range to_fract" by auto
  have cq: "cq = map_poly to_fract q'" unfolding q'_def
    by (rule range_to_fract_embed_poly[OF cq_ff])
  have cr: "cr = map_poly to_fract r'" unfolding r'_def
    by (rule range_to_fract_embed_poly[OF cr_ff])
  from factor[unfolded cq cr]
  have p: "p = q' * r'" by (simp add: injectivity)
  from c_cq have ctnt: "content_ff_ff q' =dff 1" using cq q'_def by force
  from cqs have idq: "q = smult (?c q) (map_poly to_fract q')" unfolding cq .
  with q have cq: "?c q ≠ 0" by auto
  have "r = smult (inverse (?c q)) cr" unfolding cr_def using cq by auto
  also have "cr = map_poly to_fract r'" by (rule cr)
  finally have idr: "r = smult (inverse (?c q)) (map_poly to_fract r')" by auto
  from cq p ctnt idq idr show ?thesis by blast
qed

lemma irreducible_PM_M_PFM:
  assumes irr: "irreducible p"
  shows "degree p = 0 ∧ irreducible (coeff p 0) ∨ 
  degree p ≠ 0 ∧ irreducible (map_poly to_fract p) ∧ content_ff_ff p =dff 1"
proof-
  interpret map_poly_inj_idom_hom to_fract..
  from irr[unfolded irreducible_altdef]
  have p0: "p ≠ 0" and irr: "¬ p dvd 1" "⋀ b. b dvd p ⟹ ¬ p dvd b ⟹ b dvd 1" by auto
  show ?thesis
  proof (cases "degree p = 0")
    case True
    from degree0_coeffs[OF True] obtain a where p: "p = [:a:]" by auto
    note irr = irr[unfolded p]
    from p p0 have a0: "a ≠ 0" by auto
    moreover have "¬ a dvd 1" using irr(1) by simp
    moreover {
      fix b
      assume "b dvd a" "¬ a dvd b"
      hence "[:b:] dvd [:a:]" "¬ [:a:] dvd [:b:]" unfolding const_poly_dvd .
      from irr(2)[OF this] have "b dvd 1" unfolding const_poly_dvd_1 .
    }
    ultimately have "irreducible a" unfolding irreducible_altdef by auto
    with True show ?thesis unfolding p by auto
  next
    case False
    let ?E = "map_poly to_fract"
    let ?p = "?E p"
    have dp: "degree ?p ≠ 0" using False by simp
    from p0 have p': "?p ≠ 0" by simp
    moreover have "¬ ?p dvd 1" 
      proof
        assume "?p dvd 1" then obtain q where id: "?p * q = 1" unfolding dvd_def by auto
        have deg: "degree (?p * q) = degree ?p + degree q"
          by (rule degree_mult_eq, insert id, auto)
        from arg_cong[OF id, of degree, unfolded deg] dp show False by auto
      qed
    moreover {
      fix q
      assume "q dvd ?p" and ndvd: "¬ ?p dvd q"
      then obtain r where fact: "?p = q * r" unfolding dvd_def by auto
      with p' have q0: "q ≠ 0" by auto
      from factorization_to_fract[OF this fact] obtain q' r' c where *: "c ≠ 0" "q = smult c (?E q')"
        "r = smult (inverse c) (?E r')" "content_ff_ff q' =dff 1"
        "p = q' * r'" by auto
      hence "q' dvd p" unfolding dvd_def by auto
      note irr = irr(2)[OF this]
      have "¬ p dvd q'"
      proof
        assume "p dvd q'"
        then obtain u where q': "q' = p * u" unfolding dvd_def by auto
        from arg_cong[OF this, of "λ x. smult c (?E x)", unfolded *(2)[symmetric]]
        have "q = ?p * smult c (?E u)" by simp
        hence "?p dvd q" unfolding dvd_def by blast
        with ndvd show False ..
      qed
      from irr[OF this] have "q' dvd 1" .
      from divides_degree[OF this] have "degree q' = 0" by auto
      from degree0_coeffs[OF this] obtain a' where "q' = [:a':]" by auto
      from *(2)[unfolded this] obtain a where q: "q = [:a:]"
        by (simp add: to_fract_hom.map_poly_pCons_hom)
      with q0 have a: "a ≠ 0" by auto
      have "q dvd 1" unfolding q const_poly_dvd_1 using a unfolding dvd_def
        by (intro exI[of _ "inverse a"], auto)
    }
    ultimately have irr_p': "irreducible ?p" unfolding irreducible_altdef by auto
    let ?c = "content_ff"
    have "?c ?p ∈ range to_fract"
      by (rule content_ff_to_fract, unfold to_fract_hom.coeffs_map_poly_hom, auto)
    then obtain c where cp: "?c ?p = to_fract c" by auto
    from p' cp have c: "c ≠ 0" by auto
    have "?c ?p =dff 1" unfolding cp
    proof (rule ccontr)
      define cp where "cp = normalize_content_ff ?p"
      from smult_normalize_content_ff[of ?p] have cps: "?p = smult (to_fract c) cp" unfolding cp_def cp ..
      from content_ff_normalize_content_ff_1[OF p'] have c_cp: "content_ff cp =dff 1" unfolding cp_def .
      from range_to_fract_embed_poly[OF content_ff_1_coeffs_to_fract[OF c_cp]] obtain cp' where "cp = ?E cp'" by auto
      from cps[unfolded this] have "p = smult c cp'" by (simp add: injectivity)
      hence dvd: "[: c :] dvd p" unfolding dvd_def by auto
      have "¬ p dvd [: c :]" using divides_degree[of p "[: c :]"] c False by auto
      from irr(2)[OF dvd this] have "c dvd 1" by simp
      assume "¬ to_fract c =dff 1"
      from this[unfolded eq_dff_def One_fract_def to_fract_def[symmetric] divides_ff_def to_fract_mult]
      have c1: "⋀ r. 1 ≠ c * r" by (auto simp: ac_simps simp del: to_fract_hom.hom_mult simp: to_fract_hom.hom_mult[symmetric])
      with ‹c dvd 1› show False unfolding dvd_def by blast
    qed
    with False irr_p' show ?thesis by auto
  qed
qed

lemma irreducible_M_PM:
  fixes p :: "'a :: ufd poly" assumes 0: "degree p = 0" and irr: "irreducible (coeff p 0)"
  shows "irreducible p"
proof (cases "p = 0")
  case True
  thus ?thesis using assms by auto
next
  case False
  from degree0_coeffs[OF 0] obtain a where p: "p = [:a:]" by auto
  with False have a0: "a ≠ 0" by auto
  from p irr have "irreducible a" by auto
  from this[unfolded irreducible_altdef]
  have a1: "¬ a dvd 1" and irr: "⋀ b. b dvd a ⟹ ¬ a dvd b ⟹ b dvd 1" by auto
  { 
    fix b
    assume *: "b dvd [:a:]" "¬ [:a:] dvd b"
    from divides_degree[OF this(1)] a0 have "degree b = 0" by auto
    from degree0_coeffs[OF this] obtain bb where b: "b = [: bb :]" by auto
    from * irr[of bb] have "b dvd 1" unfolding b const_poly_dvd by auto
  }
  with a0 a1 show ?thesis by (auto simp: irreducible_altdef p)
qed

lemma primitive_irreducible_imp_degree:
 "primitive (p::'a::{semiring_gcd,idom} poly) ⟹ irreducible p ⟹ degree p > 0"
  by (unfold irreducible_primitive_connect[symmetric], auto)

lemma irreducible_degree_field:
  fixes p :: "'a :: field poly" assumes "irreducible p"
  shows "degree p > 0"
proof-
  {
    assume "degree p = 0"
    from degree0_coeffs[OF this] assms obtain a where p: "p = [:a:]" and a: "a ≠ 0" by auto
    hence "1 = p * [:inverse a:]" by auto
    hence "p dvd 1" ..
    hence "p ∈ Units mk_monoid" by simp
    with assms have False unfolding irreducible_def by auto
  } then show ?thesis by auto
qed

lemma irreducible_PFM_PM: assumes
  irr: "irreducible (map_poly to_fract p)" and ct: "content_ff_ff p =dff 1"
  shows "irreducible p"
proof -
  let ?E = "map_poly to_fract"
  let ?p = "?E p"
  from ct have p0: "p ≠ 0" by (auto simp: eq_dff_def divides_ff_def)
  moreover
    from irreducible_degree_field[OF irr] have deg: "degree p ≠ 0" by simp
    from irr[unfolded irreducible_altdef]
    have irr: "⋀ b. b dvd ?p ⟹ ¬ ?p dvd b ⟹ b dvd 1" by auto
    have "¬ p dvd 1" using deg divides_degree[of p 1] by auto
  moreover {
    fix q :: "'a poly"
    assume dvd: "q dvd p" and ndvd: "¬ p dvd q"
    from dvd obtain r where pqr: "p = q * r" ..
    from arg_cong[OF this, of ?E] have pqr': "?p = ?E q * ?E r" by simp
    from p0 pqr have q: "q ≠ 0" and r: "r ≠ 0" by auto
    have dp: "degree p = degree q + degree r" unfolding pqr
      by (subst degree_mult_eq, insert q r, auto)
    from eq_dff_trans[OF eq_dff_sym[OF gauss_lemma[of "?E q" "?E r", folded pqr']] ct]
    have ct: "content_ff (?E q) * content_ff (?E r) =dff 1" .
    from content_ff_map_poly_to_fract obtain cq where cq: "content_ff (?E q) = to_fract cq" by auto
    from content_ff_map_poly_to_fract obtain cr where cr: "content_ff (?E r) = to_fract cr" by auto
    note ct[unfolded cq cr to_fract_mult eq_dff_def divides_ff_def]
    from this[folded hom_distribs]
    obtain c where c: "cq * cr * c = 1" by (auto simp del: to_fract_hom.hom_mult simp: to_fract_hom.hom_mult[symmetric])
    hence one: "1 = cq * (c * cr)" "1 = cr * (c * cq)" by (auto simp: ac_simps)
    {
      assume *: "degree q ≠ 0 ∧ degree r ≠ 0"
      with dp have "degree q < degree p" by auto
      hence "degree (?E q) < degree (?E p)" by simp
      hence ndvd: "¬ ?p dvd ?E q" using divides_degree[of ?p "?E q"] q by auto
      have "?E q dvd ?p" unfolding pqr' by auto
      from irr[OF this ndvd] have "?E q dvd 1" .
      from divides_degree[OF this] * have False by auto
    }
    hence "degree q = 0 ∨ degree r = 0" by blast
    then have "q dvd 1" 
    proof
      assume "degree q = 0"
      from degree0_coeffs[OF this] q obtain a where q: "q = [:a:]" and a: "a ≠ 0" by auto
      hence id: "set (coeffs (?E q)) = {to_fract a}" by auto
      have "divides_ff (to_fract a) (content_ff (?E q))" unfolding content_ff_iff id by auto
      from this[unfolded cq divides_ff_def, folded hom_distribs]
      obtain rr where cq: "cq = a * rr" by (auto simp del: to_fract_hom.hom_mult simp: to_fract_hom.hom_mult[symmetric])
      with one(1) have "1 = a * (rr * c * cr)" by (auto simp: ac_simps)
      hence "a dvd 1" ..
      thus ?thesis by (simp add: q)
    next
      assume "degree r = 0"
      from degree0_coeffs[OF this] r obtain a where r: "r = [:a:]" and a: "a ≠ 0" by auto
      hence id: "set (coeffs (?E r)) = {to_fract a}" by auto
      have "divides_ff (to_fract a) (content_ff (?E r))" unfolding content_ff_iff id by auto
      note this[unfolded cr divides_ff_def to_fract_mult]
      note this[folded hom_distribs]
      then obtain rr where cr: "cr = a * rr" by (auto simp del: to_fract_hom.hom_mult simp: to_fract_hom.hom_mult[symmetric])
      with one(2) have one: "1 = a * (rr * c * cq)" by (auto simp: ac_simps)
      from arg_cong[OF pqr[unfolded r], of "λ p. p * [:rr * c * cq:]"]
      have "p * [:rr * c * cq:] = q * [:a * (rr * c * cq):]" by (simp add: ac_simps)
      also have "… = q" unfolding one[symmetric] by auto
      finally obtain r where "q = p * r" by blast
      hence "p dvd q" ..
      with ndvd show ?thesis by auto
    qed
  }
  ultimately show ?thesis by (auto simp:irreducible_altdef)
qed

lemma irreducible_cases: "irreducible p ⟷
  degree p = 0 ∧ irreducible (coeff p 0) ∨ 
  degree p ≠ 0 ∧ irreducible (map_poly to_fract p) ∧ content_ff_ff p =dff 1"
  using irreducible_PM_M_PFM irreducible_M_PM irreducible_PFM_PM
  by blast

lemma dvd_PM_iff: "p dvd q ⟷ divides_ff (content_ff_ff p) (content_ff_ff q) ∧ 
  map_poly to_fract p dvd map_poly to_fract q"
proof -
  interpret map_poly_inj_idom_hom to_fract..
  let ?E = "map_poly to_fract"
  show ?thesis (is "?l = ?r")
  proof
    assume "p dvd q"
    then obtain r where qpr: "q = p * r" ..
    from arg_cong[OF this, of ?E]
    have dvd: "?E p dvd ?E q" by auto
    from content_ff_map_poly_to_fract obtain cq where cq: "content_ff_ff q = to_fract cq" by auto
    from content_ff_map_poly_to_fract obtain cp where cp: "content_ff_ff p = to_fract cp" by auto
    from content_ff_map_poly_to_fract obtain cr where cr: "content_ff_ff r = to_fract cr" by auto
    from gauss_lemma[of "?E p" "?E r", folded hom_distribs qpr, unfolded cq cp cr]
    have "divides_ff (content_ff_ff p) (content_ff_ff q)" unfolding cq cp eq_dff_def
      by (metis divides_ff_def divides_ff_trans)
    with dvd show ?r by blast
  next
    assume ?r
    show ?l 
    proof (cases "q = 0")
      case True
      with ‹?r› show ?l by auto
    next
      case False note q = this
      hence q': "?E q ≠ 0" by auto
      from ‹?r› obtain rr where qpr: "?E q = ?E p * rr" unfolding dvd_def by auto
      with q have p: "p ≠ 0" and Ep: "?E p ≠ 0" and rr: "rr ≠ 0" by auto
      from gauss_lemma[of "?E p" rr, folded qpr] 
      have ct: "content_ff_ff q =dff content_ff_ff p * content_ff rr"
        by auto
      from content_ff_map_poly_to_fract[of p] obtain cp where cp: "content_ff_ff p = to_fract cp" by auto
      from content_ff_map_poly_to_fract[of q] obtain cq where cq: "content_ff_ff q = to_fract cq" by auto
      from ‹?r›[unfolded cp cq] have "divides_ff (to_fract cp) (to_fract cq)" ..
      with ct[unfolded cp cq eq_dff_def] have "content_ff rr ∈ range to_fract"
        by (metis (no_types, lifting) Ep content_ff_0_iff cp divides_ff_def 
          divides_ff_trans mult.commute mult_right_cancel range_eqI)
      from range_to_fract_embed_poly[OF content_ff_to_fract_coeffs_to_fract[OF this]] obtain r
        where rr: "rr = ?E r" by auto
      from qpr[unfolded rr, folded hom_distribs]
      have "q = p * r" by (rule injectivity)
      thus "p dvd q" ..
    qed
  qed
qed

lemma factorial_monoid_poly: "factorial_monoid (mk_monoid :: 'a :: ufd poly monoid)"
proof (fold factorial_condition_one, intro conjI)
  interpret M: factorial_monoid "mk_monoid :: 'a monoid" by (fact factorial_monoid)
  interpret PFM: factorial_monoid "mk_monoid :: 'a fract poly monoid" 
    by (rule as_ufd.factorial_monoid)
  interpret PM: comm_monoid_cancel "mk_monoid :: 'a poly monoid" by (unfold_locales, auto)
  let ?E = "map_poly to_fract"
  show "divisor_chain_condition_monoid (mk_monoid::'a poly monoid)"
  proof (unfold_locales, unfold mk_monoid_simps)
    let ?rel' = "{(x::'a poly, y). x ≠ 0 ∧ y ≠ 0 ∧ properfactor x y}"
    let ?rel'' = "{(x::'a, y). x ≠ 0 ∧ y ≠ 0 ∧ properfactor x y}"
    let ?relPM = "{(x, y). x ≠ 0 ∧ y ≠ 0 ∧ x dvd y ∧ ¬ y dvd (x :: 'a poly)}"
    let ?relM = "{(x, y). x ≠ 0 ∧ y ≠ 0 ∧ x dvd y ∧ ¬ y dvd (x :: 'a)}"
    have id: "?rel' = ?relPM" using properfactor_nz by auto
    have id': "?rel'' = ?relM" using properfactor_nz by auto
    have "wf ?rel''" using M.division_wellfounded by auto
    hence wfM: "wf ?relM" using id' by auto
    let ?c = "λ p. inv_embed (content_ff_ff p)"
    let ?f = "λ p. (degree p, ?c p)"
    note wf = wf_inv_image[OF wf_lex_prod[OF wf_less wfM], of ?f]
    show "wf ?rel'" unfolding id
    proof (rule wf_subset[OF wf], clarify)
      fix p q :: "'a poly"
      assume p: "p ≠ 0" and q: "q ≠ 0" and dvd: "p dvd q" and ndvd: "¬ q dvd p"
      from dvd obtain r where qpr: "q = p * r" ..
      from degree_mult_eq[of p r, folded qpr] q qpr have r: "r ≠ 0" 
        and deg: "degree q = degree p + degree r" by auto
      show "(p,q) ∈ inv_image ({(x, y). x < y} <*lex*> ?relM) ?f"
      proof (cases "degree p = degree q")
        case False
        with deg have "degree p < degree q" by auto
        thus ?thesis by auto
      next
        case True
        with deg have "degree r = 0" by simp
        from degree0_coeffs[OF this] r obtain a where ra: "r = [:a:]" and a: "a ≠ 0" by auto
        from arg_cong[OF qpr, of "λ p. ?E p * [:inverse (to_fract a):]"] a
        have "?E p = ?E q * [:inverse (to_fract a):]"
          by (auto simp: ac_simps ra)
        hence "?E q dvd ?E p" ..
        with ndvd dvd_PM_iff have ndvd: "¬ divides_ff (content_ff_ff q) (content_ff_ff p)" by auto
        from content_ff_map_poly_to_fract obtain cq where cq: "content_ff_ff q = to_fract cq" by auto
        from content_ff_map_poly_to_fract obtain cp where cp: "content_ff_ff p = to_fract cp" by auto
        from ndvd[unfolded cp cq] have ndvd: "¬ cq dvd cp" by simp
        from iffD1[OF dvd_PM_iff,OF dvd,unfolded cq cp]
        have dvd: "cp dvd cq" by simp
        have c_p: "?c p = cp" unfolding cp by simp
        have c_q: "?c q = cq" unfolding cq by simp
        from q cq have cq0: "cq ≠ 0" by auto
        from p cp have cp0: "cp ≠ 0" by auto
        from ndvd cq0 cp0 dvd have "(?c p, ?c q) ∈ ?relM" unfolding c_p c_q by auto
        with True show ?thesis by auto
      qed
    qed
  qed
  show "primeness_condition_monoid (mk_monoid::'a poly monoid)"
  proof (unfold_locales, unfold mk_monoid_simps)
    fix p :: "'a poly"
    assume p: "p ≠ 0" and "irred p"
    then have irr: "irreducible p" by auto
    from p have p': "?E p ≠ 0" by auto
    from irreducible_PM_M_PFM[OF irr] have choice: "degree p = 0 ∧ irred (coeff p 0)
      ∨ degree p ≠ 0 ∧ irred (?E p) ∧ content_ff_ff p =dff 1" by auto
    show "Divisibility.prime mk_monoid p"
    proof (rule Divisibility.primeI, unfold mk_monoid_simps mem_Units)
      show "¬ p dvd 1"
      proof
        assume "p dvd 1"
        from divides_degree[OF this] have dp: "degree p = 0" by auto
        from degree0_coeffs[OF this] p obtain a where p: "p = [:a:]" and a: "a ≠ 0" by auto
        with choice have irr: "irreducible a" by auto
        from ‹p dvd 1›[unfolded p] have "a dvd 1" by auto
        with irr show False unfolding irreducible_def by auto
      qed
      fix q r :: "'a poly"
      assume q: "q ≠ 0" and r: "r ≠ 0" and "factor p (q * r)"
      from this[unfolded factor_idom] have "p dvd q * r" by auto
      from iffD1[OF dvd_PM_iff this] have dvd_ct: "divides_ff (content_ff_ff p) (content_ff (?E (q * r)))"
        and dvd_E: "?E p dvd ?E q * ?E r" by auto
      from gauss_lemma[of "?E q" "?E r"] divides_ff_trans[OF dvd_ct, of "content_ff_ff q * content_ff_ff r"]
      have dvd_ct: "divides_ff (content_ff_ff p) (content_ff_ff q * content_ff_ff r)"
        unfolding eq_dff_def by auto
      from choice
      have "p dvd q ∨ p dvd r"
      proof
        assume "degree p ≠ 0 ∧ irred (?E p) ∧ content_ff_ff p =dff 1"
        hence deg: "degree p ≠ 0" and irr: "irred (?E p)" and ct: "content_ff_ff p =dff 1" by auto
        from PFM.irreducible_prime[OF irr] p have prime: "Divisibility.prime mk_monoid (?E p)" by auto
        from q r have Eq: "?E q ∈ carrier mk_monoid" and Er: "?E r ∈ carrier mk_monoid" 
          and q': "?E q ≠ 0" and r': "?E r ≠ 0" and qr': "?E q * ?E r ≠ 0" by auto
        from PFM.prime_divides[OF Eq Er prime] q' r' qr' dvd_E
        have dvd_E: "?E p dvd ?E q ∨ ?E p dvd ?E r" by simp
        from ct have ct: "divides_ff (content_ff_ff p) 1" unfolding eq_dff_def by auto
        moreover have "⋀ q. divides_ff 1 (content_ff_ff q)" using content_ff_map_poly_to_fract
          unfolding divides_ff_def by auto
        from divides_ff_trans[OF ct this] have ct: "⋀ q. divides_ff (content_ff_ff p) (content_ff_ff q)" .
        with dvd_E show ?thesis using dvd_PM_iff by blast
      next
        assume "degree p = 0 ∧ irred (coeff p 0)"
        hence deg: "degree p = 0" and irr: "irred (coeff p 0)" by auto
        from degree0_coeffs[OF deg] p obtain a where p: "p = [:a:]" and a: "a ≠ 0" by auto
        with irr have irr: "irred a" and aM: "a ∈ carrier mk_monoid" by auto
        from M.irreducible_prime[OF irr aM] have prime: "Divisibility.prime mk_monoid a" .
        from content_ff_map_poly_to_fract obtain cq where cq: "content_ff_ff q = to_fract cq" by auto
        from content_ff_map_poly_to_fract obtain cp where cp: "content_ff_ff p = to_fract cp" by auto
        from content_ff_map_poly_to_fract obtain cr where cr: "content_ff_ff r = to_fract cr" by auto
        have "divides_ff (to_fract a) (content_ff_ff p)" unfolding p content_ff_iff using a by auto
        from divides_ff_trans[OF this[unfolded cp] dvd_ct[unfolded cp cq cr]]
        have "divides_ff (to_fract a) (to_fract (cq * cr))" by simp
        hence dvd: "a dvd cq * cr" by (auto simp add: divides_ff_def simp del: to_fract_hom.hom_mult simp: to_fract_hom.hom_mult[symmetric])
        from content_ff_divides_ff[of "to_fract a" "?E p"] have "divides_ff (to_fract cp) (to_fract a)"
          using cp a p by auto
        hence cpa: "cp dvd a" by simp
        from a q r cq cr have aM: "a ∈ carrier mk_monoid" and qM: "cq ∈ carrier mk_monoid" and rM: "cr ∈ carrier mk_monoid"
          and q': "cq ≠ 0" and r': "cr ≠ 0" and qr': "cq * cr ≠ 0" 
          by auto
        from M.prime_divides[OF qM rM prime] q' r' qr' dvd
        have "a dvd cq ∨ a dvd cr" by simp
        with dvd_trans[OF cpa] have dvd: "cp dvd cq ∨ cp dvd cr" by auto
        have "⋀ q. ?E p * (smult (inverse (to_fract a)) q) = q" unfolding p using a by (auto simp: one_poly_def)
        hence Edvd: "⋀ q. ?E p dvd q" unfolding dvd_def by metis
        from dvd Edvd show ?thesis apply (subst(1 2) dvd_PM_iff) unfolding cp cq cr by auto
      qed
      thus "factor p q ∨ factor p r" unfolding factor_idom using p q r by auto
    qed
  qed
qed

instance poly :: (ufd) ufd
  by (intro ufd.intro_of_class factorial_monoid_imp_ufd factorial_monoid_poly)


lemma primitive_iff_some_content_dvd_1:
  fixes f :: "'a :: ufd poly" (* gcd_condition suffices... *)
  shows "primitive f ⟷ some_gcd.listgcd (coeffs f) dvd 1" (is "_ ⟷ ?c dvd 1")
proof(intro iffI primitiveI)
  fix x
  assume "(⋀y. y ∈ set (coeffs f) ⟹ x dvd y)"
  from some_gcd.listgcd_greatest[of "coeffs f", OF this]
  have "x dvd ?c" by simp
  also assume "?c dvd 1"
  finally show "x dvd 1".
next
  assume "primitive f"
  from primitiveD[OF this some_gcd.listgcd[of _ "coeffs f"]]
  show "?c dvd 1" by auto
qed

end