equal
deleted
inserted
replaced
86 qed "gcd_recursion"; |
86 qed "gcd_recursion"; |
87 |
87 |
88 |
88 |
89 (*gcd(m,n) divides m and n. The conjunctions don't seem provable separately*) |
89 (*gcd(m,n) divides m and n. The conjunctions don't seem provable separately*) |
90 goal thy "(gcd(m,n) dvd m) & (gcd(m,n) dvd n)"; |
90 goal thy "(gcd(m,n) dvd m) & (gcd(m,n) dvd n)"; |
91 by (res_inst_tac [("v","m"),("v1.0","n")] gcd_induct 1); |
91 by (res_inst_tac [("u","m"),("v","n")] gcd_induct 1); |
92 by (case_tac "n=0" 1); |
92 by (case_tac "n=0" 1); |
93 by (ALLGOALS |
93 by (ALLGOALS |
94 (asm_simp_tac (!simpset addsimps [mod_less_divisor,zero_less_eq]))); |
94 (asm_simp_tac (!simpset addsimps [mod_less_divisor,zero_less_eq]))); |
95 by (blast_tac (!claset addDs [gcd_recursion]) 1); |
95 by (blast_tac (!claset addDs [gcd_recursion]) 1); |
96 qed "gcd_divides_both"; |
96 qed "gcd_divides_both"; |
110 |
110 |
111 |
111 |
112 (*Maximality: for all m,n,f naturals, |
112 (*Maximality: for all m,n,f naturals, |
113 if f divides m and f divides n then f divides gcd(m,n)*) |
113 if f divides m and f divides n then f divides gcd(m,n)*) |
114 goal thy "!!k. (f dvd m) & (f dvd n) --> f dvd gcd(m,n)"; |
114 goal thy "!!k. (f dvd m) & (f dvd n) --> f dvd gcd(m,n)"; |
115 by (res_inst_tac [("v","m"),("v1.0","n")] gcd_induct 1); |
115 by (res_inst_tac [("u","m"),("v","n")] gcd_induct 1); |
116 by (case_tac "n=0" 1); |
116 by (case_tac "n=0" 1); |
117 by (ALLGOALS |
117 by (ALLGOALS |
118 (asm_simp_tac (!simpset addsimps [dvd_mod, mod_less_divisor, |
118 (asm_simp_tac (!simpset addsimps [dvd_mod, mod_less_divisor, |
119 zero_less_eq]))); |
119 zero_less_eq]))); |
120 qed_spec_mp "gcd_greatest"; |
120 qed_spec_mp "gcd_greatest"; |