Metamath Proof Explorer


Theorem wilthlem1

Description: The only elements that are equal to their own inverses in the multiplicative group of nonzero elements in ZZ / P ZZ are 1 and -u 1 == P - 1 . (Note that from prmdiveq , ( N ^ ( P - 2 ) ) mod P is the modular inverse of N in ZZ / P ZZ . (Contributed by Mario Carneiro, 24-Jan-2015)

Ref Expression
Assertion wilthlem1 P N 1 P 1 N = N P 2 mod P N = 1 N = P 1

Proof

Step Hyp Ref Expression
1 elfzelz N 1 P 1 N
2 1 adantl P N 1 P 1 N
3 peano2zm N N 1
4 2 3 syl P N 1 P 1 N 1
5 4 zcnd P N 1 P 1 N 1
6 2 peano2zd P N 1 P 1 N + 1
7 6 zcnd P N 1 P 1 N + 1
8 5 7 mulcomd P N 1 P 1 N 1 N + 1 = N + 1 N 1
9 2 zcnd P N 1 P 1 N
10 ax-1cn 1
11 subsq N 1 N 2 1 2 = N + 1 N 1
12 9 10 11 sylancl P N 1 P 1 N 2 1 2 = N + 1 N 1
13 9 sqvald P N 1 P 1 N 2 = N N
14 sq1 1 2 = 1
15 14 a1i P N 1 P 1 1 2 = 1
16 13 15 oveq12d P N 1 P 1 N 2 1 2 = N N 1
17 8 12 16 3eqtr2d P N 1 P 1 N 1 N + 1 = N N 1
18 17 breq2d P N 1 P 1 P N 1 N + 1 P N N 1
19 fz1ssfz0 1 P 1 0 P 1
20 simpr P N 1 P 1 N 1 P 1
21 19 20 sselid P N 1 P 1 N 0 P 1
22 21 biantrurd P N 1 P 1 P N N 1 N 0 P 1 P N N 1
23 18 22 bitrd P N 1 P 1 P N 1 N + 1 N 0 P 1 P N N 1
24 simpl P N 1 P 1 P
25 euclemma P N 1 N + 1 P N 1 N + 1 P N 1 P N + 1
26 24 4 6 25 syl3anc P N 1 P 1 P N 1 N + 1 P N 1 P N + 1
27 prmnn P P
28 fzm1ndvds P N 1 P 1 ¬ P N
29 27 28 sylan P N 1 P 1 ¬ P N
30 eqid N P 2 mod P = N P 2 mod P
31 30 prmdiveq P N ¬ P N N 0 P 1 P N N 1 N = N P 2 mod P
32 24 2 29 31 syl3anc P N 1 P 1 N 0 P 1 P N N 1 N = N P 2 mod P
33 23 26 32 3bitr3rd P N 1 P 1 N = N P 2 mod P P N 1 P N + 1
34 24 27 syl P N 1 P 1 P
35 1zzd P N 1 P 1 1
36 moddvds P N 1 N mod P = 1 mod P P N 1
37 34 2 35 36 syl3anc P N 1 P 1 N mod P = 1 mod P P N 1
38 elfznn N 1 P 1 N
39 38 adantl P N 1 P 1 N
40 39 nnred P N 1 P 1 N
41 34 nnrpd P N 1 P 1 P +
42 39 nnnn0d P N 1 P 1 N 0
43 42 nn0ge0d P N 1 P 1 0 N
44 elfzle2 N 1 P 1 N P 1
45 44 adantl P N 1 P 1 N P 1
46 prmz P P
47 zltlem1 N P N < P N P 1
48 1 46 47 syl2anr P N 1 P 1 N < P N P 1
49 45 48 mpbird P N 1 P 1 N < P
50 modid N P + 0 N N < P N mod P = N
51 40 41 43 49 50 syl22anc P N 1 P 1 N mod P = N
52 34 nnred P N 1 P 1 P
53 prmuz2 P P 2
54 24 53 syl P N 1 P 1 P 2
55 eluz2gt1 P 2 1 < P
56 54 55 syl P N 1 P 1 1 < P
57 1mod P 1 < P 1 mod P = 1
58 52 56 57 syl2anc P N 1 P 1 1 mod P = 1
59 51 58 eqeq12d P N 1 P 1 N mod P = 1 mod P N = 1
60 37 59 bitr3d P N 1 P 1 P N 1 N = 1
61 35 znegcld P N 1 P 1 1
62 moddvds P N 1 N mod P = -1 mod P P N -1
63 34 2 61 62 syl3anc P N 1 P 1 N mod P = -1 mod P P N -1
64 34 nncnd P N 1 P 1 P
65 64 mulid2d P N 1 P 1 1 P = P
66 65 oveq2d P N 1 P 1 - 1 + 1 P = - 1 + P
67 neg1cn 1
68 addcom 1 P - 1 + P = P + -1
69 67 64 68 sylancr P N 1 P 1 - 1 + P = P + -1
70 negsub P 1 P + -1 = P 1
71 64 10 70 sylancl P N 1 P 1 P + -1 = P 1
72 66 69 71 3eqtrd P N 1 P 1 - 1 + 1 P = P 1
73 72 oveq1d P N 1 P 1 - 1 + 1 P mod P = P 1 mod P
74 neg1rr 1
75 74 a1i P N 1 P 1 1
76 modcyc 1 P + 1 - 1 + 1 P mod P = -1 mod P
77 75 41 35 76 syl3anc P N 1 P 1 - 1 + 1 P mod P = -1 mod P
78 peano2rem P P 1
79 52 78 syl P N 1 P 1 P 1
80 nnm1nn0 P P 1 0
81 34 80 syl P N 1 P 1 P 1 0
82 81 nn0ge0d P N 1 P 1 0 P 1
83 52 ltm1d P N 1 P 1 P 1 < P
84 modid P 1 P + 0 P 1 P 1 < P P 1 mod P = P 1
85 79 41 82 83 84 syl22anc P N 1 P 1 P 1 mod P = P 1
86 73 77 85 3eqtr3d P N 1 P 1 -1 mod P = P 1
87 51 86 eqeq12d P N 1 P 1 N mod P = -1 mod P N = P 1
88 subneg N 1 N -1 = N + 1
89 9 10 88 sylancl P N 1 P 1 N -1 = N + 1
90 89 breq2d P N 1 P 1 P N -1 P N + 1
91 63 87 90 3bitr3rd P N 1 P 1 P N + 1 N = P 1
92 60 91 orbi12d P N 1 P 1 P N 1 P N + 1 N = 1 N = P 1
93 33 92 bitrd P N 1 P 1 N = N P 2 mod P N = 1 N = P 1