equal
deleted
inserted
replaced
25 (if a = 0 \<or> b = 0 then (0, 0) |
25 (if a = 0 \<or> b = 0 then (0, 0) |
26 else |
26 else |
27 (let g = gcd a b |
27 (let g = gcd a b |
28 in if b > 0 then (a div g, b div g) else (- (a div g), - (b div g)))))" |
28 in if b > 0 then (a div g, b div g) else (- (a div g), - (b div g)))))" |
29 |
29 |
30 declare gcd_dvd1_int[presburger] gcd_dvd2_int[presburger] |
30 declare gcd_dvd1[presburger] gcd_dvd2[presburger] |
31 |
31 |
32 lemma normNum_isnormNum [simp]: "isnormNum (normNum x)" |
32 lemma normNum_isnormNum [simp]: "isnormNum (normNum x)" |
33 proof - |
33 proof - |
34 obtain a b where x: "x = (a, b)" by (cases x) |
34 obtain a b where x: "x = (a, b)" by (cases x) |
35 consider "a = 0 \<or> b = 0" | "a \<noteq> 0" "b \<noteq> 0" |
35 consider "a = 0 \<or> b = 0" | "a \<noteq> 0" "b \<noteq> 0" |
49 with gcd_ge_0_int[of a b] have gpos: "?g > 0" by arith |
49 with gcd_ge_0_int[of a b] have gpos: "?g > 0" by arith |
50 have gdvd: "?g dvd a" "?g dvd b" by arith+ |
50 have gdvd: "?g dvd a" "?g dvd b" by arith+ |
51 from dvd_mult_div_cancel[OF gdvd(1)] dvd_mult_div_cancel[OF gdvd(2)] ab |
51 from dvd_mult_div_cancel[OF gdvd(1)] dvd_mult_div_cancel[OF gdvd(2)] ab |
52 have nz': "?a' \<noteq> 0" "?b' \<noteq> 0" by - (rule notI, simp)+ |
52 have nz': "?a' \<noteq> 0" "?b' \<noteq> 0" by - (rule notI, simp)+ |
53 from ab have stupid: "a \<noteq> 0 \<or> b \<noteq> 0" by arith |
53 from ab have stupid: "a \<noteq> 0 \<or> b \<noteq> 0" by arith |
54 from div_gcd_coprime_int[OF stupid] have gp1: "?g' = 1" . |
54 from div_gcd_coprime[OF stupid] have gp1: "?g' = 1" . |
55 from ab consider "b < 0" | "b > 0" by arith |
55 from ab consider "b < 0" | "b > 0" by arith |
56 then show ?thesis |
56 then show ?thesis |
57 proof cases |
57 proof cases |
58 case b: 1 |
58 case b: 1 |
59 have False if b': "?b' \<ge> 0" |
59 have False if b': "?b' \<ge> 0" |
140 qed |
140 qed |
141 |
141 |
142 lemma Ninv_normN[simp]: "isnormNum x \<Longrightarrow> isnormNum (Ninv x)" |
142 lemma Ninv_normN[simp]: "isnormNum x \<Longrightarrow> isnormNum (Ninv x)" |
143 apply (simp add: Ninv_def isnormNum_def split_def) |
143 apply (simp add: Ninv_def isnormNum_def split_def) |
144 apply (cases "fst x = 0") |
144 apply (cases "fst x = 0") |
145 apply (auto simp add: gcd_commute_int) |
145 apply (auto simp add: gcd.commute) |
146 done |
146 done |
147 |
147 |
148 lemma isnormNum_int[simp]: "isnormNum 0\<^sub>N" "isnormNum ((1::int)\<^sub>N)" "i \<noteq> 0 \<Longrightarrow> isnormNum (i)\<^sub>N" |
148 lemma isnormNum_int[simp]: "isnormNum 0\<^sub>N" "isnormNum ((1::int)\<^sub>N)" "i \<noteq> 0 \<Longrightarrow> isnormNum (i)\<^sub>N" |
149 by (simp_all add: isnormNum_def) |
149 by (simp_all add: isnormNum_def) |
150 |
150 |
195 by (simp_all add: x y isnormNum_def) |
195 by (simp_all add: x y isnormNum_def) |
196 from H \<open>b \<noteq> 0\<close> \<open>b' \<noteq> 0\<close> have eq: "a * b' = a' * b" |
196 from H \<open>b \<noteq> 0\<close> \<open>b' \<noteq> 0\<close> have eq: "a * b' = a' * b" |
197 by (simp add: x y INum_def eq_divide_eq divide_eq_eq of_int_mult[symmetric] del: of_int_mult) |
197 by (simp add: x y INum_def eq_divide_eq divide_eq_eq of_int_mult[symmetric] del: of_int_mult) |
198 from \<open>a \<noteq> 0\<close> \<open>a' \<noteq> 0\<close> na nb |
198 from \<open>a \<noteq> 0\<close> \<open>a' \<noteq> 0\<close> na nb |
199 have gcd1: "gcd a b = 1" "gcd b a = 1" "gcd a' b' = 1" "gcd b' a' = 1" |
199 have gcd1: "gcd a b = 1" "gcd b a = 1" "gcd a' b' = 1" "gcd b' a' = 1" |
200 by (simp_all add: x y isnormNum_def add: gcd_commute_int) |
200 by (simp_all add: x y isnormNum_def add: gcd.commute) |
201 from eq have raw_dvd: "a dvd a' * b" "b dvd b' * a" "a' dvd a * b'" "b' dvd b * a'" |
201 from eq have raw_dvd: "a dvd a' * b" "b dvd b' * a" "a' dvd a * b'" "b' dvd b * a'" |
202 apply - |
202 apply - |
203 apply algebra |
203 apply algebra |
204 apply algebra |
204 apply algebra |
205 apply simp |
205 apply simp |
206 apply algebra |
206 apply algebra |
207 done |
207 done |
208 from zdvd_antisym_abs[OF coprime_dvd_mult_int[OF gcd1(2) raw_dvd(2)] |
208 from zdvd_antisym_abs[OF coprime_dvd_mult[OF gcd1(2) raw_dvd(2)] |
209 coprime_dvd_mult_int[OF gcd1(4) raw_dvd(4)]] |
209 coprime_dvd_mult[OF gcd1(4) raw_dvd(4)]] |
210 have eq1: "b = b'" using pos by arith |
210 have eq1: "b = b'" using pos by arith |
211 with eq have "a = a'" using pos by simp |
211 with eq have "a = a'" using pos by simp |
212 with eq1 show ?thesis by (simp add: x y) |
212 with eq1 show ?thesis by (simp add: x y) |
213 qed |
213 qed |
214 show ?lhs if ?rhs |
214 show ?lhs if ?rhs |
549 with isnormNum_unique[OF n] show ?thesis |
549 with isnormNum_unique[OF n] show ?thesis |
550 by simp |
550 by simp |
551 qed |
551 qed |
552 |
552 |
553 lemma Nmul_commute: "isnormNum x \<Longrightarrow> isnormNum y \<Longrightarrow> x *\<^sub>N y = y *\<^sub>N x" |
553 lemma Nmul_commute: "isnormNum x \<Longrightarrow> isnormNum y \<Longrightarrow> x *\<^sub>N y = y *\<^sub>N x" |
554 by (simp add: Nmul_def split_def Let_def gcd_commute_int mult.commute) |
554 by (simp add: Nmul_def split_def Let_def gcd.commute mult.commute) |
555 |
555 |
556 lemma Nmul_assoc: |
556 lemma Nmul_assoc: |
557 assumes "SORT_CONSTRAINT('a::{field_char_0,field})" |
557 assumes "SORT_CONSTRAINT('a::{field_char_0,field})" |
558 assumes nx: "isnormNum x" |
558 assumes nx: "isnormNum x" |
559 and ny: "isnormNum y" |
559 and ny: "isnormNum y" |