162 ALLGOALS(asm_simp_tac (!simpset addsimps add_ac))]); |
162 ALLGOALS(asm_simp_tac (!simpset addsimps add_ac))]); |
163 |
163 |
164 (*Associative law for multiplication*) |
164 (*Associative law for multiplication*) |
165 qed_goal "mult_assoc" Arith.thy "(m * n) * k = m * ((n * k)::nat)" |
165 qed_goal "mult_assoc" Arith.thy "(m * n) * k = m * ((n * k)::nat)" |
166 (fn _ => [nat_ind_tac "m" 1, |
166 (fn _ => [nat_ind_tac "m" 1, |
167 ALLGOALS (asm_simp_tac (!simpset addsimps [add_mult_distrib]))]); |
167 ALLGOALS (asm_simp_tac (!simpset addsimps [add_mult_distrib]))]); |
168 |
168 |
169 qed_goal "mult_left_commute" Arith.thy "x*(y*z) = y*((x*z)::nat)" |
169 qed_goal "mult_left_commute" Arith.thy "x*(y*z) = y*((x*z)::nat)" |
170 (fn _ => [rtac trans 1, rtac mult_commute 1, rtac trans 1, |
170 (fn _ => [rtac trans 1, rtac mult_commute 1, rtac trans 1, |
171 rtac mult_assoc 1, rtac (mult_commute RS arg_cong) 1]); |
171 rtac mult_assoc 1, rtac (mult_commute RS arg_cong) 1]); |
172 |
172 |
537 by (simp_tac (!simpset addsimps [mult_commute]) 1); |
537 by (simp_tac (!simpset addsimps [mult_commute]) 1); |
538 qed "mult_le_mono"; |
538 qed "mult_le_mono"; |
539 |
539 |
540 (*strict, in 1st argument; proof is by induction on k>0*) |
540 (*strict, in 1st argument; proof is by induction on k>0*) |
541 goal Arith.thy "!!i::nat. [| i<j; 0<k |] ==> k*i < k*j"; |
541 goal Arith.thy "!!i::nat. [| i<j; 0<k |] ==> k*i < k*j"; |
542 be zero_less_natE 1; |
542 by (etac zero_less_natE 1); |
543 by (Asm_simp_tac 1); |
543 by (Asm_simp_tac 1); |
544 by (nat_ind_tac "x" 1); |
544 by (nat_ind_tac "x" 1); |
545 by (ALLGOALS (asm_simp_tac (!simpset addsimps [add_less_mono]))); |
545 by (ALLGOALS (asm_simp_tac (!simpset addsimps [add_less_mono]))); |
546 qed "mult_less_mono2"; |
546 qed "mult_less_mono2"; |
547 |
547 |
562 (*Cancellation law for division*) |
562 (*Cancellation law for division*) |
563 goal Arith.thy "!!k. [| 0<n; 0<k |] ==> (k*m) div (k*n) = m div n"; |
563 goal Arith.thy "!!k. [| 0<n; 0<k |] ==> (k*m) div (k*n) = m div n"; |
564 by (res_inst_tac [("n","m")] less_induct 1); |
564 by (res_inst_tac [("n","m")] less_induct 1); |
565 by (case_tac "na<n" 1); |
565 by (case_tac "na<n" 1); |
566 by (asm_simp_tac (!simpset addsimps [div_less, zero_less_mult_iff, |
566 by (asm_simp_tac (!simpset addsimps [div_less, zero_less_mult_iff, |
567 mult_less_mono2]) 1); |
567 mult_less_mono2]) 1); |
568 by (subgoal_tac "~ k*na < k*n" 1); |
568 by (subgoal_tac "~ k*na < k*n" 1); |
569 by (asm_simp_tac |
569 by (asm_simp_tac |
570 (!simpset addsimps [zero_less_mult_iff, div_geq, |
570 (!simpset addsimps [zero_less_mult_iff, div_geq, |
571 diff_mult_distrib2 RS sym, diff_less]) 1); |
571 diff_mult_distrib2 RS sym, diff_less]) 1); |
572 by (asm_full_simp_tac (!simpset addsimps [not_less_iff_le, |
572 by (asm_full_simp_tac (!simpset addsimps [not_less_iff_le, |
573 le_refl RS mult_le_mono]) 1); |
573 le_refl RS mult_le_mono]) 1); |
574 qed "div_cancel"; |
574 qed "div_cancel"; |
575 |
575 |
576 goal Arith.thy "!!k. [| 0<n; 0<k |] ==> (k*m) mod (k*n) = k * (m mod n)"; |
576 goal Arith.thy "!!k. [| 0<n; 0<k |] ==> (k*m) mod (k*n) = k * (m mod n)"; |
577 by (res_inst_tac [("n","m")] less_induct 1); |
577 by (res_inst_tac [("n","m")] less_induct 1); |
578 by (case_tac "na<n" 1); |
578 by (case_tac "na<n" 1); |
579 by (asm_simp_tac (!simpset addsimps [mod_less, zero_less_mult_iff, |
579 by (asm_simp_tac (!simpset addsimps [mod_less, zero_less_mult_iff, |
580 mult_less_mono2]) 1); |
580 mult_less_mono2]) 1); |
581 by (subgoal_tac "~ k*na < k*n" 1); |
581 by (subgoal_tac "~ k*na < k*n" 1); |
582 by (asm_simp_tac |
582 by (asm_simp_tac |
583 (!simpset addsimps [zero_less_mult_iff, mod_geq, |
583 (!simpset addsimps [zero_less_mult_iff, mod_geq, |
584 diff_mult_distrib2 RS sym, diff_less]) 1); |
584 diff_mult_distrib2 RS sym, diff_less]) 1); |
585 by (asm_full_simp_tac (!simpset addsimps [not_less_iff_le, |
585 by (asm_full_simp_tac (!simpset addsimps [not_less_iff_le, |
586 le_refl RS mult_le_mono]) 1); |
586 le_refl RS mult_le_mono]) 1); |
587 qed "mult_mod_distrib"; |
587 qed "mult_mod_distrib"; |
588 |
588 |
589 |
589 |
590 (** Lemma for gcd **) |
590 (** Lemma for gcd **) |
591 |
591 |