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

Theorem lgsdir 21107
 Description: The Legendre symbol is completely multiplicative in its left argument. Together with lgsqr 21123 this implies that the product of two quadratic residues or nonresidues is a residue, and the product of a residue and a nonresidue is a nonresidue. (Contributed by Mario Carneiro, 4-Feb-2015.)
Assertion
Ref Expression
lgsdir

Proof of Theorem lgsdir
Dummy variables are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 ax-1cn 9041 . . . . . . 7
2 0cn 9077 . . . . . . 7
31, 2keepel 3789 . . . . . 6
43mulid2i 9086 . . . . 5
5 iftrue 3738 . . . . . . 7
65adantl 453 . . . . . 6
76oveq1d 6089 . . . . 5
8 simpl1 960 . . . . . . . . . . 11
98zcnd 10369 . . . . . . . . . 10
109ad2antrr 707 . . . . . . . . 9
11 simpl2 961 . . . . . . . . . . 11
1211zcnd 10369 . . . . . . . . . 10
1312ad2antrr 707 . . . . . . . . 9
1410, 13sqmuld 11528 . . . . . . . 8
15 simpr 448 . . . . . . . . 9
1615oveq1d 6089 . . . . . . . 8
1712sqcld 11514 . . . . . . . . . 10
1817ad2antrr 707 . . . . . . . . 9
1918mulid2d 9099 . . . . . . . 8
2014, 16, 193eqtrd 2472 . . . . . . 7
2120eqeq1d 2444 . . . . . 6
2221ifbid 3750 . . . . 5
234, 7, 223eqtr4a 2494 . . . 4
243mul02i 9248 . . . . 5
25 iffalse 3739 . . . . . . 7
2625adantl 453 . . . . . 6
2726oveq1d 6089 . . . . 5
28 dvdsmul1 12864 . . . . . . . . . . . 12
298, 11, 28syl2anc 643 . . . . . . . . . . 11
308, 11zmulcld 10374 . . . . . . . . . . . 12
31 dvdssq 13053 . . . . . . . . . . . 12
328, 30, 31syl2anc 643 . . . . . . . . . . 11
3329, 32mpbid 202 . . . . . . . . . 10
3433adantr 452 . . . . . . . . 9
35 breq2 4209 . . . . . . . . 9
3634, 35syl5ibcom 212 . . . . . . . 8
37 simprl 733 . . . . . . . . . . . . . . . 16
3837neneqd 2615 . . . . . . . . . . . . . . 15
39 sqeq0 11439 . . . . . . . . . . . . . . . 16
409, 39syl 16 . . . . . . . . . . . . . . 15
4138, 40mtbird 293 . . . . . . . . . . . . . 14
42 zsqcl2 11452 . . . . . . . . . . . . . . . . 17
438, 42syl 16 . . . . . . . . . . . . . . . 16
44 elnn0 10216 . . . . . . . . . . . . . . . 16
4543, 44sylib 189 . . . . . . . . . . . . . . 15
4645ord 367 . . . . . . . . . . . . . 14
4741, 46mt3d 119 . . . . . . . . . . . . 13
4847adantr 452 . . . . . . . . . . . 12
4948nnzd 10367 . . . . . . . . . . 11
50 1nn 10004 . . . . . . . . . . 11
51 dvdsle 12888 . . . . . . . . . . 11
5249, 50, 51sylancl 644 . . . . . . . . . 10
5348nnge1d 10035 . . . . . . . . . 10
5452, 53jctird 529 . . . . . . . . 9
5548nnred 10008 . . . . . . . . . 10
56 1re 9083 . . . . . . . . . 10
57 letri3 9153 . . . . . . . . . 10
5855, 56, 57sylancl 644 . . . . . . . . 9
5954, 58sylibrd 226 . . . . . . . 8
6036, 59syld 42 . . . . . . 7
6160con3and 429 . . . . . 6
62 iffalse 3739 . . . . . 6
6361, 62syl 16 . . . . 5
6424, 27, 633eqtr4a 2494 . . . 4
6523, 64pm2.61dan 767 . . 3
66 oveq2 6082 . . . . 5
67 lgs0 21086 . . . . . 6
688, 67syl 16 . . . . 5
6966, 68sylan9eqr 2490 . . . 4
70 oveq2 6082 . . . . 5
71 lgs0 21086 . . . . . 6
7211, 71syl 16 . . . . 5
7370, 72sylan9eqr 2490 . . . 4
7469, 73oveq12d 6092 . . 3
75 oveq2 6082 . . . 4
76 lgs0 21086 . . . . 5
7730, 76syl 16 . . . 4
7875, 77sylan9eqr 2490 . . 3
7965, 74, 783eqtr4rd 2479 . 2
80 lgsdilem 21099 . . . . 5
8180adantr 452 . . . 4
82 mulcl 9067 . . . . . 6
8382adantl 453 . . . . 5
84 mulcom 9069 . . . . . 6
8584adantl 453 . . . . 5
86 mulass 9071 . . . . . 6
8786adantl 453 . . . . 5
88 simpl3 962 . . . . . . 7
89 nnabscl 12122 . . . . . . 7
9088, 89sylan 458 . . . . . 6
91 nnuz 10514 . . . . . 6
9290, 91syl6eleq 2526 . . . . 5
93 simpll1 996 . . . . . . . 8
94 simpll3 998 . . . . . . . 8
95 simpr 448 . . . . . . . 8
96 eqid 2436 . . . . . . . . 9
9796lgsfcl3 21094 . . . . . . . 8
9893, 94, 95, 97syl3anc 1184 . . . . . . 7
99 elfznn 11073 . . . . . . 7
100 ffvelrn 5861 . . . . . . 7
10198, 99, 100syl2an 464 . . . . . 6
102101zcnd 10369 . . . . 5
103 simpll2 997 . . . . . . . 8
104 eqid 2436 . . . . . . . . 9
105104lgsfcl3 21094 . . . . . . . 8
106103, 94, 95, 105syl3anc 1184 . . . . . . 7
107 ffvelrn 5861 . . . . . . 7
108106, 99, 107syl2an 464 . . . . . 6
109108zcnd 10369 . . . . 5
11093adantr 452 . . . . . . . . . . . 12
111103adantr 452 . . . . . . . . . . . 12
112 simpr 448 . . . . . . . . . . . 12
113 lgsdirprm 21106 . . . . . . . . . . . 12
114110, 111, 112, 113syl3anc 1184 . . . . . . . . . . 11
115114oveq1d 6089 . . . . . . . . . 10
116 prmz 13076 . . . . . . . . . . . . 13
117 lgscl 21087 . . . . . . . . . . . . 13
11893, 116, 117syl2an 464 . . . . . . . . . . . 12
119118zcnd 10369 . . . . . . . . . . 11
120 lgscl 21087 . . . . . . . . . . . . 13
121103, 116, 120syl2an 464 . . . . . . . . . . . 12
122121zcnd 10369 . . . . . . . . . . 11
12394adantr 452 . . . . . . . . . . . 12
12495adantr 452 . . . . . . . . . . . 12
125 pczcl 13215 . . . . . . . . . . . 12
126112, 123, 124, 125syl12anc 1182 . . . . . . . . . . 11
127119, 122, 126mulexpd 11531 . . . . . . . . . 10
128115, 127eqtrd 2468 . . . . . . . . 9
129 iftrue 3738 . . . . . . . . . 10
130129adantl 453 . . . . . . . . 9
131 iftrue 3738 . . . . . . . . . . 11
132 iftrue 3738 . . . . . . . . . . 11
133131, 132oveq12d 6092 . . . . . . . . . 10
134133adantl 453 . . . . . . . . 9
135128, 130, 1343eqtr4d 2478 . . . . . . . 8
136 1t1e1 10119 . . . . . . . . . . 11
137136eqcomi 2440 . . . . . . . . . 10
138 iffalse 3739 . . . . . . . . . 10
139 iffalse 3739 . . . . . . . . . . 11
140 iffalse 3739 . . . . . . . . . . 11
141139, 140oveq12d 6092 . . . . . . . . . 10
142137, 138, 1413eqtr4a 2494 . . . . . . . . 9
143142adantl 453 . . . . . . . 8
144135, 143pm2.61dan 767 . . . . . . 7
145144adantr 452 . . . . . 6
14699adantl 453 . . . . . . 7
147 eleq1 2496 . . . . . . . . 9
148 oveq2 6082 . . . . . . . . . 10
149 oveq1 6081 . . . . . . . . . 10
150148, 149oveq12d 6092 . . . . . . . . 9
151 eqidd 2437 . . . . . . . . 9
152147, 150, 151ifbieq12d 3754 . . . . . . . 8
153 eqid 2436 . . . . . . . 8
154 ovex 6099 . . . . . . . . 9
155 1ex 9079 . . . . . . . . 9
156154, 155ifex 3790 . . . . . . . 8
157152, 153, 156fvmpt 5799 . . . . . . 7
158146, 157syl 16 . . . . . 6
159 oveq2 6082 . . . . . . . . . . 11
160159, 149oveq12d 6092 . . . . . . . . . 10
161147, 160, 151ifbieq12d 3754 . . . . . . . . 9
162 ovex 6099 . . . . . . . . . 10
163162, 155ifex 3790 . . . . . . . . 9
164161, 96, 163fvmpt 5799 . . . . . . . 8
165146, 164syl 16 . . . . . . 7
166 oveq2 6082 . . . . . . . . . . 11
167166, 149oveq12d 6092 . . . . . . . . . 10
168147, 167, 151ifbieq12d 3754 . . . . . . . . 9
169 ovex 6099 . . . . . . . . . 10
170169, 155ifex 3790 . . . . . . . . 9
171168, 104, 170fvmpt 5799 . . . . . . . 8
172146, 171syl 16 . . . . . . 7
173165, 172oveq12d 6092 . . . . . 6
174145, 158, 1733eqtr4d 2478 . . . . 5
17583, 85, 87, 92, 102, 109, 174seqcaopr 11353 . . . 4
17681, 175oveq12d 6092 . . 3
17730adantr 452 . . . 4
178153lgsval4 21093 . . . 4
179177, 94, 95, 178syl3anc 1184 . . 3
18096lgsval4 21093 . . . . . 6
18193, 94, 95, 180syl3anc 1184 . . . . 5
182104lgsval4 21093 . . . . . 6
183103, 94, 95, 182syl3anc 1184 . . . . 5
184181, 183oveq12d 6092 . . . 4
185 neg1cn 10060 . . . . . . 7
186185, 1keepel 3789 . . . . . 6
187186a1i 11 . . . . 5
188 mulcl 9067 . . . . . . 7
189188adantl 453 . . . . . 6
19092, 102, 189seqcl 11336 . . . . 5
191185, 1keepel 3789 . . . . . 6
192191a1i 11 . . . . 5
19392, 109, 189seqcl 11336 . . . . 5
194187, 190, 192, 193mul4d 9271 . . . 4
195184, 194eqtrd 2468 . . 3
196176, 179, 1953eqtr4d 2478 . 2
19779, 196pm2.61dane 2677 1
 Colors of variables: wff set class Syntax hints:   wn 3   wi 4   wb 177   wo 358   wa 359   w3a 936   wceq 1652   wcel 1725   wne 2599  cif 3732   class class class wbr 4205   cmpt 4259  wf 5443  cfv 5447  (class class class)co 6074  cc 8981  cr 8982  cc0 8983  c1 8984   cmul 8988   clt 9113   cle 9114  cneg 9285  cn 9993  c2 10042  cn0 10214  cz 10275  cuz 10481  cfz 11036   cseq 11316  cexp 11375  cabs 12032   cdivides 12845  cprime 13072   cpc 13203   clgs 21071 This theorem is referenced by:  lgssq  21112  lgsdirnn0  21116  lgsquad2lem1  21135 This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1555  ax-5 1566  ax-17 1626  ax-9 1666  ax-8 1687  ax-13 1727  ax-14 1729  ax-6 1744  ax-7 1749  ax-11 1761  ax-12 1950  ax-ext 2417  ax-rep 4313  ax-sep 4323  ax-nul 4331  ax-pow 4370  ax-pr 4396  ax-un 4694  ax-cnex 9039  ax-resscn 9040  ax-1cn 9041  ax-icn 9042  ax-addcl 9043  ax-addrcl 9044  ax-mulcl 9045  ax-mulrcl 9046  ax-mulcom 9047  ax-addass 9048  ax-mulass 9049  ax-distr 9050  ax-i2m1 9051  ax-1ne0 9052  ax-1rid 9053  ax-rnegex 9054  ax-rrecex 9055  ax-cnre 9056  ax-pre-lttri 9057  ax-pre-lttrn 9058  ax-pre-ltadd 9059  ax-pre-mulgt0 9060  ax-pre-sup 9061 This theorem depends on definitions:  df-bi 178  df-or 360  df-an 361  df-3or 937  df-3an 938  df-tru 1328  df-ex 1551  df-nf 1554  df-sb 1659  df-eu 2285  df-mo 2286  df-clab 2423  df-cleq 2429  df-clel 2432  df-nfc 2561  df-ne 2601  df-nel 2602  df-ral 2703  df-rex 2704  df-reu 2705  df-rmo 2706  df-rab 2707  df-v 2951  df-sbc 3155  df-csb 3245  df-dif 3316  df-un 3318  df-in 3320  df-ss 3327  df-pss 3329  df-nul 3622  df-if 3733  df-pw 3794  df-sn 3813  df-pr 3814  df-tp 3815  df-op 3816  df-uni 4009  df-int 4044  df-iun 4088  df-br 4206  df-opab 4260  df-mpt 4261  df-tr 4296  df-eprel 4487  df-id 4491  df-po 4496  df-so 4497  df-fr 4534  df-we 4536  df-ord 4577  df-on 4578  df-lim 4579  df-suc 4580  df-om 4839  df-xp 4877  df-rel 4878  df-cnv 4879  df-co 4880  df-dm 4881  df-rn 4882  df-res 4883  df-ima 4884  df-iota 5411  df-fun 5449  df-fn 5450  df-f 5451  df-f1 5452  df-fo 5453  df-f1o 5454  df-fv 5455  df-ov 6077  df-oprab 6078  df-mpt2 6079  df-1st 6342  df-2nd 6343  df-riota 6542  df-recs 6626  df-rdg 6661  df-1o 6717  df-2o 6718  df-oadd 6721  df-er 6898  df-map 7013  df-en 7103  df-dom 7104  df-sdom 7105  df-fin 7106  df-sup 7439  df-card 7819  df-cda 8041  df-pnf 9115  df-mnf 9116  df-xr 9117  df-ltxr 9118  df-le 9119  df-sub 9286  df-neg 9287  df-div 9671  df-nn 9994  df-2 10051  df-3 10052  df-4 10053  df-5 10054  df-6 10055  df-7 10056  df-8 10057  df-9 10058  df-n0 10215  df-z 10276  df-uz 10482  df-q 10568  df-rp 10606  df-fz 11037  df-fzo 11129  df-fl 11195  df-mod 11244  df-seq 11317  df-exp 11376  df-hash 11612  df-cj 11897  df-re 11898  df-im 11899  df-sqr 12033  df-abs 12034  df-dvds 12846  df-gcd 13000  df-prm 13073  df-phi 13148  df-pc 13204  df-lgs 21072
 Copyright terms: Public domain W3C validator