src/HOL/Integ/IntDiv.thy
changeset 14387 e96d5c42c4b0
parent 14378 69c4d5997669
child 14473 846c237bd9b3
equal deleted inserted replaced
14386:ad1ffcc90162 14387:e96d5c42c4b0
    99 apply (subgoal_tac "0 < b * (1 + q - q') ")
    99 apply (subgoal_tac "0 < b * (1 + q - q') ")
   100 apply (erule_tac [2] order_le_less_trans)
   100 apply (erule_tac [2] order_le_less_trans)
   101  prefer 2 apply (simp add: zdiff_zmult_distrib2 zadd_zmult_distrib2)
   101  prefer 2 apply (simp add: zdiff_zmult_distrib2 zadd_zmult_distrib2)
   102 apply (subgoal_tac "b * q' < b * (1 + q) ")
   102 apply (subgoal_tac "b * q' < b * (1 + q) ")
   103  prefer 2 apply (simp add: zdiff_zmult_distrib2 zadd_zmult_distrib2)
   103  prefer 2 apply (simp add: zdiff_zmult_distrib2 zadd_zmult_distrib2)
   104 apply (simp add: zmult_zless_cancel1)
   104 apply (simp add: mult_less_cancel_left)
   105 done
   105 done
   106 
   106 
   107 lemma unique_quotient_lemma_neg:
   107 lemma unique_quotient_lemma_neg:
   108      "[| b*q' + r' \<le> b*q + r;  r \<le> 0;  b < 0;  b < r' |]  
   108      "[| b*q' + r' \<le> b*q + r;  r \<le> 0;  b < 0;  b < r' |]  
   109       ==> q \<le> (q'::int)"
   109       ==> q \<le> (q'::int)"
   524      "[| b*q + r = b'*q' + r';  0 \<le> b'*q' + r';   
   524      "[| b*q + r = b'*q' + r';  0 \<le> b'*q' + r';   
   525          r' < b';  0 \<le> r;  0 < b';  b' \<le> b |]   
   525          r' < b';  0 \<le> r;  0 < b';  b' \<le> b |]   
   526       ==> q \<le> (q'::int)"
   526       ==> q \<le> (q'::int)"
   527 apply (frule q_pos_lemma, assumption+) 
   527 apply (frule q_pos_lemma, assumption+) 
   528 apply (subgoal_tac "b*q < b* (q' + 1) ")
   528 apply (subgoal_tac "b*q < b* (q' + 1) ")
   529  apply (simp add: zmult_zless_cancel1)
   529  apply (simp add: mult_less_cancel_left)
   530 apply (subgoal_tac "b*q = r' - r + b'*q'")
   530 apply (subgoal_tac "b*q = r' - r + b'*q'")
   531  prefer 2 apply simp
   531  prefer 2 apply simp
   532 apply (simp (no_asm_simp) add: zadd_zmult_distrib2)
   532 apply (simp (no_asm_simp) add: zadd_zmult_distrib2)
   533 apply (subst zadd_commute, rule zadd_zless_mono, arith)
   533 apply (subst zadd_commute, rule zadd_zless_mono, arith)
   534 apply (rule mult_right_mono, auto)
   534 apply (rule mult_right_mono, auto)
   556      "[| b*q + r = b'*q' + r';  b'*q' + r' < 0;   
   556      "[| b*q + r = b'*q' + r';  b'*q' + r' < 0;   
   557          r < b;  0 \<le> r';  0 < b';  b' \<le> b |]   
   557          r < b;  0 \<le> r';  0 < b';  b' \<le> b |]   
   558       ==> q' \<le> (q::int)"
   558       ==> q' \<le> (q::int)"
   559 apply (frule q_neg_lemma, assumption+) 
   559 apply (frule q_neg_lemma, assumption+) 
   560 apply (subgoal_tac "b*q' < b* (q + 1) ")
   560 apply (subgoal_tac "b*q' < b* (q + 1) ")
   561  apply (simp add: zmult_zless_cancel1)
   561  apply (simp add: mult_less_cancel_left)
   562 apply (simp add: zadd_zmult_distrib2)
   562 apply (simp add: zadd_zmult_distrib2)
   563 apply (subgoal_tac "b*q' \<le> b'*q'")
   563 apply (subgoal_tac "b*q' \<le> b'*q'")
   564  prefer 2 apply (simp add: mult_right_mono_neg)
   564  prefer 2 apply (simp add: mult_right_mono_neg)
   565 apply (subgoal_tac "b'*q' < b + b*q")
   565 apply (subgoal_tac "b'*q' < b + b*q")
   566  apply arith
   566  apply arith
   723 lemma zmult2_lemma_aux4: "[| (0::int) < c; 0 \<le> r; r < b |] ==> b * (q mod c) + r < b * c"
   723 lemma zmult2_lemma_aux4: "[| (0::int) < c; 0 \<le> r; r < b |] ==> b * (q mod c) + r < b * c"
   724 apply (subgoal_tac "r * 1 < b * (c - q mod c) ")
   724 apply (subgoal_tac "r * 1 < b * (c - q mod c) ")
   725 apply (simp add: zdiff_zmult_distrib2)
   725 apply (simp add: zdiff_zmult_distrib2)
   726 apply (rule order_less_le_trans)
   726 apply (rule order_less_le_trans)
   727 apply (erule mult_strict_right_mono)
   727 apply (erule mult_strict_right_mono)
   728 apply (rule_tac [2] zmult_zle_mono2)
   728 apply (rule_tac [2] mult_left_mono)
   729 apply (auto simp add: compare_rls zadd_commute [of 1]
   729 apply (auto simp add: compare_rls zadd_commute [of 1]
   730                       add1_zle_eq pos_mod_bound)
   730                       add1_zle_eq pos_mod_bound)
   731 done
   731 done
   732 
   732 
   733 lemma zmult2_lemma: "[| quorem ((a,b), (q,r));  b ~= 0;  0 < c |]  
   733 lemma zmult2_lemma: "[| quorem ((a,b), (q,r));  b ~= 0;  0 < c |]  
   902 lemma zdiv_number_of_BIT[simp]:
   902 lemma zdiv_number_of_BIT[simp]:
   903      "number_of (v BIT b) div number_of (w BIT False) =  
   903      "number_of (v BIT b) div number_of (w BIT False) =  
   904           (if ~b | (0::int) \<le> number_of w                    
   904           (if ~b | (0::int) \<le> number_of w                    
   905            then number_of v div (number_of w)     
   905            then number_of v div (number_of w)     
   906            else (number_of v + (1::int)) div (number_of w))"
   906            else (number_of v + (1::int)) div (number_of w))"
   907 apply (simp only: zadd_assoc number_of_BIT)
   907 apply (simp only: add_assoc number_of_BIT)
   908 (*create subgoal because the next step can't simplify numerals*)
   908 (*create subgoal because the next step can't simplify numerals*)
   909 apply (subgoal_tac "2 ~= (0::int) ")
   909 apply (subgoal_tac "2 ~= (0::int) ") 
   910 apply (simp del: bin_arith_extra_simps 
   910 apply (simp del: bin_arith_extra_simps arith_special
   911          add: zdiv_zmult_zmult1 pos_zdiv_mult_2 not_0_le_lemma neg_zdiv_mult_2, simp)
   911          add: zdiv_zmult_zmult1 pos_zdiv_mult_2 not_0_le_lemma neg_zdiv_mult_2)
       
   912 apply simp
   912 done
   913 done
   913 
   914 
   914 
   915 
   915 (** computing mod by shifting (proofs resemble those for div) **)
   916 (** computing mod by shifting (proofs resemble those for div) **)
   916 
   917 
   920 apply (subgoal_tac "1 \<le> a")
   921 apply (subgoal_tac "1 \<le> a")
   921  prefer 2 apply arith
   922  prefer 2 apply arith
   922 apply (subgoal_tac "1 < a * 2")
   923 apply (subgoal_tac "1 < a * 2")
   923  prefer 2 apply arith
   924  prefer 2 apply arith
   924 apply (subgoal_tac "2* (1 + b mod a) \<le> 2*a")
   925 apply (subgoal_tac "2* (1 + b mod a) \<le> 2*a")
   925  apply (rule_tac [2] zmult_zle_mono2)
   926  apply (rule_tac [2] mult_left_mono)
   926 apply (auto simp add: zadd_commute [of 1] zmult_commute add1_zle_eq 
   927 apply (auto simp add: zadd_commute [of 1] zmult_commute add1_zle_eq 
   927                       pos_mod_bound)
   928                       pos_mod_bound)
   928 apply (subst zmod_zadd1_eq)
   929 apply (subst zmod_zadd1_eq)
   929 apply (simp add: zmod_zmult_zmult2 mod_pos_pos_trivial)
   930 apply (simp add: zmod_zmult_zmult2 mod_pos_pos_trivial)
   930 apply (rule mod_pos_pos_trivial)
   931 apply (rule mod_pos_pos_trivial)
   951                 if (0::int) \<le> number_of w  
   952                 if (0::int) \<le> number_of w  
   952                 then 2 * (number_of v mod number_of w) + 1     
   953                 then 2 * (number_of v mod number_of w) + 1     
   953                 else 2 * ((number_of v + (1::int)) mod number_of w) - 1   
   954                 else 2 * ((number_of v + (1::int)) mod number_of w) - 1   
   954            else 2 * (number_of v mod number_of w))"
   955            else 2 * (number_of v mod number_of w))"
   955 apply (simp only: zadd_assoc number_of_BIT)
   956 apply (simp only: zadd_assoc number_of_BIT)
   956 apply (simp del: bin_arith_extra_simps bin_rel_simps 
   957 apply (simp del: bin_arith_extra_simps bin_rel_simps arith_special
   957          add: zmod_zmult_zmult1 pos_zmod_mult_2 not_0_le_lemma neg_zmod_mult_2, simp)
   958          add: zmod_zmult_zmult1 pos_zmod_mult_2 not_0_le_lemma neg_zmod_mult_2
       
   959  neg_def) 
   958 done
   960 done
   959 
   961 
   960 
   962 
   961 
   963 
   962 (** Quotients of signs **)
   964 (** Quotients of signs **)
  1112   apply (subgoal_tac "0 < n")
  1114   apply (subgoal_tac "0 < n")
  1113    prefer 2
  1115    prefer 2
  1114    apply (blast intro: order_less_trans)
  1116    apply (blast intro: order_less_trans)
  1115   apply (simp add: zero_less_mult_iff)
  1117   apply (simp add: zero_less_mult_iff)
  1116   apply (subgoal_tac "n * k < n * 1")
  1118   apply (subgoal_tac "n * k < n * 1")
  1117    apply (drule zmult_zless_cancel1 [THEN iffD1], auto)
  1119    apply (drule mult_less_cancel_left [THEN iffD1], auto)
  1118   done
  1120   done
  1119 
  1121 
  1120 lemma int_dvd_iff: "(int m dvd z) = (m dvd nat (abs z))"
  1122 lemma int_dvd_iff: "(int m dvd z) = (m dvd nat (abs z))"
  1121   apply (auto simp add: dvd_def nat_abs_mult_distrib)
  1123   apply (auto simp add: dvd_def nat_abs_mult_distrib)
  1122   apply (auto simp add: nat_eq_iff abs_if split add: split_if_asm)
  1124   apply (auto simp add: nat_eq_iff abs_if split add: split_if_asm)