src/HOL/Divides.thy
changeset 63040 eb4ddd18d635
parent 62597 b3f2b8c906a6
child 63145 703edebd1d92
equal deleted inserted replaced
63039:1a20fd9cf281 63040:eb4ddd18d635
   621   from assms mod_less_eq_dividend [of a "2 * b"] have "b \<le> a"
   621   from assms mod_less_eq_dividend [of a "2 * b"] have "b \<le> a"
   622     by (auto intro: trans)
   622     by (auto intro: trans)
   623   with \<open>0 < b\<close> have "0 < a div b" by (auto intro: div_positive)
   623   with \<open>0 < b\<close> have "0 < a div b" by (auto intro: div_positive)
   624   then have [simp]: "1 \<le> a div b" by (simp add: discrete)
   624   then have [simp]: "1 \<le> a div b" by (simp add: discrete)
   625   with \<open>0 < b\<close> have mod_less: "a mod b < b" by (simp add: pos_mod_bound)
   625   with \<open>0 < b\<close> have mod_less: "a mod b < b" by (simp add: pos_mod_bound)
   626   def w \<equiv> "a div b mod 2" with parity have w_exhaust: "w = 0 \<or> w = 1" by auto
   626   define w where "w = a div b mod 2"
       
   627   with parity have w_exhaust: "w = 0 \<or> w = 1" by auto
   627   have mod_w: "a mod (2 * b) = a mod b + b * w"
   628   have mod_w: "a mod (2 * b) = a mod b + b * w"
   628     by (simp add: w_def mod_mult2_eq ac_simps)
   629     by (simp add: w_def mod_mult2_eq ac_simps)
   629   from assms w_exhaust have "w = 1"
   630   from assms w_exhaust have "w = 1"
   630     by (auto simp add: mod_w) (insert mod_less, auto)
   631     by (auto simp add: mod_w) (insert mod_less, auto)
   631   with mod_w have mod: "a mod (2 * b) = a mod b + b" by simp
   632   with mod_w have mod: "a mod (2 * b) = a mod b + b" by simp
   639 lemma divmod_digit_0:
   640 lemma divmod_digit_0:
   640   assumes "0 < b" and "a mod (2 * b) < b"
   641   assumes "0 < b" and "a mod (2 * b) < b"
   641   shows "2 * (a div (2 * b)) = a div b" (is "?P")
   642   shows "2 * (a div (2 * b)) = a div b" (is "?P")
   642     and "a mod (2 * b) = a mod b" (is "?Q")
   643     and "a mod (2 * b) = a mod b" (is "?Q")
   643 proof -
   644 proof -
   644   def w \<equiv> "a div b mod 2" with parity have w_exhaust: "w = 0 \<or> w = 1" by auto
   645   define w where "w = a div b mod 2"
       
   646   with parity have w_exhaust: "w = 0 \<or> w = 1" by auto
   645   have mod_w: "a mod (2 * b) = a mod b + b * w"
   647   have mod_w: "a mod (2 * b) = a mod b + b * w"
   646     by (simp add: w_def mod_mult2_eq ac_simps)
   648     by (simp add: w_def mod_mult2_eq ac_simps)
   647   moreover have "b \<le> a mod b + b"
   649   moreover have "b \<le> a mod b + b"
   648   proof -
   650   proof -
   649     from \<open>0 < b\<close> pos_mod_sign have "0 \<le> a mod b" by blast
   651     from \<open>0 < b\<close> pos_mod_sign have "0 \<le> a mod b" by blast