equal
deleted
inserted
replaced
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 |