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