3858 by blast |
3858 by blast |
3859 with \<open>y \<noteq> 0\<close> show ?thesis |
3859 with \<open>y \<noteq> 0\<close> show ?thesis |
3860 by (auto simp add: mod_poly_def intro: *) |
3860 by (auto simp add: mod_poly_def intro: *) |
3861 qed |
3861 qed |
3862 |
3862 |
3863 inductive eucl_rel_poly :: "'a::field poly \<Rightarrow> 'a poly \<Rightarrow> 'a poly \<times> 'a poly \<Rightarrow> bool" |
|
3864 where |
|
3865 eucl_rel_poly_by0: "eucl_rel_poly x 0 (0, x)" |
|
3866 | eucl_rel_poly_dividesI: "y \<noteq> 0 \<Longrightarrow> x = q * y \<Longrightarrow> eucl_rel_poly x y (q, 0)" |
|
3867 | eucl_rel_poly_remainderI: |
|
3868 "y \<noteq> 0 \<Longrightarrow> degree r < degree y \<Longrightarrow> x = q * y + r \<Longrightarrow> eucl_rel_poly x y (q, r)" |
|
3869 |
|
3870 lemma eucl_rel_poly_iff: |
|
3871 "eucl_rel_poly x y (q, r) \<longleftrightarrow> |
|
3872 x = q * y + r \<and> (if y = 0 then q = 0 else r = 0 \<or> degree r < degree y)" |
|
3873 by (auto elim: eucl_rel_poly.cases |
|
3874 intro: eucl_rel_poly_by0 eucl_rel_poly_dividesI eucl_rel_poly_remainderI) |
|
3875 |
|
3876 lemma eucl_rel_poly: |
|
3877 "eucl_rel_poly x y (x div y, x mod y)" |
|
3878 using degree_mod_less_degree [of y x] |
|
3879 by (auto simp add: eucl_rel_poly_iff mod_eq_0_iff_dvd) |
|
3880 |
|
3881 lemma |
|
3882 assumes 1: "eucl_rel_poly x y (q1, r1)" |
|
3883 assumes 2: "eucl_rel_poly x y (q2, r2)" |
|
3884 shows eucl_rel_poly_unique_div: "q1 = q2" (is ?Q) |
|
3885 and eucl_rel_poly_unique_mod: "r1 = r2" (is ?R) |
|
3886 proof - |
|
3887 have \<open>?Q \<and> ?R\<close> |
|
3888 proof (cases "y = 0") |
|
3889 assume "y = 0" |
|
3890 with assms show ?thesis |
|
3891 by (simp add: eucl_rel_poly_iff) |
|
3892 next |
|
3893 assume [simp]: "y \<noteq> 0" |
|
3894 from 1 have q1: "x = q1 * y + r1" and r1: "r1 = 0 \<or> degree r1 < degree y" |
|
3895 unfolding eucl_rel_poly_iff by simp_all |
|
3896 from 2 have q2: "x = q2 * y + r2" and r2: "r2 = 0 \<or> degree r2 < degree y" |
|
3897 unfolding eucl_rel_poly_iff by simp_all |
|
3898 from q1 q2 have q3: "(q1 - q2) * y = r2 - r1" |
|
3899 by (simp add: algebra_simps) |
|
3900 from r1 r2 have r3: "(r2 - r1) = 0 \<or> degree (r2 - r1) < degree y" |
|
3901 by (auto intro: degree_diff_less) |
|
3902 show "q1 = q2 \<and> r1 = r2" |
|
3903 proof (rule classical) |
|
3904 assume "\<not> ?thesis" |
|
3905 with q3 have "q1 \<noteq> q2" and "r1 \<noteq> r2" by auto |
|
3906 with r3 have "degree (r2 - r1) < degree y" by simp |
|
3907 also have "degree y \<le> degree (q1 - q2) + degree y" by simp |
|
3908 also from \<open>q1 \<noteq> q2\<close> have "\<dots> = degree ((q1 - q2) * y)" |
|
3909 by (simp add: degree_mult_eq) |
|
3910 also from q3 have "\<dots> = degree (r2 - r1)" |
|
3911 by simp |
|
3912 finally have "degree (r2 - r1) < degree (r2 - r1)" . |
|
3913 then show ?thesis by simp |
|
3914 qed |
|
3915 qed |
|
3916 then show ?Q and ?R |
|
3917 by simp_all |
|
3918 qed |
|
3919 |
|
3920 lemma pdivmod_pdivmodrel: |
|
3921 \<open>eucl_rel_poly x y (q, r) \<longleftrightarrow> (x div y, x mod y) = (q, r)\<close> |
|
3922 using eucl_rel_poly_unique_div [of x y _ _ q r, OF eucl_rel_poly] |
|
3923 eucl_rel_poly_unique_mod [of x y _ _ q r, OF eucl_rel_poly] |
|
3924 eucl_rel_poly [of x y] |
|
3925 by auto |
|
3926 |
|
3927 lemma div_poly_eq: "eucl_rel_poly x y (q, r) \<Longrightarrow> x div y = q" |
|
3928 for x :: "'a::field poly" |
|
3929 by (simp add: pdivmod_pdivmodrel) |
|
3930 |
|
3931 lemma mod_poly_eq: "eucl_rel_poly x y (q, r) \<Longrightarrow> x mod y = r" |
|
3932 for x :: "'a::field poly" |
|
3933 by (simp add: pdivmod_pdivmodrel) |
|
3934 |
|
3935 lemma div_poly_less: |
|
3936 fixes x :: "'a::field poly" |
|
3937 assumes "degree x < degree y" |
|
3938 shows "x div y = 0" |
|
3939 proof - |
|
3940 from assms have "eucl_rel_poly x y (0, x)" |
|
3941 by (simp add: eucl_rel_poly_iff) |
|
3942 then show "x div y = 0" |
|
3943 by (rule div_poly_eq) |
|
3944 qed |
|
3945 |
|
3946 lemma mod_poly_less: |
|
3947 assumes "degree x < degree y" |
|
3948 shows "x mod y = x" |
|
3949 proof - |
|
3950 from assms have "eucl_rel_poly x y (0, x)" |
|
3951 by (simp add: eucl_rel_poly_iff) |
|
3952 then show "x mod y = x" |
|
3953 by (rule mod_poly_eq) |
|
3954 qed |
|
3955 |
|
3956 instantiation poly :: (field) unique_euclidean_ring |
3863 instantiation poly :: (field) unique_euclidean_ring |
3957 begin |
3864 begin |
3958 |
3865 |
3959 definition euclidean_size_poly :: "'a poly \<Rightarrow> nat" |
3866 definition euclidean_size_poly :: "'a poly \<Rightarrow> nat" |
3960 where "euclidean_size_poly p = (if p = 0 then 0 else 2 ^ degree p)" |
3867 where "euclidean_size_poly p = (if p = 0 then 0 else 2 ^ degree p)" |
3972 next |
3879 next |
3973 case False |
3880 case False |
3974 with \<open>p \<noteq> 0\<close> \<open>euclidean_size r < euclidean_size p\<close> |
3881 with \<open>p \<noteq> 0\<close> \<open>euclidean_size r < euclidean_size p\<close> |
3975 have \<open>degree r < degree p\<close> |
3882 have \<open>degree r < degree p\<close> |
3976 by (simp add: euclidean_size_poly_def) |
3883 by (simp add: euclidean_size_poly_def) |
3977 show \<open>(q * p + r) div p = q\<close> |
3884 with \<open>r \<noteq> 0\<close> have \<open>\<not> p dvd r\<close> |
3978 by (rule div_poly_eq) |
3885 by (auto dest: dvd_imp_degree) |
3979 (use \<open>degree r < degree p\<close> in \<open>auto simp add: eucl_rel_poly_iff\<close>) |
3886 have \<open>(q * p + r) div p = q \<and> (q * p + r) mod p = r\<close> |
|
3887 proof (rule ccontr) |
|
3888 assume \<open>\<not> ?thesis\<close> |
|
3889 moreover have *: \<open>((q * p + r) div p - q) * p = r - (q * p + r) mod p\<close> |
|
3890 by (simp add: algebra_simps) |
|
3891 ultimately have \<open>(q * p + r) div p \<noteq> q\<close> and \<open>(q * p + r) mod p \<noteq> r\<close> |
|
3892 using \<open>p \<noteq> 0\<close> by auto |
|
3893 from \<open>\<not> p dvd r\<close> have \<open>\<not> p dvd (q * p + r)\<close> |
|
3894 by simp |
|
3895 with \<open>p \<noteq> 0\<close> have \<open>degree ((q * p + r) mod p) < degree p\<close> |
|
3896 by (rule degree_mod_less_degree) |
|
3897 with \<open>degree r < degree p\<close> \<open>(q * p + r) mod p \<noteq> r\<close> |
|
3898 have \<open>degree (r - (q * p + r) mod p) < degree p\<close> |
|
3899 by (auto intro: degree_diff_less) |
|
3900 also have \<open>degree p \<le> degree ((q * p + r) div p - q) + degree p\<close> |
|
3901 by simp |
|
3902 also from \<open>(q * p + r) div p \<noteq> q\<close> \<open>p \<noteq> 0\<close> |
|
3903 have \<open>\<dots> = degree (((q * p + r) div p - q) * p)\<close> |
|
3904 by (simp add: degree_mult_eq) |
|
3905 also from * have \<open>\<dots> = degree (r - (q * p + r) mod p)\<close> |
|
3906 by simp |
|
3907 finally have \<open>degree (r - (q * p + r) mod p) < degree (r - (q * p + r) mod p)\<close> . |
|
3908 then show False |
|
3909 by simp |
|
3910 qed |
|
3911 then show \<open>(q * p + r) div p = q\<close> .. |
3980 qed |
3912 qed |
3981 qed (auto simp: euclidean_size_poly_def div_mult_mod_eq div_poly_less degree_mult_eq power_add |
3913 qed (auto simp: euclidean_size_poly_def degree_mult_eq power_add intro: degree_mod_less_degree) |
3982 intro!: degree_mod_less_degree split: if_splits) |
|
3983 |
3914 |
3984 end |
3915 end |
3985 |
3916 |
3986 lemma euclidean_relation_polyI [case_names by0 divides euclidean_relation]: |
3917 lemma euclidean_relation_polyI [case_names by0 divides euclidean_relation]: |
3987 \<open>(x div y, x mod y) = (q, r)\<close> |
3918 \<open>(x div y, x mod y) = (q, r)\<close> |
3993 |
3924 |
3994 lemma div_poly_eq_0_iff: |
3925 lemma div_poly_eq_0_iff: |
3995 \<open>x div y = 0 \<longleftrightarrow> x = 0 \<or> y = 0 \<or> degree x < degree y\<close> for x y :: \<open>'a::field poly\<close> |
3926 \<open>x div y = 0 \<longleftrightarrow> x = 0 \<or> y = 0 \<or> degree x < degree y\<close> for x y :: \<open>'a::field poly\<close> |
3996 by (simp add: unique_euclidean_semiring_class.div_eq_0_iff euclidean_size_poly_def) |
3927 by (simp add: unique_euclidean_semiring_class.div_eq_0_iff euclidean_size_poly_def) |
3997 |
3928 |
|
3929 lemma div_poly_less: |
|
3930 \<open>x div y = 0\<close> if \<open>degree x < degree y\<close> for x y :: \<open>'a::field poly\<close> |
|
3931 using that by (simp add: div_poly_eq_0_iff) |
|
3932 |
|
3933 lemma mod_poly_less: |
|
3934 \<open>x mod y = x\<close> if \<open>degree x < degree y\<close> |
|
3935 using that by (simp add: mod_eq_self_iff_div_eq_0 div_poly_eq_0_iff) |
|
3936 |
3998 lemma degree_div_less: |
3937 lemma degree_div_less: |
3999 fixes x y::"'a::field poly" |
3938 \<open>degree (x div y) < degree x\<close> |
4000 assumes "degree x\<noteq>0" "degree y\<noteq>0" |
3939 if \<open>degree x > 0\<close> \<open>degree y > 0\<close> |
4001 shows "degree (x div y) < degree x" |
3940 for x y :: \<open>'a::field poly\<close> |
4002 proof - |
3941 proof (cases \<open>x div y = 0\<close>) |
4003 have "x\<noteq>0" "y\<noteq>0" using assms by auto |
3942 case True |
4004 define q r where "q=x div y" and "r=x mod y" |
3943 with \<open>degree x > 0\<close> show ?thesis |
4005 have *:"eucl_rel_poly x y (q, r)" unfolding q_def r_def |
3944 by simp |
4006 by (simp add: eucl_rel_poly) |
3945 next |
4007 then have "r = 0 \<or> degree r < degree y" using \<open>y\<noteq>0\<close> unfolding eucl_rel_poly_iff by auto |
3946 case False |
4008 moreover have ?thesis when "r=0" |
3947 from that have \<open>x \<noteq> 0\<close> \<open>y \<noteq> 0\<close> |
4009 proof - |
3948 and *: \<open>degree (x div y * y + x mod y) > 0\<close> |
4010 have "x = q * y" using * that unfolding eucl_rel_poly_iff by auto |
3949 by auto |
4011 then have "q\<noteq>0" using \<open>x\<noteq>0\<close> \<open>y\<noteq>0\<close> by auto |
3950 show ?thesis |
4012 from degree_mult_eq[OF this \<open>y\<noteq>0\<close>] \<open>x = q * y\<close> |
3951 proof (cases \<open>y dvd x\<close>) |
4013 have "degree x = degree q +degree y" by auto |
|
4014 then show ?thesis unfolding q_def using assms by auto |
|
4015 qed |
|
4016 moreover have ?thesis when "degree r<degree y" |
|
4017 proof (cases "degree y>degree x") |
|
4018 case True |
3952 case True |
4019 then have "q=0" unfolding q_def using div_poly_less by auto |
3953 then obtain z where \<open>x = y * z\<close> .. |
4020 then show ?thesis unfolding q_def using assms(1) by auto |
3954 then have \<open>degree (x div y) < degree (x div y * y)\<close> |
|
3955 using \<open>y \<noteq> 0\<close> \<open>x \<noteq> 0\<close> \<open>degree y > 0\<close> by (simp add: degree_mult_eq) |
|
3956 with \<open>y dvd x\<close> show ?thesis |
|
3957 by simp |
4021 next |
3958 next |
4022 case False |
3959 case False |
4023 then have "degree x>degree r" using that by auto |
3960 with \<open>y \<noteq> 0\<close> have \<open>degree (x mod y) < degree y\<close> |
4024 then have "degree x = degree (x-r)" using degree_add_eq_right[of "-r" x] by auto |
3961 by (rule degree_mod_less_degree) |
4025 have "x-r = q*y" using * unfolding eucl_rel_poly_iff by auto |
3962 with \<open>y \<noteq> 0\<close> \<open>x div y \<noteq> 0\<close> have \<open>degree (x mod y) < degree (x div y * y)\<close> |
4026 then have "q\<noteq>0" using \<open>degree r < degree x\<close> by auto |
3963 by (simp add: degree_mult_eq) |
4027 have "degree x = degree q +degree y" |
3964 then have \<open>degree (x div y * y + x mod y) = degree (x div y * y)\<close> |
4028 using degree_mult_eq[OF \<open>q\<noteq>0\<close> \<open>y\<noteq>0\<close>] \<open>x-r = q*y\<close> \<open>degree x = degree (x-r)\<close> by auto |
3965 by (rule degree_add_eq_left) |
4029 then show ?thesis unfolding q_def using assms by auto |
3966 with \<open>y \<noteq> 0\<close> \<open>x div y \<noteq> 0\<close> \<open>degree y > 0\<close> show ?thesis |
|
3967 by (simp add: degree_mult_eq) |
4030 qed |
3968 qed |
4031 ultimately show ?thesis by auto |
3969 qed |
4032 qed |
3970 |
|
3971 lemma degree_mod_less': "b \<noteq> 0 \<Longrightarrow> a mod b \<noteq> 0 \<Longrightarrow> degree (a mod b) < degree b" |
|
3972 by (rule degree_mod_less_degree) auto |
4033 |
3973 |
4034 lemma degree_mod_less: "y \<noteq> 0 \<Longrightarrow> x mod y = 0 \<or> degree (x mod y) < degree y" |
3974 lemma degree_mod_less: "y \<noteq> 0 \<Longrightarrow> x mod y = 0 \<or> degree (x mod y) < degree y" |
4035 using eucl_rel_poly [of x y] unfolding eucl_rel_poly_iff by simp |
3975 using degree_mod_less' by blast |
4036 |
|
4037 lemma degree_mod_less': "b \<noteq> 0 \<Longrightarrow> a mod b \<noteq> 0 \<Longrightarrow> degree (a mod b) < degree b" |
|
4038 using degree_mod_less [of b a] by auto |
|
4039 |
|
4040 lemma eucl_rel_poly_pCons: |
|
4041 assumes rel: "eucl_rel_poly x y (q, r)" |
|
4042 assumes y: "y \<noteq> 0" |
|
4043 assumes b: "b = coeff (pCons a r) (degree y) / coeff y (degree y)" |
|
4044 shows "eucl_rel_poly (pCons a x) y (pCons b q, pCons a r - smult b y)" |
|
4045 (is "eucl_rel_poly ?x y (?q, ?r)") |
|
4046 proof - |
|
4047 from assms have x: "x = q * y + r" and r: "r = 0 \<or> degree r < degree y" |
|
4048 by (simp_all add: eucl_rel_poly_iff) |
|
4049 from b x have "?x = ?q * y + ?r" by simp |
|
4050 moreover |
|
4051 have "?r = 0 \<or> degree ?r < degree y" |
|
4052 proof (rule eq_zero_or_degree_less) |
|
4053 show "degree ?r \<le> degree y" |
|
4054 proof (rule degree_diff_le) |
|
4055 from r show "degree (pCons a r) \<le> degree y" |
|
4056 by auto |
|
4057 show "degree (smult b y) \<le> degree y" |
|
4058 by (rule degree_smult_le) |
|
4059 qed |
|
4060 from \<open>y \<noteq> 0\<close> show "coeff ?r (degree y) = 0" |
|
4061 by (simp add: b) |
|
4062 qed |
|
4063 ultimately show ?thesis |
|
4064 unfolding eucl_rel_poly_iff using \<open>y \<noteq> 0\<close> by simp |
|
4065 qed |
|
4066 |
3976 |
4067 lemma div_smult_left: \<open>smult a x div y = smult a (x div y)\<close> (is ?Q) |
3977 lemma div_smult_left: \<open>smult a x div y = smult a (x div y)\<close> (is ?Q) |
4068 and mod_smult_left: \<open>smult a x mod y = smult a (x mod y)\<close> (is ?R) |
3978 and mod_smult_left: \<open>smult a x mod y = smult a (x mod y)\<close> (is ?R) |
4069 for x y :: \<open>'a::field poly\<close> |
3979 for x y :: \<open>'a::field poly\<close> |
4070 proof - |
3980 proof - |
4189 qed |
4099 qed |
4190 then show ?Q and ?R |
4100 then show ?Q and ?R |
4191 by simp_all |
4101 by simp_all |
4192 qed |
4102 qed |
4193 |
4103 |
|
4104 lemma dvd_pCons_imp_dvd_pCons_mod: |
|
4105 \<open>y dvd pCons a (x mod y)\<close> if \<open>y dvd pCons a x\<close> |
|
4106 proof - |
|
4107 have \<open>pCons a x = pCons a (x div y * y + x mod y)\<close> |
|
4108 by simp |
|
4109 also have \<open>\<dots> = pCons 0 (x div y * y) + pCons a (x mod y)\<close> |
|
4110 by simp |
|
4111 also have \<open>pCons 0 (x div y * y) = (x div y * monom 1 (Suc 0)) * y\<close> |
|
4112 by (simp add: monom_Suc) |
|
4113 finally show \<open>y dvd pCons a (x mod y)\<close> |
|
4114 using \<open>y dvd pCons a x\<close> by simp |
|
4115 qed |
|
4116 |
|
4117 lemma degree_less_if_less_eqI: |
|
4118 \<open>degree x < degree y\<close> if \<open>degree x \<le> degree y\<close> \<open>coeff x (degree y) = 0\<close> \<open>x \<noteq> 0\<close> |
|
4119 proof (cases \<open>degree x = degree y\<close>) |
|
4120 case True |
|
4121 with \<open>coeff x (degree y) = 0\<close> have \<open>lead_coeff x = 0\<close> |
|
4122 by simp |
|
4123 then have \<open>x = 0\<close> |
|
4124 by simp |
|
4125 with \<open>x \<noteq> 0\<close> show ?thesis |
|
4126 by simp |
|
4127 next |
|
4128 case False |
|
4129 with \<open>degree x \<le> degree y\<close> show ?thesis |
|
4130 by simp |
|
4131 qed |
|
4132 |
4194 lemma div_pCons_eq: |
4133 lemma div_pCons_eq: |
4195 "pCons a p div q = |
4134 \<open>pCons a p div q = (if q = 0 then 0 else pCons (coeff (pCons a (p mod q)) (degree q) / lead_coeff q) (p div q))\<close> (is ?Q) |
4196 (if q = 0 then 0 |
4135 and mod_pCons_eq: |
4197 else pCons (coeff (pCons a (p mod q)) (degree q) / lead_coeff q) (p div q))" |
4136 \<open>pCons a p mod q = (if q = 0 then pCons a p else pCons a (p mod q) - smult (coeff (pCons a (p mod q)) (degree q) / lead_coeff q) q)\<close> (is ?R) |
4198 using eucl_rel_poly_pCons [OF eucl_rel_poly _ refl, of q a p] |
4137 for x y :: \<open>'a::field poly\<close> |
4199 by (auto intro: div_poly_eq) |
4138 proof - |
4200 |
4139 have \<open>?Q\<close> and \<open>?R\<close> if \<open>q = 0\<close> |
4201 lemma mod_pCons_eq: |
4140 using that by simp_all |
4202 "pCons a p mod q = |
4141 moreover have \<open>?Q\<close> and \<open>?R\<close> if \<open>q \<noteq> 0\<close> |
4203 (if q = 0 then pCons a p |
4142 proof - |
4204 else pCons a (p mod q) - smult (coeff (pCons a (p mod q)) (degree q) / lead_coeff q) q)" |
4143 define b where \<open>b = coeff (pCons a (p mod q)) (degree q) / lead_coeff q\<close> |
4205 using eucl_rel_poly_pCons [OF eucl_rel_poly _ refl, of q a p] |
4144 have \<open>(pCons a p div q, pCons a p mod q) = |
4206 by (auto intro: mod_poly_eq) |
4145 (pCons b (p div q), (pCons a (p mod q) - smult b q))\<close> (is \<open>_ = (?q, ?r)\<close>) |
|
4146 proof (cases q ?q ?r \<open>pCons a p\<close> rule: euclidean_relation_polyI) |
|
4147 case by0 |
|
4148 with \<open>q \<noteq> 0\<close> show ?case by simp |
|
4149 next |
|
4150 case divides |
|
4151 show ?case |
|
4152 proof (cases \<open>pCons a (p mod q) = 0\<close>) |
|
4153 case True |
|
4154 then show ?thesis |
|
4155 by (auto simp add: b_def) |
|
4156 next |
|
4157 case False |
|
4158 have \<open>q dvd pCons a (p mod q)\<close> |
|
4159 using \<open>q dvd pCons a p\<close> by (rule dvd_pCons_imp_dvd_pCons_mod) |
|
4160 then obtain s where *: \<open>pCons a (p mod q) = q * s\<close> .. |
|
4161 with False have \<open>s \<noteq> 0\<close> |
|
4162 by auto |
|
4163 from \<open>q \<noteq> 0\<close> have \<open>degree (pCons a (p mod q)) \<le> degree q\<close> |
|
4164 by (auto simp add: Suc_le_eq intro: degree_mod_less_degree) |
|
4165 moreover from \<open>s \<noteq> 0\<close> have \<open>degree q \<le> degree (pCons a (p mod q))\<close> |
|
4166 by (simp add: degree_mult_right_le *) |
|
4167 ultimately have \<open>degree (pCons a (p mod q)) = degree q\<close> |
|
4168 by (rule order.antisym) |
|
4169 with \<open>s \<noteq> 0\<close> \<open>q \<noteq> 0\<close> have \<open>degree s = 0\<close> |
|
4170 by (simp add: * degree_mult_eq) |
|
4171 then obtain c where \<open>s = [:c:]\<close> |
|
4172 by (rule degree_eq_zeroE) |
|
4173 also have \<open>c = b\<close> |
|
4174 using \<open>q \<noteq> 0\<close> by (simp add: b_def * \<open>s = [:c:]\<close>) |
|
4175 finally have \<open>smult b q = pCons a (p mod q)\<close> |
|
4176 by (simp add: *) |
|
4177 then show ?thesis |
|
4178 by simp |
|
4179 qed |
|
4180 next |
|
4181 case euclidean_relation |
|
4182 then have \<open>degree q > 0\<close> |
|
4183 using is_unit_iff_degree by blast |
|
4184 from \<open>q \<noteq> 0\<close> have \<open>degree (pCons a (p mod q)) \<le> degree q\<close> |
|
4185 by (auto simp add: Suc_le_eq intro: degree_mod_less_degree) |
|
4186 moreover have \<open>degree (smult b q) \<le> degree q\<close> |
|
4187 by (rule degree_smult_le) |
|
4188 ultimately have \<open>degree (pCons a (p mod q) - smult b q) \<le> degree q\<close> |
|
4189 by (rule degree_diff_le) |
|
4190 moreover have \<open>coeff (pCons a (p mod q) - smult b q) (degree q) = 0\<close> |
|
4191 using \<open>degree q > 0\<close> by (auto simp add: b_def) |
|
4192 ultimately have \<open>degree (pCons a (p mod q) - smult b q) < degree q\<close> |
|
4193 using \<open>degree q > 0\<close> |
|
4194 by (cases \<open>pCons a (p mod q) = smult b q\<close>) |
|
4195 (auto intro: degree_less_if_less_eqI) |
|
4196 then show ?case |
|
4197 by simp |
|
4198 qed |
|
4199 with \<open>q \<noteq> 0\<close> show ?Q and ?R |
|
4200 by (simp_all add: b_def) |
|
4201 qed |
|
4202 ultimately show ?Q and ?R |
|
4203 by simp_all |
|
4204 qed |
4207 |
4205 |
4208 lemma div_mod_fold_coeffs: |
4206 lemma div_mod_fold_coeffs: |
4209 "(p div q, p mod q) = |
4207 "(p div q, p mod q) = |
4210 (if q = 0 then (0, p) |
4208 (if q = 0 then (0, p) |
4211 else |
4209 else |