Metamath Proof Explorer < Previous   Next > Nearby theorems Mirrors  >  Home  >  MPE Home  >  Th. List  >  lgsqrlem2 Structured version   Unicode version

Theorem lgsqrlem2 21128
 Description: Lemma for lgsqr 21132. (Contributed by Mario Carneiro, 15-Jun-2015.)
Hypotheses
Ref Expression
lgsqr.y ℤ/n
lgsqr.s Poly1
lgsqr.b
lgsqr.d deg1
lgsqr.o eval1
lgsqr.e .gmulGrp
lgsqr.x var1
lgsqr.m
lgsqr.u
lgsqr.t
lgsqr.l RHom
lgsqr.1
lgsqr.g
Assertion
Ref Expression
lgsqrlem2
Distinct variable groups:   ,   ,   ,   ,   ,   ,
Allowed substitution hints:   ()   ()   ()   ()   ()   ()   ()   ()

Proof of Theorem lgsqrlem2
Dummy variables are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 lgsqr.1 . . . . . . . . . . . . 13
21eldifad 3334 . . . . . . . . . . . 12
3 lgsqr.y . . . . . . . . . . . . 13 ℤ/n
43znfld 16843 . . . . . . . . . . . 12 Field
52, 4syl 16 . . . . . . . . . . 11 Field
6 fldidom 16367 . . . . . . . . . . 11 Field IDomn
75, 6syl 16 . . . . . . . . . 10 IDomn
8 isidom 16366 . . . . . . . . . . 11 IDomn Domn
98simplbi 448 . . . . . . . . . 10 IDomn
107, 9syl 16 . . . . . . . . 9
11 crngrng 15676 . . . . . . . . 9
1210, 11syl 16 . . . . . . . 8
13 eqid 2438 . . . . . . . . 9 flds flds
14 lgsqr.l . . . . . . . . 9 RHom
1513, 14zrhrhm 16795 . . . . . . . 8 flds RingHom
1612, 15syl 16 . . . . . . 7 flds RingHom
17 zsubrg 16754 . . . . . . . . 9 SubRingfld
1813subrgbas 15879 . . . . . . . . 9 SubRingfld flds
1917, 18ax-mp 8 . . . . . . . 8 flds
20 eqid 2438 . . . . . . . 8
2119, 20rhmf 15829 . . . . . . 7 flds RingHom
2216, 21syl 16 . . . . . 6
2322adantr 453 . . . . 5
24 elfzelz 11061 . . . . . . 7
2524adantl 454 . . . . . 6
26 zsqcl 11454 . . . . . 6
2725, 26syl 16 . . . . 5
2823, 27ffvelrnd 5873 . . . 4
29 lgsqr.s . . . . 5 Poly1
30 lgsqr.b . . . . 5
31 lgsqr.d . . . . 5 deg1
32 lgsqr.o . . . . 5 eval1
33 lgsqr.e . . . . 5 .gmulGrp
34 lgsqr.x . . . . 5 var1
35 lgsqr.m . . . . 5
36 lgsqr.u . . . . 5
37 lgsqr.t . . . . 5
381adantr 453 . . . . 5
39 elfznn 11082 . . . . . . . . . . 11
4039adantl 454 . . . . . . . . . 10
4140nncnd 10018 . . . . . . . . 9
42 oddprm 13191 . . . . . . . . . . . 12
431, 42syl 16 . . . . . . . . . . 11
4443nnnn0d 10276 . . . . . . . . . 10
4544adantr 453 . . . . . . . . 9
46 2nn0 10240 . . . . . . . . . 10
4746a1i 11 . . . . . . . . 9
4841, 45, 47expmuld 11528 . . . . . . . 8
49 prmnn 13084 . . . . . . . . . . . . . . . 16
502, 49syl 16 . . . . . . . . . . . . . . 15
5150nnred 10017 . . . . . . . . . . . . . 14
52 peano2rem 9369 . . . . . . . . . . . . . 14
5351, 52syl 16 . . . . . . . . . . . . 13
5453recnd 9116 . . . . . . . . . . . 12
55 2cn 10072 . . . . . . . . . . . . 13
5655a1i 11 . . . . . . . . . . . 12
57 2ne0 10085 . . . . . . . . . . . . 13
5857a1i 11 . . . . . . . . . . . 12
5954, 56, 58divcan2d 9794 . . . . . . . . . . 11
60 phiprm 13168 . . . . . . . . . . . 12
612, 60syl 16 . . . . . . . . . . 11
6259, 61eqtr4d 2473 . . . . . . . . . 10
6362adantr 453 . . . . . . . . 9
6463oveq2d 6099 . . . . . . . 8
6548, 64eqtr3d 2472 . . . . . . 7
6665oveq1d 6098 . . . . . 6
672adantr 453 . . . . . . . 8
6867, 49syl 16 . . . . . . 7
6950nnzd 10376 . . . . . . . . . 10
7069adantr 453 . . . . . . . . 9
71 gcdcom 13022 . . . . . . . . 9
7225, 70, 71syl2anc 644 . . . . . . . 8
7340nnred 10017 . . . . . . . . . . . 12
7453rehalfcld 10216 . . . . . . . . . . . . 13
7574adantr 453 . . . . . . . . . . . 12
7651adantr 453 . . . . . . . . . . . 12
77 elfzle2 11063 . . . . . . . . . . . . 13
7877adantl 454 . . . . . . . . . . . 12
79 prmuz2 13099 . . . . . . . . . . . . . . . . . 18
802, 79syl 16 . . . . . . . . . . . . . . . . 17
81 uz2m1nn 10552 . . . . . . . . . . . . . . . . 17
8280, 81syl 16 . . . . . . . . . . . . . . . 16
8382nnrpd 10649 . . . . . . . . . . . . . . 15
84 rphalflt 10640 . . . . . . . . . . . . . . 15
8583, 84syl 16 . . . . . . . . . . . . . 14
8651ltm1d 9945 . . . . . . . . . . . . . 14
8774, 53, 51, 85, 86lttrd 9233 . . . . . . . . . . . . 13
8887adantr 453 . . . . . . . . . . . 12
8973, 75, 76, 78, 88lelttrd 9230 . . . . . . . . . . 11
9073, 76ltnled 9222 . . . . . . . . . . 11
9189, 90mpbid 203 . . . . . . . . . 10
92 dvdsle 12897 . . . . . . . . . . 11
9370, 40, 92syl2anc 644 . . . . . . . . . 10
9491, 93mtod 171 . . . . . . . . 9
95 coprm 13102 . . . . . . . . . 10
9667, 25, 95syl2anc 644 . . . . . . . . 9
9794, 96mpbid 203 . . . . . . . 8
9872, 97eqtrd 2470 . . . . . . 7
99 eulerth 13174 . . . . . . 7
10068, 25, 98, 99syl3anc 1185 . . . . . 6
10166, 100eqtrd 2470 . . . . 5
1023, 29, 30, 31, 32, 33, 34, 35, 36, 37, 14, 38, 27, 101lgsqrlem1 21127 . . . 4
103 eqid 2438 . . . . . . . 8 s s
104 eqid 2438 . . . . . . . 8 s s
105 fvex 5744 . . . . . . . . 9
106105a1i 11 . . . . . . . 8
10732, 29, 103, 20evl1rhm 19951 . . . . . . . . . . 11 RingHom s
10810, 107syl 16 . . . . . . . . . 10 RingHom s
10930, 104rhmf 15829 . . . . . . . . . 10 RingHom s s
110108, 109syl 16 . . . . . . . . 9 s
11129ply1rng 16644 . . . . . . . . . . . . 13
11212, 111syl 16 . . . . . . . . . . . 12
113 rnggrp 15671 . . . . . . . . . . . 12
114112, 113syl 16 . . . . . . . . . . 11
115 eqid 2438 . . . . . . . . . . . . . 14 mulGrp mulGrp
116115rngmgp 15672 . . . . . . . . . . . . 13 mulGrp
117112, 116syl 16 . . . . . . . . . . . 12 mulGrp
11834, 29, 30vr1cl 16613 . . . . . . . . . . . . 13
11912, 118syl 16 . . . . . . . . . . . 12
120115, 30mgpbas 15656 . . . . . . . . . . . . 13 mulGrp
121120, 33mulgnn0cl 14908 . . . . . . . . . . . 12 mulGrp
122117, 44, 119, 121syl3anc 1185 . . . . . . . . . . 11
12330, 36rngidcl 15686 . . . . . . . . . . . 12
124112, 123syl 16 . . . . . . . . . . 11
12530, 35grpsubcl 14871 . . . . . . . . . . 11
126114, 122, 124, 125syl3anc 1185 . . . . . . . . . 10
12737, 126syl5eqel 2522 . . . . . . . . 9
128110, 127ffvelrnd 5873 . . . . . . . 8 s
129103, 20, 104, 5, 106, 128pwselbas 13713 . . . . . . 7
130 ffn 5593 . . . . . . 7
131129, 130syl 16 . . . . . 6
132131adantr 453 . . . . 5
133 fniniseg 5853 . . . . 5
134132, 133syl 16 . . . 4
13528, 102, 134mpbir2and 890 . . 3
136 lgsqr.g . . 3
137135, 136fmptd 5895 . 2
138 oveq1 6090 . . . . . . . . 9
139138fveq2d 5734 . . . . . . . 8
140 fvex 5744 . . . . . . . 8
141139, 136, 140fvmpt 5808 . . . . . . 7
142141ad2antrl 710 . . . . . 6
143 oveq1 6090 . . . . . . . . 9
144143fveq2d 5734 . . . . . . . 8
145 fvex 5744 . . . . . . . 8
146144, 136, 145fvmpt 5808 . . . . . . 7
147146ad2antll 711 . . . . . 6
148142, 147eqeq12d 2452 . . . . 5
14950nnnn0d 10276 . . . . . . 7
150149adantr 453 . . . . . 6
151 elfzelz 11061 . . . . . . . 8
152151ad2antrl 710 . . . . . . 7
153 zsqcl 11454 . . . . . . 7
154152, 153syl 16 . . . . . 6
155 elfzelz 11061 . . . . . . . 8
156155ad2antll 711 . . . . . . 7
157 zsqcl 11454 . . . . . . 7
158156, 157syl 16 . . . . . 6
1593, 14zndvds 16832 . . . . . 6
160150, 154, 158, 159syl3anc 1185 . . . . 5
161 elfznn 11082 . . . . . . . . 9
162161ad2antrl 710 . . . . . . . 8
163162nncnd 10018 . . . . . . 7
164 elfznn 11082 . . . . . . . . 9
165164ad2antll 711 . . . . . . . 8
166165nncnd 10018 . . . . . . 7
167 subsq 11490 . . . . . . 7
168163, 166, 167syl2anc 644 . . . . . 6
169168breq2d 4226 . . . . 5
170148, 160, 1693bitrd 272 . . . 4
1712adantr 453 . . . . . 6
172152, 156zaddcld 10381 . . . . . 6
173152, 156zsubcld 10382 . . . . . 6
174 euclemma 13110 . . . . . 6
175171, 172, 173, 174syl3anc 1185 . . . . 5
176171, 49syl 16 . . . . . . . . 9
177176nnzd 10376 . . . . . . . 8
178162, 165nnaddcld 10048 . . . . . . . 8
179 dvdsle 12897 . . . . . . . 8
180177, 178, 179syl2anc 644 . . . . . . 7
181178nnred 10017 . . . . . . . . . 10
182176nnred 10017 . . . . . . . . . . 11
183182, 52syl 16 . . . . . . . . . 10
184162nnred 10017 . . . . . . . . . . . 12
185165nnred 10017 . . . . . . . . . . . 12
18674adantr 453 . . . . . . . . . . . 12
187 elfzle2 11063 . . . . . . . . . . . . 13
188187ad2antrl 710 . . . . . . . . . . . 12
189 elfzle2 11063 . . . . . . . . . . . . 13
190189ad2antll 711 . . . . . . . . . . . 12
191184, 185, 186, 186, 188, 190le2addd 9646 . . . . . . . . . . 11
19254adantr 453 . . . . . . . . . . . 12
1931922halvesd 10215 . . . . . . . . . . 11
194191, 193breqtrd 4238 . . . . . . . . . 10
195182ltm1d 9945 . . . . . . . . . 10
196181, 183, 182, 194, 195lelttrd 9230 . . . . . . . . 9
197181, 182ltnled 9222 . . . . . . . . 9
198196, 197mpbid 203 . . . . . . . 8
199198pm2.21d 101 . . . . . . 7
200180, 199syld 43 . . . . . 6
201 moddvds 12861 . . . . . . . . 9
202176, 152, 156, 201syl3anc 1185 . . . . . . . 8
203176nnrpd 10649 . . . . . . . . . 10
204162nnnn0d 10276 . . . . . . . . . . 11
205204nn0ge0d 10279 . . . . . . . . . 10
20687adantr 453 . . . . . . . . . . 11
207184, 186, 182, 188, 206lelttrd 9230 . . . . . . . . . 10
208 modid 11272 . . . . . . . . . 10
209184, 203, 205, 207, 208syl22anc 1186 . . . . . . . . 9
210165nnnn0d 10276 . . . . . . . . . . 11
211210nn0ge0d 10279 . . . . . . . . . 10
212185, 186, 182, 190, 206lelttrd 9230 . . . . . . . . . 10
213 modid 11272 . . . . . . . . . 10
214185, 203, 211, 212, 213syl22anc 1186 . . . . . . . . 9
215209, 214eqeq12d 2452 . . . . . . . 8
216202, 215bitr3d 248 . . . . . . 7
217216biimpd 200 . . . . . 6
218200, 217jaod 371 . . . . 5
219175, 218sylbid 208 . . . 4
220170, 219sylbid 208 . . 3
221220ralrimivva 2800 . 2
222 dff13 6006 . 2
223137, 221, 222sylanbrc 647 1
 Colors of variables: wff set class Syntax hints:   wn 3   wi 4   wb 178   wo 359   wa 360   wceq 1653   wcel 1726   wne 2601  wral 2707  cvv 2958   cdif 3319  csn 3816   class class class wbr 4214   cmpt 4268  ccnv 4879  cima 4883   wfn 5451  wf 5452  wf1 5453  cfv 5456  (class class class)co 6083  cc 8990  cr 8991  cc0 8992  c1 8993   caddc 8995   cmul 8997   clt 9122   cle 9123   cmin 9293   cdiv 9679  cn 10002  c2 10051  cn0 10223  cz 10284  cuz 10490  crp 10614  cfz 11045   cmo 11252  cexp 11384   cdivides 12854   cgcd 13008  cprime 13081  cphi 13155  cbs 13471   ↾s cress 13472   s cpws 13672  c0g 13725  cmnd 14686  cgrp 14687  csg 14690  .gcmg 14691  mulGrpcmgp 15650  crg 15662  ccrg 15663  cur 15664   RingHom crh 15819  Fieldcfield 15838  SubRingcsubrg 15866  Domncdomn 16342  IDomncidom 16343  var1cv1 16572  Poly1cpl1 16573  eval1ce1 16575  ℂfldccnfld 16705  RHomczrh 16780  ℤ/nℤczn 16783   deg1 cdg1 19979 This theorem is referenced by:  lgsqrlem4  21130 This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1556  ax-5 1567  ax-17 1627  ax-9 1667  ax-8 1688  ax-13 1728  ax-14 1730  ax-6 1745  ax-7 1750  ax-11 1762  ax-12 1951  ax-ext 2419  ax-rep 4322  ax-sep 4332  ax-nul 4340  ax-pow 4379  ax-pr 4405  ax-un 4703  ax-inf2 7598  ax-cnex 9048  ax-resscn 9049  ax-1cn 9050  ax-icn 9051  ax-addcl 9052  ax-addrcl 9053  ax-mulcl 9054  ax-mulrcl 9055  ax-mulcom 9056  ax-addass 9057  ax-mulass 9058  ax-distr 9059  ax-i2m1 9060  ax-1ne0 9061  ax-1rid 9062  ax-rnegex 9063  ax-rrecex 9064  ax-cnre 9065  ax-pre-lttri 9066  ax-pre-lttrn 9067  ax-pre-ltadd 9068  ax-pre-mulgt0 9069  ax-pre-sup 9070  ax-addf 9071  ax-mulf 9072 This theorem depends on definitions:  df-bi 179  df-or 361  df-an 362  df-3or 938  df-3an 939  df-tru 1329  df-ex 1552  df-nf 1555  df-sb 1660  df-eu 2287  df-mo 2288  df-clab 2425  df-cleq 2431  df-clel 2434  df-nfc 2563  df-ne 2603  df-nel 2604  df-ral 2712  df-rex 2713  df-reu 2714  df-rmo 2715  df-rab 2716  df-v 2960  df-sbc 3164  df-csb 3254  df-dif 3325  df-un 3327  df-in 3329  df-ss 3336  df-pss 3338  df-nul 3631  df-if 3742  df-pw 3803  df-sn 3822  df-pr 3823  df-tp 3824  df-op 3825  df-uni 4018  df-int 4053  df-iun 4097  df-iin 4098  df-br 4215  df-opab 4269  df-mpt 4270  df-tr 4305  df-eprel 4496  df-id 4500  df-po 4505  df-so 4506  df-fr 4543  df-se 4544  df-we 4545  df-ord 4586  df-on 4587  df-lim 4588  df-suc 4589  df-om 4848  df-xp 4886  df-rel 4887  df-cnv 4888  df-co 4889  df-dm 4890  df-rn 4891  df-res 4892  df-ima 4893  df-iota 5420  df-fun 5458  df-fn 5459  df-f 5460  df-f1 5461  df-fo 5462  df-f1o 5463  df-fv 5464  df-isom 5465  df-ov 6086  df-oprab 6087  df-mpt2 6088  df-of 6307  df-ofr 6308  df-1st 6351  df-2nd 6352  df-tpos 6481  df-riota 6551  df-recs 6635  df-rdg 6670  df-1o 6726  df-2o 6727  df-oadd 6730  df-er 6907  df-ec 6909  df-qs 6913  df-map 7022  df-pm 7023  df-ixp 7066  df-en 7112  df-dom 7113  df-sdom 7114  df-fin 7115  df-sup 7448  df-oi 7481  df-card 7828  df-cda 8050  df-pnf 9124  df-mnf 9125  df-xr 9126  df-ltxr 9127  df-le 9128  df-sub 9295  df-neg 9296  df-div 9680  df-nn 10003  df-2 10060  df-3 10061  df-4 10062  df-5 10063  df-6 10064  df-7 10065  df-8 10066  df-9 10067  df-10 10068  df-n0 10224  df-z 10285  df-dec 10385  df-uz 10491  df-rp 10615  df-fz 11046  df-fzo 11138  df-fl 11204  df-mod 11253  df-seq 11326  df-exp 11385  df-hash 11621  df-cj 11906  df-re 11907  df-im 11908  df-sqr 12042  df-abs 12043  df-dvds 12855  df-gcd 13009  df-prm 13082  df-phi 13157  df-struct 13473  df-ndx 13474  df-slot 13475  df-base 13476  df-sets 13477  df-ress 13478  df-plusg 13544  df-mulr 13545  df-starv 13546  df-sca 13547  df-vsca 13548  df-tset 13550  df-ple 13551  df-ds 13553  df-unif 13554  df-hom 13555  df-cco 13556  df-prds 13673  df-pws 13675  df-0g 13729  df-gsum 13730  df-imas 13736  df-divs 13737  df-mre 13813  df-mrc 13814  df-acs 13816  df-mnd 14692  df-mhm 14740  df-submnd 14741  df-grp 14814  df-minusg 14815  df-sbg 14816  df-mulg 14817  df-subg 14943  df-nsg 14944  df-eqg 14945  df-ghm 15006  df-cntz 15118  df-cmn 15416  df-abl 15417  df-mgp 15651  df-rng 15665  df-cring 15666  df-ur 15667  df-oppr 15730  df-dvdsr 15748  df-unit 15749  df-invr 15779  df-rnghom 15821  df-drng 15839  df-field 15840  df-subrg 15868  df-lmod 15954  df-lss 16011  df-lsp 16050  df-sra 16246  df-rgmod 16247  df-lidl 16248  df-rsp 16249  df-2idl 16305  df-nzr 16331  df-rlreg 16345  df-domn 16346  df-idom 16347  df-assa 16374  df-asp 16375  df-ascl 16376  df-psr 16419  df-mvr 16420  df-mpl 16421  df-evls 16422  df-evl 16423  df-opsr 16427  df-psr1 16578  df-vr1 16579  df-ply1 16580  df-evl1 16582  df-cnfld 16706  df-zrh 16784  df-zn 16787
 Copyright terms: Public domain W3C validator