23 where |
23 where |
24 empty [simp]: "{} \<in> RsetR m" |
24 empty [simp]: "{} \<in> RsetR m" |
25 | insert: "A \<in> RsetR m ==> zgcd a m = 1 ==> |
25 | insert: "A \<in> RsetR m ==> zgcd a m = 1 ==> |
26 \<forall>a'. a' \<in> A --> \<not> zcong a a' m ==> insert a A \<in> RsetR m" |
26 \<forall>a'. a' \<in> A --> \<not> zcong a a' m ==> insert a A \<in> RsetR m" |
27 |
27 |
28 consts |
28 fun |
29 BnorRset :: "int * int => int set" |
29 BnorRset :: "int \<Rightarrow> int => int set" |
30 |
30 where |
31 recdef BnorRset |
31 "BnorRset a m = |
32 "measure ((\<lambda>(a, m). nat a) :: int * int => nat)" |
|
33 "BnorRset (a, m) = |
|
34 (if 0 < a then |
32 (if 0 < a then |
35 let na = BnorRset (a - 1, m) |
33 let na = BnorRset (a - 1) m |
36 in (if zgcd a m = 1 then insert a na else na) |
34 in (if zgcd a m = 1 then insert a na else na) |
37 else {})" |
35 else {})" |
38 |
36 |
39 definition |
37 definition |
40 norRRset :: "int => int set" where |
38 norRRset :: "int => int set" where |
41 "norRRset m = BnorRset (m - 1, m)" |
39 "norRRset m = BnorRset (m - 1) m" |
42 |
40 |
43 definition |
41 definition |
44 noXRRset :: "int => int => int set" where |
42 noXRRset :: "int => int => int set" where |
45 "noXRRset m x = (\<lambda>a. a * x) ` norRRset m" |
43 "noXRRset m x = (\<lambda>a. a * x) ` norRRset m" |
46 |
44 |
72 |
70 |
73 declare BnorRset.simps [simp del] |
71 declare BnorRset.simps [simp del] |
74 |
72 |
75 lemma BnorRset_induct: |
73 lemma BnorRset_induct: |
76 assumes "!!a m. P {} a m" |
74 assumes "!!a m. P {} a m" |
77 and "!!a m. 0 < (a::int) ==> P (BnorRset (a - 1, m::int)) (a - 1) m |
75 and "!!a m :: int. 0 < a ==> P (BnorRset (a - 1) m) (a - 1) m |
78 ==> P (BnorRset(a,m)) a m" |
76 ==> P (BnorRset a m) a m" |
79 shows "P (BnorRset(u,v)) u v" |
77 shows "P (BnorRset u v) u v" |
80 apply (rule BnorRset.induct) |
78 apply (rule BnorRset.induct) |
81 apply safe |
79 apply (case_tac "0 < a") |
82 apply (case_tac [2] "0 < a") |
80 apply (rule_tac assms) |
83 apply (rule_tac [2] prems) |
|
84 apply simp_all |
81 apply simp_all |
85 apply (simp_all add: BnorRset.simps prems) |
82 apply (simp_all add: BnorRset.simps assms) |
86 done |
83 done |
87 |
84 |
88 lemma Bnor_mem_zle [rule_format]: "b \<in> BnorRset (a, m) \<longrightarrow> b \<le> a" |
85 lemma Bnor_mem_zle [rule_format]: "b \<in> BnorRset a m \<longrightarrow> b \<le> a" |
89 apply (induct a m rule: BnorRset_induct) |
86 apply (induct a m rule: BnorRset_induct) |
90 apply simp |
87 apply simp |
91 apply (subst BnorRset.simps) |
88 apply (subst BnorRset.simps) |
92 apply (unfold Let_def, auto) |
89 apply (unfold Let_def, auto) |
93 done |
90 done |
94 |
91 |
95 lemma Bnor_mem_zle_swap: "a < b ==> b \<notin> BnorRset (a, m)" |
92 lemma Bnor_mem_zle_swap: "a < b ==> b \<notin> BnorRset a m" |
96 by (auto dest: Bnor_mem_zle) |
93 by (auto dest: Bnor_mem_zle) |
97 |
94 |
98 lemma Bnor_mem_zg [rule_format]: "b \<in> BnorRset (a, m) --> 0 < b" |
95 lemma Bnor_mem_zg [rule_format]: "b \<in> BnorRset a m --> 0 < b" |
99 apply (induct a m rule: BnorRset_induct) |
96 apply (induct a m rule: BnorRset_induct) |
100 prefer 2 |
97 prefer 2 |
101 apply (subst BnorRset.simps) |
98 apply (subst BnorRset.simps) |
102 apply (unfold Let_def, auto) |
99 apply (unfold Let_def, auto) |
103 done |
100 done |
104 |
101 |
105 lemma Bnor_mem_if [rule_format]: |
102 lemma Bnor_mem_if [rule_format]: |
106 "zgcd b m = 1 --> 0 < b --> b \<le> a --> b \<in> BnorRset (a, m)" |
103 "zgcd b m = 1 --> 0 < b --> b \<le> a --> b \<in> BnorRset a m" |
107 apply (induct a m rule: BnorRset.induct, auto) |
104 apply (induct a m rule: BnorRset.induct, auto) |
108 apply (subst BnorRset.simps) |
105 apply (subst BnorRset.simps) |
109 defer |
106 defer |
110 apply (subst BnorRset.simps) |
107 apply (subst BnorRset.simps) |
111 apply (unfold Let_def, auto) |
108 apply (unfold Let_def, auto) |
112 done |
109 done |
113 |
110 |
114 lemma Bnor_in_RsetR [rule_format]: "a < m --> BnorRset (a, m) \<in> RsetR m" |
111 lemma Bnor_in_RsetR [rule_format]: "a < m --> BnorRset a m \<in> RsetR m" |
115 apply (induct a m rule: BnorRset_induct, simp) |
112 apply (induct a m rule: BnorRset_induct, simp) |
116 apply (subst BnorRset.simps) |
113 apply (subst BnorRset.simps) |
117 apply (unfold Let_def, auto) |
114 apply (unfold Let_def, auto) |
118 apply (rule RsetR.insert) |
115 apply (rule RsetR.insert) |
119 apply (rule_tac [3] allI) |
116 apply (rule_tac [3] allI) |
122 apply (subgoal_tac [6] "a' \<le> a - 1") |
119 apply (subgoal_tac [6] "a' \<le> a - 1") |
123 apply (rule_tac [7] Bnor_mem_zle) |
120 apply (rule_tac [7] Bnor_mem_zle) |
124 apply (rule_tac [5] Bnor_mem_zg, auto) |
121 apply (rule_tac [5] Bnor_mem_zg, auto) |
125 done |
122 done |
126 |
123 |
127 lemma Bnor_fin: "finite (BnorRset (a, m))" |
124 lemma Bnor_fin: "finite (BnorRset a m)" |
128 apply (induct a m rule: BnorRset_induct) |
125 apply (induct a m rule: BnorRset_induct) |
129 prefer 2 |
126 prefer 2 |
130 apply (subst BnorRset.simps) |
127 apply (subst BnorRset.simps) |
131 apply (unfold Let_def, auto) |
128 apply (unfold Let_def, auto) |
132 done |
129 done |
256 |
253 |
257 lemma Bnor_prod_power_aux: "a \<notin> A ==> inj f ==> f a \<notin> f ` A" |
254 lemma Bnor_prod_power_aux: "a \<notin> A ==> inj f ==> f a \<notin> f ` A" |
258 by (unfold inj_on_def, auto) |
255 by (unfold inj_on_def, auto) |
259 |
256 |
260 lemma Bnor_prod_power [rule_format]: |
257 lemma Bnor_prod_power [rule_format]: |
261 "x \<noteq> 0 ==> a < m --> \<Prod>((\<lambda>a. a * x) ` BnorRset (a, m)) = |
258 "x \<noteq> 0 ==> a < m --> \<Prod>((\<lambda>a. a * x) ` BnorRset a m) = |
262 \<Prod>(BnorRset(a, m)) * x^card (BnorRset (a, m))" |
259 \<Prod>(BnorRset a m) * x^card (BnorRset a m)" |
263 apply (induct a m rule: BnorRset_induct) |
260 apply (induct a m rule: BnorRset_induct) |
264 prefer 2 |
261 prefer 2 |
265 apply (simplesubst BnorRset.simps) --{*multiple redexes*} |
262 apply (simplesubst BnorRset.simps) --{*multiple redexes*} |
266 apply (unfold Let_def, auto) |
263 apply (unfold Let_def, auto) |
267 apply (simp add: Bnor_fin Bnor_mem_zle_swap) |
264 apply (simp add: Bnor_fin Bnor_mem_zle_swap) |
282 apply (subgoal_tac [2] "a \<notin> A \<and> b \<notin> B \<and> finite A \<and> finite B") |
279 apply (subgoal_tac [2] "a \<notin> A \<and> b \<notin> B \<and> finite A \<and> finite B") |
283 apply (auto intro: fin_bijRl fin_bijRr zcong_zmult) |
280 apply (auto intro: fin_bijRl fin_bijRr zcong_zmult) |
284 done |
281 done |
285 |
282 |
286 lemma Bnor_prod_zgcd [rule_format]: |
283 lemma Bnor_prod_zgcd [rule_format]: |
287 "a < m --> zgcd (\<Prod>(BnorRset(a, m))) m = 1" |
284 "a < m --> zgcd (\<Prod>(BnorRset a m)) m = 1" |
288 apply (induct a m rule: BnorRset_induct) |
285 apply (induct a m rule: BnorRset_induct) |
289 prefer 2 |
286 prefer 2 |
290 apply (subst BnorRset.simps) |
287 apply (subst BnorRset.simps) |
291 apply (unfold Let_def, auto) |
288 apply (unfold Let_def, auto) |
292 apply (simp add: Bnor_fin Bnor_mem_zle_swap) |
289 apply (simp add: Bnor_fin Bnor_mem_zle_swap) |
297 "0 < m ==> zgcd x m = 1 ==> [x^(phi m) = 1] (mod m)" |
294 "0 < m ==> zgcd x m = 1 ==> [x^(phi m) = 1] (mod m)" |
298 apply (unfold norRRset_def phi_def) |
295 apply (unfold norRRset_def phi_def) |
299 apply (case_tac "x = 0") |
296 apply (case_tac "x = 0") |
300 apply (case_tac [2] "m = 1") |
297 apply (case_tac [2] "m = 1") |
301 apply (rule_tac [3] iffD1) |
298 apply (rule_tac [3] iffD1) |
302 apply (rule_tac [3] k = "\<Prod>(BnorRset(m - 1, m))" |
299 apply (rule_tac [3] k = "\<Prod>(BnorRset (m - 1) m)" |
303 in zcong_cancel2) |
300 in zcong_cancel2) |
304 prefer 5 |
301 prefer 5 |
305 apply (subst Bnor_prod_power [symmetric]) |
302 apply (subst Bnor_prod_power [symmetric]) |
306 apply (rule_tac [7] Bnor_prod_zgcd, simp_all) |
303 apply (rule_tac [7] Bnor_prod_zgcd, simp_all) |
307 apply (rule bijzcong_zcong_prod) |
304 apply (rule bijzcong_zcong_prod) |
308 apply (fold norRRset_def noXRRset_def) |
305 apply (fold norRRset_def, fold noXRRset_def) |
309 apply (subst RRset2norRR_eq_norR [symmetric]) |
306 apply (subst RRset2norRR_eq_norR [symmetric]) |
310 apply (rule_tac [3] inj_func_bijR, auto) |
307 apply (rule_tac [3] inj_func_bijR, auto) |
311 apply (unfold zcongm_def) |
308 apply (unfold zcongm_def) |
312 apply (rule_tac [2] RRset2norRR_correct1) |
309 apply (rule_tac [2] RRset2norRR_correct1) |
313 apply (rule_tac [5] RRset2norRR_inj) |
310 apply (rule_tac [5] RRset2norRR_inj) |
317 apply (rule finite_imageI) |
314 apply (rule finite_imageI) |
318 apply (rule Bnor_fin) |
315 apply (rule Bnor_fin) |
319 done |
316 done |
320 |
317 |
321 lemma Bnor_prime: |
318 lemma Bnor_prime: |
322 "\<lbrakk> zprime p; a < p \<rbrakk> \<Longrightarrow> card (BnorRset (a, p)) = nat a" |
319 "\<lbrakk> zprime p; a < p \<rbrakk> \<Longrightarrow> card (BnorRset a p) = nat a" |
323 apply (induct a p rule: BnorRset.induct) |
320 apply (induct a p rule: BnorRset.induct) |
324 apply (subst BnorRset.simps) |
321 apply (subst BnorRset.simps) |
325 apply (unfold Let_def, auto simp add:zless_zprime_imp_zrelprime) |
322 apply (unfold Let_def, auto simp add:zless_zprime_imp_zrelprime) |
326 apply (subgoal_tac "finite (BnorRset (a - 1,m))") |
323 apply (subgoal_tac "finite (BnorRset (a - 1) m)") |
327 apply (subgoal_tac "a ~: BnorRset (a - 1,m)") |
324 apply (subgoal_tac "a ~: BnorRset (a - 1) m") |
328 apply (auto simp add: card_insert_disjoint Suc_nat_eq_nat_zadd1) |
325 apply (auto simp add: card_insert_disjoint Suc_nat_eq_nat_zadd1) |
329 apply (frule Bnor_mem_zle, arith) |
326 apply (frule Bnor_mem_zle, arith) |
330 apply (frule Bnor_fin) |
327 apply (frule Bnor_fin) |
331 done |
328 done |
332 |
329 |