equal
deleted
inserted
replaced
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 |