src/HOL/Divides.thy
changeset 62390 842917225d56
parent 61944 5d06ecfdb472
child 62597 b3f2b8c906a6
equal deleted inserted replaced
62380:29800666e526 62390:842917225d56
  1000 next
  1000 next
  1001   fix m n q :: nat
  1001   fix m n q :: nat
  1002   assume "m \<noteq> 0"
  1002   assume "m \<noteq> 0"
  1003   hence "\<And>a b. divmod_nat_rel n q (a, b) \<Longrightarrow> divmod_nat_rel (m * n) (m * q) (a, m * b)"
  1003   hence "\<And>a b. divmod_nat_rel n q (a, b) \<Longrightarrow> divmod_nat_rel (m * n) (m * q) (a, m * b)"
  1004     unfolding divmod_nat_rel_def
  1004     unfolding divmod_nat_rel_def
  1005     by (auto split: split_if_asm, simp_all add: algebra_simps)
  1005     by (auto split: if_split_asm, simp_all add: algebra_simps)
  1006   moreover from divmod_nat_rel have "divmod_nat_rel n q (n div q, n mod q)" .
  1006   moreover from divmod_nat_rel have "divmod_nat_rel n q (n div q, n mod q)" .
  1007   ultimately have "divmod_nat_rel (m * n) (m * q) (n div q, m * (n mod q))" .
  1007   ultimately have "divmod_nat_rel (m * n) (m * q) (n div q, m * (n mod q))" .
  1008   thus "(m * n) div (m * q) = n div q" by (rule div_nat_unique)
  1008   thus "(m * n) div (m * q) = n div q" by (rule div_nat_unique)
  1009 next
  1009 next
  1010   fix n :: nat show "n div 0 = 0"
  1010   fix n :: nat show "n div 0 = 0"
  1658   "b * q' + r' \<le> b*q + r \<Longrightarrow> r \<le> 0 \<Longrightarrow> b < r \<Longrightarrow> b < r' \<Longrightarrow> q \<le> (q'::int)"
  1658   "b * q' + r' \<le> b*q + r \<Longrightarrow> r \<le> 0 \<Longrightarrow> b < r \<Longrightarrow> b < r' \<Longrightarrow> q \<le> (q'::int)"
  1659   by (rule_tac b = "-b" and r = "-r'" and r' = "-r" in unique_quotient_lemma) auto
  1659   by (rule_tac b = "-b" and r = "-r'" and r' = "-r" in unique_quotient_lemma) auto
  1660 
  1660 
  1661 lemma unique_quotient:
  1661 lemma unique_quotient:
  1662   "divmod_int_rel a b (q, r) \<Longrightarrow> divmod_int_rel a b (q', r') \<Longrightarrow> q = q'"
  1662   "divmod_int_rel a b (q, r) \<Longrightarrow> divmod_int_rel a b (q', r') \<Longrightarrow> q = q'"
  1663 apply (simp add: divmod_int_rel_def linorder_neq_iff split: split_if_asm)
  1663 apply (simp add: divmod_int_rel_def linorder_neq_iff split: if_split_asm)
  1664 apply (blast intro: order_antisym
  1664 apply (blast intro: order_antisym
  1665              dest: order_eq_refl [THEN unique_quotient_lemma]
  1665              dest: order_eq_refl [THEN unique_quotient_lemma]
  1666              order_eq_refl [THEN unique_quotient_lemma_neg] sym)+
  1666              order_eq_refl [THEN unique_quotient_lemma_neg] sym)+
  1667 done
  1667 done
  1668 
  1668 
  2070 
  2070 
  2071 lemma zmult2_lemma: "[| divmod_int_rel a b (q, r); 0 < c |]
  2071 lemma zmult2_lemma: "[| divmod_int_rel a b (q, r); 0 < c |]
  2072       ==> divmod_int_rel a (b * c) (q div c, b*(q mod c) + r)"
  2072       ==> divmod_int_rel a (b * c) (q div c, b*(q mod c) + r)"
  2073 by (auto simp add: mult.assoc divmod_int_rel_def linorder_neq_iff
  2073 by (auto simp add: mult.assoc divmod_int_rel_def linorder_neq_iff
  2074                    zero_less_mult_iff distrib_left [symmetric]
  2074                    zero_less_mult_iff distrib_left [symmetric]
  2075                    zmult2_lemma_aux1 zmult2_lemma_aux2 zmult2_lemma_aux3 zmult2_lemma_aux4 mult_less_0_iff split: split_if_asm)
  2075                    zmult2_lemma_aux1 zmult2_lemma_aux2 zmult2_lemma_aux3 zmult2_lemma_aux4 mult_less_0_iff split: if_split_asm)
  2076 
  2076 
  2077 lemma zdiv_zmult2_eq:
  2077 lemma zdiv_zmult2_eq:
  2078   fixes a b c :: int
  2078   fixes a b c :: int
  2079   shows "0 \<le> c \<Longrightarrow> a div (b * c) = (a div b) div c"
  2079   shows "0 \<le> c \<Longrightarrow> a div (b * c) = (a div b) div c"
  2080 apply (case_tac "b = 0", simp)
  2080 apply (case_tac "b = 0", simp)