src/HOL/NumberTheory/Gauss.thy
changeset 27556 292098f2efdf
parent 26289 9d2c375e242b
child 30034 60f64f112174
equal deleted inserted replaced
27555:dfda3192dec2 27556:292098f2efdf
     3     Authors:    Jeremy Avigad, David Gray, and Adam Kramer)
     3     Authors:    Jeremy Avigad, David Gray, and Adam Kramer)
     4 *)
     4 *)
     5 
     5 
     6 header {* Gauss' Lemma *}
     6 header {* Gauss' Lemma *}
     7 
     7 
     8 theory Gauss imports Euler begin
     8 theory Gauss
       
     9 imports Euler
       
    10 begin
     9 
    11 
    10 locale GAUSS =
    12 locale GAUSS =
    11   fixes p :: "int"
    13   fixes p :: "int"
    12   fixes a :: "int"
    14   fixes a :: "int"
    13 
    15 
   282     by arith
   284     by arith
   283   finally show "p - StandardRes p (y * a) \<le> (p - 1) div 2"
   285   finally show "p - StandardRes p (y * a) \<le> (p - 1) div 2"
   284     using zless_add1_eq [of "p - StandardRes p (y * a)" "(p - 1) div 2"] by auto
   286     using zless_add1_eq [of "p - StandardRes p (y * a)" "(p - 1) div 2"] by auto
   285 qed
   287 qed
   286 
   288 
   287 lemma all_A_relprime: "\<forall>x \<in> A. zgcd(x, p) = 1"
   289 lemma all_A_relprime: "\<forall>x \<in> A. zgcd x p = 1"
   288   using p_prime p_minus_one_l by (auto simp add: A_def zless_zprime_imp_zrelprime)
   290   using p_prime p_minus_one_l by (auto simp add: A_def zless_zprime_imp_zrelprime)
   289 
   291 
   290 lemma A_prod_relprime: "zgcd((setprod id A),p) = 1"
   292 lemma A_prod_relprime: "zgcd (setprod id A) p = 1"
   291   using all_A_relprime finite_A by (simp add: all_relprime_prod_relprime)
   293   using all_A_relprime finite_A by (simp add: all_relprime_prod_relprime)
   292 
   294 
   293 
   295 
   294 subsection {* Relationships Between Gauss Sets *}
   296 subsection {* Relationships Between Gauss Sets *}
   295 
   297