1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| A.Asperti, C.Sacerdoti Coen, *)
8 (* ||A|| E.Tassi, S.Zacchiroli *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU Lesser General Public License Version 2.1 *)
13 (**************************************************************************)
15 set "baseuri" "cic:/matita/nat/fermat_little_theorem".
18 include "nat/permutation.ma".
20 theorem permut_mod: \forall p,a:nat. prime p \to
21 \lnot divides p a\to permut (\lambda n.(mod (a*n) p)) (pred p).
23 split.intros.apply le_S_S_to_le.
25 change with mod (a*i) p < p.
28 simplify.apply trans_le ? (S (S O)).
29 apply le_n_Sn.assumption.
30 rewrite < S_pred.apply le_n.
33 apply trans_lt ? (S O).simplify.apply le_n.assumption.
35 apply nat_compare_elim i j.
42 apply le_plus_to_minus.
43 apply trans_le ? (pred p).assumption.
48 apply trans_lt ? (S O).simplify.apply le_n.assumption.
49 apply le_to_not_lt p (j-i).
50 apply divides_to_le.simplify.
51 apply le_SO_minus.assumption.
52 cut divides p a \lor divides p (j-i).
53 elim Hcut.apply False_ind.apply H1.assumption.assumption.
54 apply divides_times_to_divides.assumption.
55 rewrite > distr_times_minus.
56 apply eq_mod_to_divides.
59 apply trans_lt ? (S O).simplify.apply le_n.assumption.
70 apply le_plus_to_minus.
71 apply trans_le ? (pred p).assumption.
76 apply trans_lt ? (S O).simplify.apply le_n.assumption.
77 apply le_to_not_lt p (i-j).
78 apply divides_to_le.simplify.
79 apply le_SO_minus.assumption.
80 cut divides p a \lor divides p (i-j).
81 elim Hcut.apply False_ind.apply H1.assumption.assumption.
82 apply divides_times_to_divides.assumption.
83 rewrite > distr_times_minus.
84 apply eq_mod_to_divides.
87 apply trans_lt ? (S O).simplify.apply le_n.assumption.