src/HOL/Divides.thy
changeset 45607 16b4f5774621
parent 45530 0c4853bb77bf
child 46026 83caa4f4bd56
equal deleted inserted replaced
45606:b1e1508643b1 45607:16b4f5774621
  1140 by (simp add: Suc3_eq_add_3)
  1140 by (simp add: Suc3_eq_add_3)
  1141 
  1141 
  1142 lemma Suc_mod_eq_add3_mod: "(Suc (Suc (Suc m))) mod n = (3+m) mod n"
  1142 lemma Suc_mod_eq_add3_mod: "(Suc (Suc (Suc m))) mod n = (3+m) mod n"
  1143 by (simp add: Suc3_eq_add_3)
  1143 by (simp add: Suc3_eq_add_3)
  1144 
  1144 
  1145 lemmas Suc_div_eq_add3_div_number_of =
  1145 lemmas Suc_div_eq_add3_div_number_of [simp] = Suc_div_eq_add3_div [of _ "number_of v"] for v
  1146     Suc_div_eq_add3_div [of _ "number_of v", standard]
  1146 lemmas Suc_mod_eq_add3_mod_number_of [simp] = Suc_mod_eq_add3_mod [of _ "number_of v"] for v
  1147 declare Suc_div_eq_add3_div_number_of [simp]
       
  1148 
       
  1149 lemmas Suc_mod_eq_add3_mod_number_of =
       
  1150     Suc_mod_eq_add3_mod [of _ "number_of v", standard]
       
  1151 declare Suc_mod_eq_add3_mod_number_of [simp]
       
  1152 
  1147 
  1153 
  1148 
  1154 lemma Suc_times_mod_eq: "1<k ==> Suc (k * m) mod k = 1" 
  1149 lemma Suc_times_mod_eq: "1<k ==> Suc (k * m) mod k = 1" 
  1155 apply (induct "m")
  1150 apply (induct "m")
  1156 apply (simp_all add: mod_Suc)
  1151 apply (simp_all add: mod_Suc)
  1157 done
  1152 done
  1158 
  1153 
  1159 declare Suc_times_mod_eq [of "number_of w", standard, simp]
  1154 declare Suc_times_mod_eq [of "number_of w", simp] for w
  1160 
  1155 
  1161 lemma [simp]: "n div k \<le> (Suc n) div k"
  1156 lemma [simp]: "n div k \<le> (Suc n) div k"
  1162 by (simp add: div_le_mono) 
  1157 by (simp add: div_le_mono) 
  1163 
  1158 
  1164 lemma Suc_n_div_2_gt_zero [simp]: "(0::nat) < n ==> 0 < (n + 1) div 2"
  1159 lemma Suc_n_div_2_gt_zero [simp]: "(0::nat) < n ==> 0 < (n + 1) div 2"
  1448 lemma pos_mod_conj : "(0::int) < b ==> 0 \<le> a mod b & a mod b < b"
  1443 lemma pos_mod_conj : "(0::int) < b ==> 0 \<le> a mod b & a mod b < b"
  1449 apply (cut_tac a = a and b = b in divmod_int_correct)
  1444 apply (cut_tac a = a and b = b in divmod_int_correct)
  1450 apply (auto simp add: divmod_int_rel_def mod_int_def)
  1445 apply (auto simp add: divmod_int_rel_def mod_int_def)
  1451 done
  1446 done
  1452 
  1447 
  1453 lemmas pos_mod_sign  [simp] = pos_mod_conj [THEN conjunct1, standard]
  1448 lemmas pos_mod_sign [simp] = pos_mod_conj [THEN conjunct1]
  1454    and pos_mod_bound [simp] = pos_mod_conj [THEN conjunct2, standard]
  1449    and pos_mod_bound [simp] = pos_mod_conj [THEN conjunct2]
  1455 
  1450 
  1456 lemma neg_mod_conj : "b < (0::int) ==> a mod b \<le> 0 & b < a mod b"
  1451 lemma neg_mod_conj : "b < (0::int) ==> a mod b \<le> 0 & b < a mod b"
  1457 apply (cut_tac a = a and b = b in divmod_int_correct)
  1452 apply (cut_tac a = a and b = b in divmod_int_correct)
  1458 apply (auto simp add: divmod_int_rel_def div_int_def mod_int_def)
  1453 apply (auto simp add: divmod_int_rel_def div_int_def mod_int_def)
  1459 done
  1454 done
  1460 
  1455 
  1461 lemmas neg_mod_sign  [simp] = neg_mod_conj [THEN conjunct1, standard]
  1456 lemmas neg_mod_sign [simp] = neg_mod_conj [THEN conjunct1]
  1462    and neg_mod_bound [simp] = neg_mod_conj [THEN conjunct2, standard]
  1457    and neg_mod_bound [simp] = neg_mod_conj [THEN conjunct2]
  1463 
       
  1464 
  1458 
  1465 
  1459 
  1466 subsubsection{*General Properties of div and mod*}
  1460 subsubsection{*General Properties of div and mod*}
  1467 
  1461 
  1468 lemma divmod_int_rel_div_mod: "b \<noteq> 0 ==> divmod_int_rel a b (a div b, a mod b)"
  1462 lemma divmod_int_rel_div_mod: "b \<noteq> 0 ==> divmod_int_rel a b (a div b, a mod b)"
  1726   {* K (divmod_proc @{thm int_div_pos_eq} @{thm int_div_neg_eq}) *}
  1720   {* K (divmod_proc @{thm int_div_pos_eq} @{thm int_div_neg_eq}) *}
  1727 
  1721 
  1728 simproc_setup binary_int_mod ("number_of m mod number_of n :: int") =
  1722 simproc_setup binary_int_mod ("number_of m mod number_of n :: int") =
  1729   {* K (divmod_proc @{thm int_mod_pos_eq} @{thm int_mod_neg_eq}) *}
  1723   {* K (divmod_proc @{thm int_mod_pos_eq} @{thm int_mod_neg_eq}) *}
  1730 
  1724 
  1731 lemmas posDivAlg_eqn_number_of [simp] =
  1725 lemmas posDivAlg_eqn_number_of [simp] = posDivAlg_eqn [of "number_of v" "number_of w"] for v w
  1732     posDivAlg_eqn [of "number_of v" "number_of w", standard]
  1726 lemmas negDivAlg_eqn_number_of [simp] = negDivAlg_eqn [of "number_of v" "number_of w"] for v w
  1733 
       
  1734 lemmas negDivAlg_eqn_number_of [simp] =
       
  1735     negDivAlg_eqn [of "number_of v" "number_of w", standard]
       
  1736 
  1727 
  1737 
  1728 
  1738 text{*Special-case simplification *}
  1729 text{*Special-case simplification *}
  1739 
  1730 
  1740 lemma zmod_minus1_right [simp]: "a mod (-1::int) = 0"
  1731 lemma zmod_minus1_right [simp]: "a mod (-1::int) = 0"
  1747 by (cut_tac a = a and b = "-1" in zmod_zdiv_equality, auto)
  1738 by (cut_tac a = a and b = "-1" in zmod_zdiv_equality, auto)
  1748 
  1739 
  1749 (** The last remaining special cases for constant arithmetic:
  1740 (** The last remaining special cases for constant arithmetic:
  1750     1 div z and 1 mod z **)
  1741     1 div z and 1 mod z **)
  1751 
  1742 
  1752 lemmas div_pos_pos_1_number_of [simp] =
  1743 lemmas div_pos_pos_1_number_of [simp] = div_pos_pos [OF zero_less_one, of "number_of w"] for w
  1753     div_pos_pos [OF zero_less_one, of "number_of w", standard]
  1744 lemmas div_pos_neg_1_number_of [simp] = div_pos_neg [OF zero_less_one, of "number_of w"] for w
  1754 
  1745 lemmas mod_pos_pos_1_number_of [simp] = mod_pos_pos [OF zero_less_one, of "number_of w"] for w
  1755 lemmas div_pos_neg_1_number_of [simp] =
  1746 lemmas mod_pos_neg_1_number_of [simp] = mod_pos_neg [OF zero_less_one, of "number_of w"] for w
  1756     div_pos_neg [OF zero_less_one, of "number_of w", standard]
  1747 lemmas posDivAlg_eqn_1_number_of [simp] = posDivAlg_eqn [of concl: 1 "number_of w"] for w
  1757 
  1748 lemmas negDivAlg_eqn_1_number_of [simp] = negDivAlg_eqn [of concl: 1 "number_of w"] for w
  1758 lemmas mod_pos_pos_1_number_of [simp] =
       
  1759     mod_pos_pos [OF zero_less_one, of "number_of w", standard]
       
  1760 
       
  1761 lemmas mod_pos_neg_1_number_of [simp] =
       
  1762     mod_pos_neg [OF zero_less_one, of "number_of w", standard]
       
  1763 
       
  1764 
       
  1765 lemmas posDivAlg_eqn_1_number_of [simp] =
       
  1766     posDivAlg_eqn [of concl: 1 "number_of w", standard]
       
  1767 
       
  1768 lemmas negDivAlg_eqn_1_number_of [simp] =
       
  1769     negDivAlg_eqn [of concl: 1 "number_of w", standard]
       
  1770 
       
  1771 
  1749 
  1772 
  1750 
  1773 subsubsection{*Monotonicity in the First Argument (Dividend)*}
  1751 subsubsection{*Monotonicity in the First Argument (Dividend)*}
  1774 
  1752 
  1775 lemma zdiv_mono1: "[| a \<le> a';  0 < (b::int) |] ==> a div b \<le> a' div b"
  1753 lemma zdiv_mono1: "[| a \<le> a';  0 < (b::int) |] ==> a div b \<le> a' div b"
  2067 done
  2045 done
  2068 
  2046 
  2069 text {* Enable (lin)arith to deal with @{const div} and @{const mod}
  2047 text {* Enable (lin)arith to deal with @{const div} and @{const mod}
  2070   when these are applied to some constant that is of the form
  2048   when these are applied to some constant that is of the form
  2071   @{term "number_of k"}: *}
  2049   @{term "number_of k"}: *}
  2072 declare split_zdiv [of _ _ "number_of k", standard, arith_split]
  2050 declare split_zdiv [of _ _ "number_of k", arith_split] for k
  2073 declare split_zmod [of _ _ "number_of k", standard, arith_split]
  2051 declare split_zmod [of _ _ "number_of k", arith_split] for k
  2074 
  2052 
  2075 
  2053 
  2076 subsubsection{*Speeding up the Division Algorithm with Shifting*}
  2054 subsubsection{*Speeding up the Division Algorithm with Shifting*}
  2077 
  2055 
  2078 text{*computing div by shifting *}
  2056 text{*computing div by shifting *}
  2255 
  2233 
  2256 
  2234 
  2257 subsubsection {* The Divides Relation *}
  2235 subsubsection {* The Divides Relation *}
  2258 
  2236 
  2259 lemmas zdvd_iff_zmod_eq_0_number_of [simp] =
  2237 lemmas zdvd_iff_zmod_eq_0_number_of [simp] =
  2260   dvd_eq_mod_eq_0 [of "number_of x::int" "number_of y::int", standard]
  2238   dvd_eq_mod_eq_0 [of "number_of x" "number_of y"] for x y :: int
  2261 
  2239 
  2262 lemma zdvd_zmod: "f dvd m ==> f dvd (n::int) ==> f dvd m mod n"
  2240 lemma zdvd_zmod: "f dvd m ==> f dvd (n::int) ==> f dvd m mod n"
  2263   by (rule dvd_mod) (* TODO: remove *)
  2241   by (rule dvd_mod) (* TODO: remove *)
  2264 
  2242 
  2265 lemma zdvd_zmod_imp_zdvd: "k dvd m mod n ==> k dvd n ==> k dvd (m::int)"
  2243 lemma zdvd_zmod_imp_zdvd: "k dvd m mod n ==> k dvd n ==> k dvd (m::int)"
  2454      "Suc 0 mod number_of v' =  
  2432      "Suc 0 mod number_of v' =  
  2455         (if neg (number_of v' :: int) then Suc 0
  2433         (if neg (number_of v' :: int) then Suc 0
  2456          else nat (1 mod number_of v'))"
  2434          else nat (1 mod number_of v'))"
  2457 by (simp del: nat_numeral_1_eq_1 add: numeral_1_eq_Suc_0 [symmetric]) 
  2435 by (simp del: nat_numeral_1_eq_1 add: numeral_1_eq_Suc_0 [symmetric]) 
  2458 
  2436 
  2459 lemmas dvd_eq_mod_eq_0_number_of =
  2437 lemmas dvd_eq_mod_eq_0_number_of [simp] =
  2460   dvd_eq_mod_eq_0 [of "number_of x" "number_of y", standard]
  2438   dvd_eq_mod_eq_0 [of "number_of x" "number_of y"] for x y
  2461 
       
  2462 declare dvd_eq_mod_eq_0_number_of [simp]
       
  2463 
  2439 
  2464 
  2440 
  2465 subsubsection {* Nitpick *}
  2441 subsubsection {* Nitpick *}
  2466 
  2442 
  2467 lemma zmod_zdiv_equality':
  2443 lemma zmod_zdiv_equality':