src/HOL/Number_Theory/Gauss.thy
changeset 67399 eab6ce8368fa
parent 67118 ccab07d1196c
child 68707 5b269897df9d
equal deleted inserted replaced
67398:5eb932e604a2 67399:eab6ce8368fa
   167     by (auto simp add: B_def inj_on_def A_def) metis
   167     by (auto simp add: B_def inj_on_def A_def) metis
   168 qed
   168 qed
   169 
   169 
   170 lemma inj_on_pminusx_E: "inj_on (\<lambda>x. p - x) E"
   170 lemma inj_on_pminusx_E: "inj_on (\<lambda>x. p - x) E"
   171   apply (auto simp add: E_def C_def B_def A_def)
   171   apply (auto simp add: E_def C_def B_def A_def)
   172   apply (rule inj_on_inverseI [where g = "op - (int p)"])
   172   apply (rule inj_on_inverseI [where g = "(-) (int p)"])
   173   apply auto
   173   apply auto
   174   done
   174   done
   175 
   175 
   176 lemma nonzero_mod_p: "0 < x \<Longrightarrow> x < int p \<Longrightarrow> [x \<noteq> 0](mod p)"
   176 lemma nonzero_mod_p: "0 < x \<Longrightarrow> x < int p \<Longrightarrow> [x \<noteq> 0](mod p)"
   177   for x :: int
   177   for x :: int
   313 lemma prod_D_F_eq_prod_A: "prod id D * prod id F = prod id A"
   313 lemma prod_D_F_eq_prod_A: "prod id D * prod id F = prod id A"
   314   by (metis F_D_disj F_Un_D_eq_A Int_commute Un_commute finite_D finite_F prod.union_disjoint)
   314   by (metis F_D_disj F_Un_D_eq_A Int_commute Un_commute finite_D finite_F prod.union_disjoint)
   315 
   315 
   316 lemma prod_F_zcong: "[prod id F = ((-1) ^ (card E)) * prod id E] (mod p)"
   316 lemma prod_F_zcong: "[prod id F = ((-1) ^ (card E)) * prod id E] (mod p)"
   317 proof -
   317 proof -
   318   have FE: "prod id F = prod (op - p) E"
   318   have FE: "prod id F = prod ((-) p) E"
   319     apply (auto simp add: F_def)
   319     apply (auto simp add: F_def)
   320     apply (insert finite_E inj_on_pminusx_E)
   320     apply (insert finite_E inj_on_pminusx_E)
   321     apply (drule prod.reindex)
   321     apply (drule prod.reindex)
   322     apply auto
   322     apply auto
   323     done
   323     done
   324   then have "\<forall>x \<in> E. [(p-x) mod p = - x](mod p)"
   324   then have "\<forall>x \<in> E. [(p-x) mod p = - x](mod p)"
   325     by (metis cong_def minus_mod_self1 mod_mod_trivial)
   325     by (metis cong_def minus_mod_self1 mod_mod_trivial)
   326   then have "[prod ((\<lambda>x. x mod p) \<circ> (op - p)) E = prod (uminus) E](mod p)"
   326   then have "[prod ((\<lambda>x. x mod p) \<circ> ((-) p)) E = prod (uminus) E](mod p)"
   327     using finite_E p_ge_2 cong_prod [of E "(\<lambda>x. x mod p) \<circ> (op - p)" uminus p]
   327     using finite_E p_ge_2 cong_prod [of E "(\<lambda>x. x mod p) \<circ> ((-) p)" uminus p]
   328     by auto
   328     by auto
   329   then have two: "[prod id F = prod (uminus) E](mod p)"
   329   then have two: "[prod id F = prod (uminus) E](mod p)"
   330     by (metis FE cong_cong_mod_int cong_refl cong_prod minus_mod_self1)
   330     by (metis FE cong_cong_mod_int cong_refl cong_prod minus_mod_self1)
   331   have "prod uminus E = (-1) ^ card E * prod id E"
   331   have "prod uminus E = (-1) ^ card E * prod id E"
   332     using finite_E by (induct set: finite) auto
   332     using finite_E by (induct set: finite) auto