src/HOL/Decision_Procs/Rat_Pair.thy
changeset 62348 9a5f43dac883
parent 60698 29e8bdc41f90
child 62390 842917225d56
equal deleted inserted replaced
62347:2230b7047376 62348:9a5f43dac883
    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"