src/HOL/Computational_Algebra/Polynomial_Factorial.thy
changeset 65486 d801126a14cb
parent 65435 378175f44328
child 65963 ca1e636fa716
equal deleted inserted replaced
65485:8c7bc3a13513 65486:d801126a14cb
    15 begin
    15 begin
    16 
    16 
    17 subsection \<open>Various facts about polynomials\<close>
    17 subsection \<open>Various facts about polynomials\<close>
    18 
    18 
    19 lemma prod_mset_const_poly: " (\<Prod>x\<in>#A. [:f x:]) = [:prod_mset (image_mset f A):]"
    19 lemma prod_mset_const_poly: " (\<Prod>x\<in>#A. [:f x:]) = [:prod_mset (image_mset f A):]"
    20   by (induct A) (simp_all add: one_poly_def ac_simps)
    20   by (induct A) (simp_all add: ac_simps)
    21 
    21 
    22 lemma irreducible_const_poly_iff:
    22 lemma irreducible_const_poly_iff:
    23   fixes c :: "'a :: {comm_semiring_1,semiring_no_zero_divisors}"
    23   fixes c :: "'a :: {comm_semiring_1,semiring_no_zero_divisors}"
    24   shows "irreducible [:c:] \<longleftrightarrow> irreducible c"
    24   shows "irreducible [:c:] \<longleftrightarrow> irreducible c"
    25 proof
    25 proof
    33     finally have "degree a = 0" "degree b = 0" by auto
    33     finally have "degree a = 0" "degree b = 0" by auto
    34     then obtain a' b' where ab': "a = [:a':]" "b = [:b':]" by (auto elim!: degree_eq_zeroE)
    34     then obtain a' b' where ab': "a = [:a':]" "b = [:b':]" by (auto elim!: degree_eq_zeroE)
    35     from ab have "coeff [:c:] 0 = coeff (a * b) 0" by (simp only: )
    35     from ab have "coeff [:c:] 0 = coeff (a * b) 0" by (simp only: )
    36     hence "c = a' * b'" by (simp add: ab' mult_ac)
    36     hence "c = a' * b'" by (simp add: ab' mult_ac)
    37     from A and this have "a' dvd 1 \<or> b' dvd 1" by (rule irreducibleD)
    37     from A and this have "a' dvd 1 \<or> b' dvd 1" by (rule irreducibleD)
    38     with ab' show "a dvd 1 \<or> b dvd 1" by (auto simp: one_poly_def)
    38     with ab' show "a dvd 1 \<or> b dvd 1"
       
    39       by (auto simp add: is_unit_const_poly_iff)
    39   qed (insert A, auto simp: irreducible_def is_unit_poly_iff)
    40   qed (insert A, auto simp: irreducible_def is_unit_poly_iff)
    40 next
    41 next
    41   assume A: "irreducible [:c:]"
    42   assume A: "irreducible [:c:]"
    42   show "irreducible c"
    43   then have "c \<noteq> 0" and "\<not> c dvd 1"
       
    44     by (auto simp add: irreducible_def is_unit_const_poly_iff)
       
    45   then show "irreducible c"
    43   proof (rule irreducibleI)
    46   proof (rule irreducibleI)
    44     fix a b assume ab: "c = a * b"
    47     fix a b assume ab: "c = a * b"
    45     hence "[:c:] = [:a:] * [:b:]" by (simp add: mult_ac)
    48     hence "[:c:] = [:a:] * [:b:]" by (simp add: mult_ac)
    46     from A and this have "[:a:] dvd 1 \<or> [:b:] dvd 1" by (rule irreducibleD)
    49     from A and this have "[:a:] dvd 1 \<or> [:b:] dvd 1" by (rule irreducibleD)
    47     thus "a dvd 1 \<or> b dvd 1" by (simp add: one_poly_def)
    50     then show "a dvd 1 \<or> b dvd 1"
    48   qed (insert A, auto simp: irreducible_def one_poly_def)
    51       by (auto simp add: is_unit_const_poly_iff)
       
    52   qed
    49 qed
    53 qed
    50 
    54 
    51 
    55 
    52 subsection \<open>Lifting elements into the field of fractions\<close>
    56 subsection \<open>Lifting elements into the field of fractions\<close>
    53 
    57 
   139 
   143 
   140 lemma fract_poly_0 [simp]: "fract_poly 0 = 0"
   144 lemma fract_poly_0 [simp]: "fract_poly 0 = 0"
   141   by (simp add: poly_eqI coeff_map_poly)
   145   by (simp add: poly_eqI coeff_map_poly)
   142 
   146 
   143 lemma fract_poly_1 [simp]: "fract_poly 1 = 1"
   147 lemma fract_poly_1 [simp]: "fract_poly 1 = 1"
   144   by (simp add: one_poly_def map_poly_pCons)
   148   by (simp add: map_poly_pCons)
   145 
   149 
   146 lemma fract_poly_add [simp]:
   150 lemma fract_poly_add [simp]:
   147   "fract_poly (p + q) = fract_poly p + fract_poly q"
   151   "fract_poly (p + q) = fract_poly p + fract_poly q"
   148   by (intro poly_eqI) (simp_all add: coeff_map_poly)
   152   by (intro poly_eqI) (simp_all add: coeff_map_poly)
   149 
   153 
   361       with assms coeff_m show "c dvd coeff a i"
   365       with assms coeff_m show "c dvd coeff a i"
   362         by (simp add: prime_elem_dvd_mult_iff)
   366         by (simp add: prime_elem_dvd_mult_iff)
   363     qed
   367     qed
   364     hence "[:c:] dvd a" by (subst const_poly_dvd_iff) blast
   368     hence "[:c:] dvd a" by (subst const_poly_dvd_iff) blast
   365   }
   369   }
   366   thus "[:c:] dvd a \<or> [:c:] dvd b" by blast
   370   then show "[:c:] dvd a \<or> [:c:] dvd b" by blast
   367 qed (insert assms, simp_all add: prime_elem_def one_poly_def)
   371 next
       
   372   from assms show "[:c:] \<noteq> 0" and "\<not> [:c:] dvd 1"
       
   373     by (simp_all add: prime_elem_def is_unit_const_poly_iff)
       
   374 qed
   368 
   375 
   369 lemma prime_elem_const_poly_iff:
   376 lemma prime_elem_const_poly_iff:
   370   fixes c :: "'a :: semidom"
   377   fixes c :: "'a :: semidom"
   371   shows   "prime_elem [:c:] \<longleftrightarrow> prime_elem c"
   378   shows   "prime_elem [:c:] \<longleftrightarrow> prime_elem c"
   372 proof
   379 proof