src/HOL/NumberTheory/IntPrimes.ML
changeset 10198 2b255b772585
parent 10142 d1d61d13e461
child 10658 b9d43a2add79
equal deleted inserted replaced
10197:4ea3ee8de019 10198:2b255b772585
   144 by (asm_simp_tac (simpset() addsimps [zdvd_zadd, zdvd_zmult2]) 2);
   144 by (asm_simp_tac (simpset() addsimps [zdvd_zadd, zdvd_zmult2]) 2);
   145 by (asm_full_simp_tac (simpset() addsimps [zmod_zdiv_equality RS sym]) 1);
   145 by (asm_full_simp_tac (simpset() addsimps [zmod_zdiv_equality RS sym]) 1);
   146 qed "zdvd_zmod_imp_zdvd";
   146 qed "zdvd_zmod_imp_zdvd";
   147 
   147 
   148 Goalw [dvd_def] "(k dvd n) = (n mod (k::int) = #0)";
   148 Goalw [dvd_def] "(k dvd n) = (n mod (k::int) = #0)";
   149 by (zdiv_undefined_case_tac "k=#0" 1);
   149 by (auto_tac (claset(), simpset() addsimps [zmod_zmult_self2]));  
   150 by Safe_tac;
       
   151 by (res_inst_tac [("x","n div k")] exI 2);
       
   152 by (rtac trans 2);
       
   153 by (res_inst_tac [("b","k")] zmod_zdiv_equality 2);
       
   154 by (ALLGOALS Asm_simp_tac);
       
   155 qed "zdvd_iff_zmod_eq_0";
   150 qed "zdvd_iff_zmod_eq_0";
   156 
   151 
   157 Goal "[| ~k<#0; k~=#0 |] ==> #0<(k::int)";
   152 Goal "[| ~k<#0; k~=#0 |] ==> #0<(k::int)";
   158 by (arith_tac 1);
   153 by (arith_tac 1);
   159 val lemma = result();
   154 val lemma = result();
   547 by Auto_tac;  
   542 by Auto_tac;  
   548 qed "zcong_zless_imp_eq";
   543 qed "zcong_zless_imp_eq";
   549 
   544 
   550 Goal "[| p:zprime; #0<a; a<p; [a*a = #1](mod p) |] ==> a = #1 | a = p-#1";
   545 Goal "[| p:zprime; #0<a; a<p; [a*a = #1](mod p) |] ==> a = #1 | a = p-#1";
   551 by (cut_inst_tac [("p","p"),("a","a")] zcong_square 1);
   546 by (cut_inst_tac [("p","p"),("a","a")] zcong_square 1);
   552 by Safe_tac;
   547 by (full_simp_tac (simpset() addsimps [zprime_def]) 1); 
   553 by (res_inst_tac [("Pa","a=p-#1")] swap 2);
   548 by (auto_tac (claset() addIs [zcong_zless_imp_eq], simpset())); 
   554 by (rtac zcong_zless_imp_eq 1);
       
   555 by (rtac zcong_zless_imp_eq 7);
       
   556 by (rewtac zprime_def);
       
   557 by Auto_tac;
       
   558 qed "zcong_square_zless";
   549 qed "zcong_square_zless";
   559 
   550 
   560 Goalw [zcong_def] "[| #0<a; a<m; #0<b; b<a |] ==> ~[a = b] (mod m) ";
   551 Goalw [zcong_def] "[| #0<a; a<m; #0<b; b<a |] ==> ~[a = b] (mod m) ";
   561 by (rtac zdvd_not_zless 1);
   552 by (rtac zdvd_not_zless 1);
   562 by Auto_tac;
   553 by Auto_tac;