42 let ?g = "gcd a b" |
42 let ?g = "gcd a b" |
43 let ?a' = "a div ?g" |
43 let ?a' = "a div ?g" |
44 let ?b' = "b div ?g" |
44 let ?b' = "b div ?g" |
45 let ?g' = "gcd ?a' ?b'" |
45 let ?g' = "gcd ?a' ?b'" |
46 from anz bnz have "?g \<noteq> 0" by simp with gcd_ge_0_int[of a b] |
46 from anz bnz have "?g \<noteq> 0" by simp with gcd_ge_0_int[of a b] |
47 have gpos: "?g > 0" by arith |
47 have gpos: "?g > 0" by arith |
48 have gdvd: "?g dvd a" "?g dvd b" by arith+ |
48 have gdvd: "?g dvd a" "?g dvd b" by arith+ |
49 from zdvd_mult_div_cancel[OF gdvd(1)] zdvd_mult_div_cancel[OF gdvd(2)] |
49 from zdvd_mult_div_cancel[OF gdvd(1)] zdvd_mult_div_cancel[OF gdvd(2)] |
50 anz bnz |
50 anz bnz |
51 have nz':"?a' \<noteq> 0" "?b' \<noteq> 0" |
51 have nz':"?a' \<noteq> 0" "?b' \<noteq> 0" |
52 by - (rule notI, simp)+ |
52 by - (rule notI, simp)+ |
138 lemma Ninv_normN[simp]: "isnormNum x \<Longrightarrow> isnormNum (Ninv x)" |
138 lemma Ninv_normN[simp]: "isnormNum x \<Longrightarrow> isnormNum (Ninv x)" |
139 by (simp add: Ninv_def isnormNum_def split_def) |
139 by (simp add: Ninv_def isnormNum_def split_def) |
140 (cases "fst x = 0", auto simp add: gcd_commute_int) |
140 (cases "fst x = 0", auto simp add: gcd_commute_int) |
141 |
141 |
142 lemma isnormNum_int[simp]: |
142 lemma isnormNum_int[simp]: |
143 "isnormNum 0\<^sub>N" "isnormNum (1::int)\<^sub>N" "i \<noteq> 0 \<Longrightarrow> isnormNum i\<^sub>N" |
143 "isnormNum 0\<^sub>N" "isnormNum ((1::int)\<^sub>N)" "i \<noteq> 0 \<Longrightarrow> isnormNum (i\<^sub>N)" |
144 by (simp_all add: isnormNum_def) |
144 by (simp_all add: isnormNum_def) |
145 |
145 |
146 |
146 |
147 text {* Relations over Num *} |
147 text {* Relations over Num *} |
148 |
148 |
177 "Nle = (\<lambda>a b. 0\<ge>\<^sub>N (a -\<^sub>N b))" |
177 "Nle = (\<lambda>a b. 0\<ge>\<^sub>N (a -\<^sub>N b))" |
178 |
178 |
179 definition |
179 definition |
180 "INum = (\<lambda>(a,b). of_int a / of_int b)" |
180 "INum = (\<lambda>(a,b). of_int a / of_int b)" |
181 |
181 |
182 lemma INum_int [simp]: "INum i\<^sub>N = ((of_int i) ::'a::field)" "INum 0\<^sub>N = (0::'a::field)" |
182 lemma INum_int [simp]: "INum (i\<^sub>N) = ((of_int i) ::'a::field)" "INum 0\<^sub>N = (0::'a::field)" |
183 by (simp_all add: INum_def) |
183 by (simp_all add: INum_def) |
184 |
184 |
185 lemma isnormNum_unique[simp]: |
185 lemma isnormNum_unique[simp]: |
186 assumes na: "isnormNum x" and nb: "isnormNum y" |
186 assumes na: "isnormNum x" and nb: "isnormNum y" |
187 shows "((INum x ::'a::{field_char_0, field_inverse_zero}) = INum y) = (x = y)" (is "?lhs = ?rhs") |
187 shows "((INum x ::'a::{field_char_0, field_inverse_zero}) = INum y) = (x = y)" (is "?lhs = ?rhs") |
193 hence ?rhs using na nb H |
193 hence ?rhs using na nb H |
194 by (simp add: INum_def split_def isnormNum_def split: split_if_asm)} |
194 by (simp add: INum_def split_def isnormNum_def split: split_if_asm)} |
195 moreover |
195 moreover |
196 { assume az: "a \<noteq> 0" and bz: "b \<noteq> 0" and a'z: "a'\<noteq>0" and b'z: "b'\<noteq>0" |
196 { assume az: "a \<noteq> 0" and bz: "b \<noteq> 0" and a'z: "a'\<noteq>0" and b'z: "b'\<noteq>0" |
197 from az bz a'z b'z na nb have pos: "b > 0" "b' > 0" by (simp_all add: isnormNum_def) |
197 from az bz a'z b'z na nb have pos: "b > 0" "b' > 0" by (simp_all add: isnormNum_def) |
198 from prems have eq:"a * b' = a'*b" |
198 from H bz b'z have eq:"a * b' = a'*b" |
199 by (simp add: INum_def eq_divide_eq divide_eq_eq of_int_mult[symmetric] del: of_int_mult) |
199 by (simp add: INum_def eq_divide_eq divide_eq_eq of_int_mult[symmetric] del: of_int_mult) |
200 from prems have gcd1: "gcd a b = 1" "gcd b a = 1" "gcd a' b' = 1" "gcd b' a' = 1" |
200 from az a'z na nb have gcd1: "gcd a b = 1" "gcd b a = 1" "gcd a' b' = 1" "gcd b' a' = 1" |
201 by (simp_all add: isnormNum_def add: gcd_commute_int) |
201 by (simp_all add: isnormNum_def add: gcd_commute_int) |
202 from eq have raw_dvd: "a dvd a'*b" "b dvd b'*a" "a' dvd a*b'" "b' dvd b*a'" |
202 from eq have raw_dvd: "a dvd a'*b" "b dvd b'*a" "a' dvd a*b'" "b' dvd b*a'" |
203 apply - |
203 apply - |
204 apply algebra |
204 apply algebra |
205 apply algebra |
205 apply algebra |
206 apply simp |
206 apply simp |
207 apply algebra |
207 apply algebra |
208 done |
208 done |
209 from zdvd_antisym_abs[OF coprime_dvd_mult_int[OF gcd1(2) raw_dvd(2)] |
209 from zdvd_antisym_abs[OF coprime_dvd_mult_int[OF gcd1(2) raw_dvd(2)] |
210 coprime_dvd_mult_int[OF gcd1(4) raw_dvd(4)]] |
210 coprime_dvd_mult_int[OF gcd1(4) raw_dvd(4)]] |
211 have eq1: "b = b'" using pos by arith |
211 have eq1: "b = b'" using pos by arith |
212 with eq have "a = a'" using pos by simp |
212 with eq have "a = a'" using pos by simp |
213 with eq1 have ?rhs by simp} |
213 with eq1 have ?rhs by simp} |
214 ultimately show ?rhs by blast |
214 ultimately show ?rhs by blast |
215 next |
215 next |
216 assume ?rhs thus ?lhs by simp |
216 assume ?rhs thus ?lhs by simp |
223 |
223 |
224 lemma of_int_div_aux: "d ~= 0 ==> ((of_int x)::'a::field_char_0) / (of_int d) = |
224 lemma of_int_div_aux: "d ~= 0 ==> ((of_int x)::'a::field_char_0) / (of_int d) = |
225 of_int (x div d) + (of_int (x mod d)) / ((of_int d)::'a)" |
225 of_int (x div d) + (of_int (x mod d)) / ((of_int d)::'a)" |
226 proof - |
226 proof - |
227 assume "d ~= 0" |
227 assume "d ~= 0" |
228 hence dz: "of_int d \<noteq> (0::'a)" by (simp add: of_int_eq_0_iff) |
|
229 let ?t = "of_int (x div d) * ((of_int d)::'a) + of_int(x mod d)" |
228 let ?t = "of_int (x div d) * ((of_int d)::'a) + of_int(x mod d)" |
230 let ?f = "\<lambda>x. x / of_int d" |
229 let ?f = "\<lambda>x. x / of_int d" |
231 have "x = (x div d) * d + x mod d" |
230 have "x = (x div d) * d + x mod d" |
232 by auto |
231 by auto |
233 then have eq: "of_int x = ?t" |
232 then have eq: "of_int x = ?t" |
234 by (simp only: of_int_mult[symmetric] of_int_add [symmetric]) |
233 by (simp only: of_int_mult[symmetric] of_int_add [symmetric]) |
235 then have "of_int x / of_int d = ?t / of_int d" |
234 then have "of_int x / of_int d = ?t / of_int d" |
236 using cong[OF refl[of ?f] eq] by simp |
235 using cong[OF refl[of ?f] eq] by simp |
237 then show ?thesis by (simp add: add_divide_distrib algebra_simps prems) |
236 then show ?thesis by (simp add: add_divide_distrib algebra_simps `d ~= 0`) |
238 qed |
237 qed |
239 |
238 |
240 lemma of_int_div: "(d::int) ~= 0 ==> d dvd n ==> |
239 lemma of_int_div: "(d::int) ~= 0 ==> d dvd n ==> |
241 (of_int(n div d)::'a::field_char_0) = of_int n / of_int d" |
240 (of_int(n div d)::'a::field_char_0) = of_int n / of_int d" |
242 apply (frule of_int_div_aux [of d n, where ?'a = 'a]) |
241 apply (frule of_int_div_aux [of d n, where ?'a = 'a]) |
292 let ?g = "gcd (a * b' + b * a') (b*b')" |
291 let ?g = "gcd (a * b' + b * a') (b*b')" |
293 have gz: "?g \<noteq> 0" using z by simp |
292 have gz: "?g \<noteq> 0" using z by simp |
294 have ?thesis using aa' bb' z gz |
293 have ?thesis using aa' bb' z gz |
295 of_int_div[where ?'a = 'a, OF gz gcd_dvd1_int[where x="a * b' + b * a'" and y="b*b'"]] of_int_div[where ?'a = 'a, |
294 of_int_div[where ?'a = 'a, OF gz gcd_dvd1_int[where x="a * b' + b * a'" and y="b*b'"]] of_int_div[where ?'a = 'a, |
296 OF gz gcd_dvd2_int[where x="a * b' + b * a'" and y="b*b'"]] |
295 OF gz gcd_dvd2_int[where x="a * b' + b * a'" and y="b*b'"]] |
297 by (simp add: x y Nadd_def INum_def normNum_def Let_def add_divide_distrib)} |
296 by (simp add: Nadd_def INum_def normNum_def Let_def add_divide_distrib)} |
298 ultimately have ?thesis using aa' bb' |
297 ultimately have ?thesis using aa' bb' |
299 by (simp add: Nadd_def INum_def normNum_def x y Let_def) } |
298 by (simp add: Nadd_def INum_def normNum_def Let_def) } |
300 ultimately show ?thesis by blast |
299 ultimately show ?thesis by blast |
301 qed |
300 qed |
302 |
301 |
303 lemma Nmul[simp]: "INum (x *\<^sub>N y) = INum x * (INum y:: 'a :: {field_char_0, field_inverse_zero}) " |
302 lemma Nmul[simp]: "INum (x *\<^sub>N y) = INum x * (INum y:: 'a :: {field_char_0, field_inverse_zero}) " |
304 proof- |
303 proof- |
510 have " \<exists> a b a' b'. x = (a,b) \<and> y= (a',b')" by auto |
509 have " \<exists> a b a' b'. x = (a,b) \<and> y= (a',b')" by auto |
511 then obtain a b a' b' where xy[simp]: "x = (a,b)" "y = (a',b')" by blast |
510 then obtain a b a' b' where xy[simp]: "x = (a,b)" "y = (a',b')" by blast |
512 have n0: "isnormNum 0\<^sub>N" by simp |
511 have n0: "isnormNum 0\<^sub>N" by simp |
513 show ?thesis using nx ny |
512 show ?thesis using nx ny |
514 apply (simp only: isnormNum_unique[where ?'a = 'a, OF Nmul_normN[OF nx ny] n0, symmetric] Nmul[where ?'a = 'a]) |
513 apply (simp only: isnormNum_unique[where ?'a = 'a, OF Nmul_normN[OF nx ny] n0, symmetric] Nmul[where ?'a = 'a]) |
515 by (simp add: INum_def split_def isnormNum_def fst_conv snd_conv split: split_if_asm) |
514 by (simp add: INum_def split_def isnormNum_def split: split_if_asm) |
516 } |
515 } |
517 qed |
516 qed |
518 lemma Nneg_Nneg[simp]: "~\<^sub>N (~\<^sub>N c) = c" |
517 lemma Nneg_Nneg[simp]: "~\<^sub>N (~\<^sub>N c) = c" |
519 by (simp add: Nneg_def split_def) |
518 by (simp add: Nneg_def split_def) |
520 |
519 |
521 lemma Nmul1[simp]: |
520 lemma Nmul1[simp]: |
522 "isnormNum c \<Longrightarrow> 1\<^sub>N *\<^sub>N c = c" |
521 "isnormNum c \<Longrightarrow> 1\<^sub>N *\<^sub>N c = c" |
523 "isnormNum c \<Longrightarrow> c *\<^sub>N 1\<^sub>N = c" |
522 "isnormNum c \<Longrightarrow> c *\<^sub>N (1\<^sub>N) = c" |
524 apply (simp_all add: Nmul_def Let_def split_def isnormNum_def) |
523 apply (simp_all add: Nmul_def Let_def split_def isnormNum_def) |
525 apply (cases "fst c = 0", simp_all, cases c, simp_all)+ |
524 apply (cases "fst c = 0", simp_all, cases c, simp_all)+ |
526 done |
525 done |
527 |
526 |
528 end |
527 end |