src/HOL/ex/Primes.ML
changeset 3301 cdcc4d5602b6
parent 3270 4a3ab8d43451
child 3359 88cd6a2c6ebe
equal deleted inserted replaced
3300:4f5ffefa7799 3301:cdcc4d5602b6
    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";