174 Goal "0<k ==> ALL m. m <= n --> (m div k) <= (n div k)"; |
174 Goal "0<k ==> ALL m. m <= n --> (m div k) <= (n div k)"; |
175 by (res_inst_tac [("n","n")] less_induct 1); |
175 by (res_inst_tac [("n","n")] less_induct 1); |
176 by (Clarify_tac 1); |
176 by (Clarify_tac 1); |
177 by (case_tac "n<k" 1); |
177 by (case_tac "n<k" 1); |
178 (* 1 case n<k *) |
178 (* 1 case n<k *) |
179 by (subgoal_tac "m<k" 1); |
|
180 by (asm_simp_tac (simpset() addsimps [div_less]) 1); |
179 by (asm_simp_tac (simpset() addsimps [div_less]) 1); |
181 by (trans_tac 1); |
|
182 (* 2 case n >= k *) |
180 (* 2 case n >= k *) |
183 by (case_tac "m<k" 1); |
181 by (case_tac "m<k" 1); |
184 (* 2.1 case m<k *) |
182 (* 2.1 case m<k *) |
185 by (asm_simp_tac (simpset() addsimps [div_less]) 1); |
183 by (asm_simp_tac (simpset() addsimps [div_less]) 1); |
186 (* 2.2 case m>=k *) |
184 (* 2.2 case m>=k *) |
189 |
187 |
190 |
188 |
191 (* Antimonotonicity of div in second argument *) |
189 (* Antimonotonicity of div in second argument *) |
192 Goal "[| 0<m; m<=n |] ==> (k div n) <= (k div m)"; |
190 Goal "[| 0<m; m<=n |] ==> (k div n) <= (k div m)"; |
193 by (subgoal_tac "0<n" 1); |
191 by (subgoal_tac "0<n" 1); |
194 by (trans_tac 2); |
192 by (Simp_tac 2); |
195 by (res_inst_tac [("n","k")] less_induct 1); |
193 by (res_inst_tac [("n","k")] less_induct 1); |
196 by (Simp_tac 1); |
194 by (Simp_tac 1); |
197 by (rename_tac "k" 1); |
195 by (rename_tac "k" 1); |
198 by (case_tac "k<n" 1); |
196 by (case_tac "k<n" 1); |
199 by (asm_simp_tac (simpset() addsimps [div_less]) 1); |
197 by (asm_simp_tac (simpset() addsimps [div_less]) 1); |
200 by (subgoal_tac "~(k<m)" 1); |
198 by (subgoal_tac "~(k<m)" 1); |
201 by (trans_tac 2); |
199 by (Simp_tac 2); |
202 by (asm_simp_tac (simpset() addsimps [div_geq]) 1); |
200 by (asm_simp_tac (simpset() addsimps [div_geq]) 1); |
203 by (subgoal_tac "(k-n) div n <= (k-m) div n" 1); |
201 by (subgoal_tac "(k-n) div n <= (k-m) div n" 1); |
204 by (REPEAT (eresolve_tac [div_le_mono,diff_le_mono2] 2)); |
202 by (REPEAT (eresolve_tac [div_le_mono,diff_le_mono2] 2)); |
205 by (rtac le_trans 1); |
203 by (rtac le_trans 1); |
206 by (Asm_simp_tac 1); |
204 by (Asm_simp_tac 1); |
209 |
207 |
210 Goal "0<n ==> m div n <= m"; |
208 Goal "0<n ==> m div n <= m"; |
211 by (subgoal_tac "m div n <= m div 1" 1); |
209 by (subgoal_tac "m div n <= m div 1" 1); |
212 by (Asm_full_simp_tac 1); |
210 by (Asm_full_simp_tac 1); |
213 by (rtac div_le_mono2 1); |
211 by (rtac div_le_mono2 1); |
214 by (ALLGOALS trans_tac); |
212 by (ALLGOALS Simp_tac); |
215 qed "div_le_dividend"; |
213 qed "div_le_dividend"; |
216 Addsimps [div_le_dividend]; |
214 Addsimps [div_le_dividend]; |
217 |
215 |
218 (* Similar for "less than" *) |
216 (* Similar for "less than" *) |
219 Goal "1<n ==> (0 < m) --> (m div n < m)"; |
217 Goal "1<n ==> (0 < m) --> (m div n < m)"; |
221 by (Simp_tac 1); |
219 by (Simp_tac 1); |
222 by (rename_tac "m" 1); |
220 by (rename_tac "m" 1); |
223 by (case_tac "m<n" 1); |
221 by (case_tac "m<n" 1); |
224 by (asm_full_simp_tac (simpset() addsimps [div_less]) 1); |
222 by (asm_full_simp_tac (simpset() addsimps [div_less]) 1); |
225 by (subgoal_tac "0<n" 1); |
223 by (subgoal_tac "0<n" 1); |
226 by (trans_tac 2); |
224 by (Simp_tac 2); |
227 by (asm_full_simp_tac (simpset() addsimps [div_geq]) 1); |
225 by (asm_full_simp_tac (simpset() addsimps [div_geq]) 1); |
228 by (case_tac "n<m" 1); |
226 by (case_tac "n<m" 1); |
229 by (subgoal_tac "(m-n) div n < (m-n)" 1); |
227 by (subgoal_tac "(m-n) div n < (m-n)" 1); |
230 by (REPEAT (ares_tac [impI,less_trans_Suc] 1)); |
228 by (REPEAT (ares_tac [impI,less_trans_Suc] 1)); |
231 by (asm_full_simp_tac (simpset() addsimps [diff_less]) 1); |
229 by (asm_full_simp_tac (simpset() addsimps [diff_less]) 1); |
232 by (asm_full_simp_tac (simpset() addsimps [diff_less]) 1); |
230 by (asm_full_simp_tac (simpset() addsimps [diff_less]) 1); |
233 (* case n=m *) |
231 (* case n=m *) |
234 by (subgoal_tac "m=n" 1); |
232 by (subgoal_tac "m=n" 1); |
235 by (trans_tac 2); |
233 by (Simp_tac 2); |
236 by (asm_simp_tac (simpset() addsimps [div_less]) 1); |
234 by (asm_simp_tac (simpset() addsimps [div_less]) 1); |
237 qed_spec_mp "div_less_dividend"; |
235 qed_spec_mp "div_less_dividend"; |
238 Addsimps [div_less_dividend]; |
236 Addsimps [div_less_dividend]; |
239 |
237 |
240 (*** Further facts about mod (mainly for the mutilated chess board ***) |
238 (*** Further facts about mod (mainly for the mutilated chess board ***) |