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 |