src/HOL/Number_Theory/Euclidean_Algorithm.thy
changeset 60517 f16e4fb20652
parent 60516 0826b7025d07
child 60526 fad653acf58f
     1.1 --- a/src/HOL/Number_Theory/Euclidean_Algorithm.thy	Fri Jun 19 07:53:33 2015 +0200
     1.2 +++ b/src/HOL/Number_Theory/Euclidean_Algorithm.thy	Fri Jun 19 07:53:35 2015 +0200
     1.3 @@ -5,276 +5,6 @@
     1.4  theory Euclidean_Algorithm
     1.5  imports Complex_Main
     1.6  begin
     1.7 -
     1.8 -context semidom_divide
     1.9 -begin
    1.10 -
    1.11 -lemma dvd_div_mult_self [simp]:
    1.12 -  "a dvd b \<Longrightarrow> b div a * a = b"
    1.13 -  by (cases "a = 0") (auto elim: dvdE simp add: ac_simps)
    1.14 -
    1.15 -lemma dvd_mult_div_cancel [simp]:
    1.16 -  "a dvd b \<Longrightarrow> a * (b div a) = b"
    1.17 -  using dvd_div_mult_self [of a b] by (simp add: ac_simps)
    1.18 -  
    1.19 -lemma div_mult_swap:
    1.20 -  assumes "c dvd b"
    1.21 -  shows "a * (b div c) = (a * b) div c"
    1.22 -proof (cases "c = 0")
    1.23 -  case True then show ?thesis by simp
    1.24 -next
    1.25 -  case False from assms obtain d where "b = c * d" ..
    1.26 -  moreover from False have "a * divide (d * c) c = ((a * d) * c) div c"
    1.27 -    by simp
    1.28 -  ultimately show ?thesis by (simp add: ac_simps)
    1.29 -qed
    1.30 -
    1.31 -lemma dvd_div_mult:
    1.32 -  assumes "c dvd b"
    1.33 -  shows "b div c * a = (b * a) div c"
    1.34 -  using assms div_mult_swap [of c b a] by (simp add: ac_simps)
    1.35 -
    1.36 -  
    1.37 -text \<open>Units: invertible elements in a ring\<close>
    1.38 -
    1.39 -abbreviation is_unit :: "'a \<Rightarrow> bool"
    1.40 -where
    1.41 -  "is_unit a \<equiv> a dvd 1"
    1.42 -
    1.43 -lemma not_is_unit_0 [simp]:
    1.44 -  "\<not> is_unit 0"
    1.45 -  by simp
    1.46 -
    1.47 -lemma unit_imp_dvd [dest]: 
    1.48 -  "is_unit b \<Longrightarrow> b dvd a"
    1.49 -  by (rule dvd_trans [of _ 1]) simp_all
    1.50 -
    1.51 -lemma unit_dvdE:
    1.52 -  assumes "is_unit a"
    1.53 -  obtains c where "a \<noteq> 0" and "b = a * c"
    1.54 -proof -
    1.55 -  from assms have "a dvd b" by auto
    1.56 -  then obtain c where "b = a * c" ..
    1.57 -  moreover from assms have "a \<noteq> 0" by auto
    1.58 -  ultimately show thesis using that by blast
    1.59 -qed
    1.60 -
    1.61 -lemma dvd_unit_imp_unit:
    1.62 -  "a dvd b \<Longrightarrow> is_unit b \<Longrightarrow> is_unit a"
    1.63 -  by (rule dvd_trans)
    1.64 -
    1.65 -lemma unit_div_1_unit [simp, intro]:
    1.66 -  assumes "is_unit a"
    1.67 -  shows "is_unit (1 div a)"
    1.68 -proof -
    1.69 -  from assms have "1 = 1 div a * a" by simp
    1.70 -  then show "is_unit (1 div a)" by (rule dvdI)
    1.71 -qed
    1.72 -
    1.73 -lemma is_unitE [elim?]:
    1.74 -  assumes "is_unit a"
    1.75 -  obtains b where "a \<noteq> 0" and "b \<noteq> 0"
    1.76 -    and "is_unit b" and "1 div a = b" and "1 div b = a"
    1.77 -    and "a * b = 1" and "c div a = c * b"
    1.78 -proof (rule that)
    1.79 -  def b \<equiv> "1 div a"
    1.80 -  then show "1 div a = b" by simp
    1.81 -  from b_def `is_unit a` show "is_unit b" by simp
    1.82 -  from `is_unit a` and `is_unit b` show "a \<noteq> 0" and "b \<noteq> 0" by auto
    1.83 -  from b_def `is_unit a` show "a * b = 1" by simp
    1.84 -  then have "1 = a * b" ..
    1.85 -  with b_def `b \<noteq> 0` show "1 div b = a" by simp
    1.86 -  from `is_unit a` have "a dvd c" ..
    1.87 -  then obtain d where "c = a * d" ..
    1.88 -  with `a \<noteq> 0` `a * b = 1` show "c div a = c * b"
    1.89 -    by (simp add: mult.assoc mult.left_commute [of a])
    1.90 -qed
    1.91 -
    1.92 -lemma unit_prod [intro]:
    1.93 -  "is_unit a \<Longrightarrow> is_unit b \<Longrightarrow> is_unit (a * b)"
    1.94 -  by (subst mult_1_left [of 1, symmetric]) (rule mult_dvd_mono) 
    1.95 -  
    1.96 -lemma unit_div [intro]:
    1.97 -  "is_unit a \<Longrightarrow> is_unit b \<Longrightarrow> is_unit (a div b)"
    1.98 -  by (erule is_unitE [of b a]) (simp add: ac_simps unit_prod)
    1.99 -
   1.100 -lemma mult_unit_dvd_iff:
   1.101 -  assumes "is_unit b"
   1.102 -  shows "a * b dvd c \<longleftrightarrow> a dvd c"
   1.103 -proof
   1.104 -  assume "a * b dvd c"
   1.105 -  with assms show "a dvd c"
   1.106 -    by (simp add: dvd_mult_left)
   1.107 -next
   1.108 -  assume "a dvd c"
   1.109 -  then obtain k where "c = a * k" ..
   1.110 -  with assms have "c = (a * b) * (1 div b * k)"
   1.111 -    by (simp add: mult_ac)
   1.112 -  then show "a * b dvd c" by (rule dvdI)
   1.113 -qed
   1.114 -
   1.115 -lemma dvd_mult_unit_iff:
   1.116 -  assumes "is_unit b"
   1.117 -  shows "a dvd c * b \<longleftrightarrow> a dvd c"
   1.118 -proof
   1.119 -  assume "a dvd c * b"
   1.120 -  with assms have "c * b dvd c * (b * (1 div b))"
   1.121 -    by (subst mult_assoc [symmetric]) simp
   1.122 -  also from `is_unit b` have "b * (1 div b) = 1" by (rule is_unitE) simp
   1.123 -  finally have "c * b dvd c" by simp
   1.124 -  with `a dvd c * b` show "a dvd c" by (rule dvd_trans)
   1.125 -next
   1.126 -  assume "a dvd c"
   1.127 -  then show "a dvd c * b" by simp
   1.128 -qed
   1.129 -
   1.130 -lemma div_unit_dvd_iff:
   1.131 -  "is_unit b \<Longrightarrow> a div b dvd c \<longleftrightarrow> a dvd c"
   1.132 -  by (erule is_unitE [of _ a]) (auto simp add: mult_unit_dvd_iff)
   1.133 -
   1.134 -lemma dvd_div_unit_iff:
   1.135 -  "is_unit b \<Longrightarrow> a dvd c div b \<longleftrightarrow> a dvd c"
   1.136 -  by (erule is_unitE [of _ c]) (simp add: dvd_mult_unit_iff)
   1.137 -
   1.138 -lemmas unit_dvd_iff = mult_unit_dvd_iff div_unit_dvd_iff
   1.139 -  dvd_mult_unit_iff dvd_div_unit_iff -- \<open>FIXME consider fact collection\<close>
   1.140 -
   1.141 -lemma unit_mult_div_div [simp]:
   1.142 -  "is_unit a \<Longrightarrow> b * (1 div a) = b div a"
   1.143 -  by (erule is_unitE [of _ b]) simp
   1.144 -
   1.145 -lemma unit_div_mult_self [simp]:
   1.146 -  "is_unit a \<Longrightarrow> b div a * a = b"
   1.147 -  by (rule dvd_div_mult_self) auto
   1.148 -
   1.149 -lemma unit_div_1_div_1 [simp]:
   1.150 -  "is_unit a \<Longrightarrow> 1 div (1 div a) = a"
   1.151 -  by (erule is_unitE) simp
   1.152 -
   1.153 -lemma unit_div_mult_swap:
   1.154 -  "is_unit c \<Longrightarrow> a * (b div c) = (a * b) div c"
   1.155 -  by (erule unit_dvdE [of _ b]) (simp add: mult.left_commute [of _ c])
   1.156 -
   1.157 -lemma unit_div_commute:
   1.158 -  "is_unit b \<Longrightarrow> (a div b) * c = (a * c) div b"
   1.159 -  using unit_div_mult_swap [of b c a] by (simp add: ac_simps)
   1.160 -
   1.161 -lemma unit_eq_div1:
   1.162 -  "is_unit b \<Longrightarrow> a div b = c \<longleftrightarrow> a = c * b"
   1.163 -  by (auto elim: is_unitE)
   1.164 -
   1.165 -lemma unit_eq_div2:
   1.166 -  "is_unit b \<Longrightarrow> a = c div b \<longleftrightarrow> a * b = c"
   1.167 -  using unit_eq_div1 [of b c a] by auto
   1.168 -
   1.169 -lemma unit_mult_left_cancel:
   1.170 -  assumes "is_unit a"
   1.171 -  shows "a * b = a * c \<longleftrightarrow> b = c" (is "?P \<longleftrightarrow> ?Q")
   1.172 -  using assms mult_cancel_left [of a b c] by auto 
   1.173 -
   1.174 -lemma unit_mult_right_cancel:
   1.175 -  "is_unit a \<Longrightarrow> b * a = c * a \<longleftrightarrow> b = c"
   1.176 -  using unit_mult_left_cancel [of a b c] by (auto simp add: ac_simps)
   1.177 -
   1.178 -lemma unit_div_cancel:
   1.179 -  assumes "is_unit a"
   1.180 -  shows "b div a = c div a \<longleftrightarrow> b = c"
   1.181 -proof -
   1.182 -  from assms have "is_unit (1 div a)" by simp
   1.183 -  then have "b * (1 div a) = c * (1 div a) \<longleftrightarrow> b = c"
   1.184 -    by (rule unit_mult_right_cancel)
   1.185 -  with assms show ?thesis by simp
   1.186 -qed
   1.187 -  
   1.188 -
   1.189 -text \<open>Associated elements in a ring – an equivalence relation induced by the quasi-order divisibility \<close>
   1.190 -
   1.191 -definition associated :: "'a \<Rightarrow> 'a \<Rightarrow> bool" 
   1.192 -where
   1.193 -  "associated a b \<longleftrightarrow> a dvd b \<and> b dvd a"
   1.194 -
   1.195 -lemma associatedI:
   1.196 -  "a dvd b \<Longrightarrow> b dvd a \<Longrightarrow> associated a b"
   1.197 -  by (simp add: associated_def)
   1.198 -
   1.199 -lemma associatedD1:
   1.200 -  "associated a b \<Longrightarrow> a dvd b"
   1.201 -  by (simp add: associated_def)
   1.202 -
   1.203 -lemma associatedD2:
   1.204 -  "associated a b \<Longrightarrow> b dvd a"
   1.205 -  by (simp add: associated_def)
   1.206 -
   1.207 -lemma associated_refl [simp]:
   1.208 -  "associated a a"
   1.209 -  by (auto intro: associatedI)
   1.210 -
   1.211 -lemma associated_sym:
   1.212 -  "associated b a \<longleftrightarrow> associated a b"
   1.213 -  by (auto intro: associatedI dest: associatedD1 associatedD2)
   1.214 -
   1.215 -lemma associated_trans:
   1.216 -  "associated a b \<Longrightarrow> associated b c \<Longrightarrow> associated a c"
   1.217 -  by (auto intro: associatedI dvd_trans dest: associatedD1 associatedD2)
   1.218 -
   1.219 -lemma equivp_associated:
   1.220 -  "equivp associated"
   1.221 -proof (rule equivpI)
   1.222 -  show "reflp associated"
   1.223 -    by (rule reflpI) simp
   1.224 -  show "symp associated"
   1.225 -    by (rule sympI) (simp add: associated_sym)
   1.226 -  show "transp associated"
   1.227 -    by (rule transpI) (fact associated_trans)
   1.228 -qed
   1.229 -
   1.230 -lemma associated_0 [simp]:
   1.231 -  "associated 0 b \<longleftrightarrow> b = 0"
   1.232 -  "associated a 0 \<longleftrightarrow> a = 0"
   1.233 -  by (auto dest: associatedD1 associatedD2)
   1.234 -
   1.235 -lemma associated_unit:
   1.236 -  "associated a b \<Longrightarrow> is_unit a \<Longrightarrow> is_unit b"
   1.237 -  using dvd_unit_imp_unit by (auto dest!: associatedD1 associatedD2)
   1.238 -
   1.239 -lemma is_unit_associatedI:
   1.240 -  assumes "is_unit c" and "a = c * b"
   1.241 -  shows "associated a b"
   1.242 -proof (rule associatedI)
   1.243 -  from `a = c * b` show "b dvd a" by auto
   1.244 -  from `is_unit c` obtain d where "c * d = 1" by (rule is_unitE)
   1.245 -  moreover from `a = c * b` have "d * a = d * (c * b)" by simp
   1.246 -  ultimately have "b = a * d" by (simp add: ac_simps)
   1.247 -  then show "a dvd b" ..
   1.248 -qed
   1.249 -
   1.250 -lemma associated_is_unitE:
   1.251 -  assumes "associated a b"
   1.252 -  obtains c where "is_unit c" and "a = c * b"
   1.253 -proof (cases "b = 0")
   1.254 -  case True with assms have "is_unit 1" and "a = 1 * b" by simp_all
   1.255 -  with that show thesis .
   1.256 -next
   1.257 -  case False
   1.258 -  from assms have "a dvd b" and "b dvd a" by (auto dest: associatedD1 associatedD2)
   1.259 -  then obtain c d where "b = a * d" and "a = b * c" by (blast elim: dvdE)
   1.260 -  then have "a = c * b" and "(c * d) * b = 1 * b" by (simp_all add: ac_simps)
   1.261 -  with False have "c * d = 1" using mult_cancel_right [of "c * d" b 1] by simp
   1.262 -  then have "is_unit c" by auto
   1.263 -  with `a = c * b` that show thesis by blast
   1.264 -qed
   1.265 -  
   1.266 -lemmas unit_simps = mult_unit_dvd_iff div_unit_dvd_iff dvd_mult_unit_iff 
   1.267 -  dvd_div_unit_iff unit_div_mult_swap unit_div_commute
   1.268 -  unit_mult_left_cancel unit_mult_right_cancel unit_div_cancel 
   1.269 -  unit_eq_div1 unit_eq_div2
   1.270 -
   1.271 -end
   1.272 -
   1.273 -lemma is_unit_int:
   1.274 -  "is_unit (k::int) \<longleftrightarrow> k = 1 \<or> k = - 1"
   1.275 -  by auto
   1.276 -
   1.277    
   1.278  text {*
   1.279    A Euclidean semiring is a semiring upon which the Euclidean algorithm can be