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

Theorem prmreclem3 14941
 Description: Lemma for prmrec 14945. The main inequality established here is , where is the set of squarefree numbers in . This is demonstrated by the map where is the largest number whose square divides . (Contributed by Mario Carneiro, 5-Aug-2014.)
Hypotheses
Ref Expression
prmrec.1
prmrec.2
prmrec.3
prmrec.4
prmreclem2.5
Assertion
Ref Expression
prmreclem3
Distinct variable groups:   ,,,   ,,   ,,   ,,   ,,,   ,,
Allowed substitution hints:   ()   ()   ()   ()

Proof of Theorem prmreclem3
Dummy variables are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 fzfi 12223 . . . . . 6
2 prmrec.4 . . . . . . 7
3 ssrab2 3500 . . . . . . 7
42, 3eqsstri 3448 . . . . . 6
5 ssfi 7810 . . . . . 6
61, 4, 5mp2an 686 . . . . 5
7 hashcl 12576 . . . . 5
86, 7ax-mp 5 . . . 4
98nn0rei 10904 . . 3
109a1i 11 . 2
11 2nn 10790 . . . . . 6
12 prmrec.2 . . . . . . 7
1312nnnn0d 10949 . . . . . 6
14 nnexpcl 12323 . . . . . 6
1511, 13, 14sylancr 676 . . . . 5
1615nnnn0d 10949 . . . 4
17 prmrec.3 . . . . . . . 8
1817nnrpd 11362 . . . . . . 7
1918rpsqrtcld 13550 . . . . . 6
2019rprege0d 11371 . . . . 5
21 flge0nn0 12087 . . . . 5
2220, 21syl 17 . . . 4
2316, 22nn0mulcld 10954 . . 3
2423nn0red 10950 . 2
2515nnred 10646 . . 3
2619rpred 11364 . . 3
2725, 26remulcld 9689 . 2
28 ssrab2 3500 . . . . . . 7
29 ssfi 7810 . . . . . . 7
306, 28, 29mp2an 686 . . . . . 6
31 hashcl 12576 . . . . . 6
3230, 31ax-mp 5 . . . . 5
3332nn0rei 10904 . . . 4
3422nn0red 10950 . . . 4
35 remulcl 9642 . . . 4
3633, 34, 35sylancr 676 . . 3
37 fzfi 12223 . . . . . . 7
38 xpfi 7860 . . . . . . 7
3930, 37, 38mp2an 686 . . . . . 6
40 simpr 468 . . . . . . . . . . . . . . . . . . 19
414, 40sseldi 3416 . . . . . . . . . . . . . . . . . 18
42 elfznn 11854 . . . . . . . . . . . . . . . . . 18
4341, 42syl 17 . . . . . . . . . . . . . . . . 17
44 prmreclem2.5 . . . . . . . . . . . . . . . . . . 19
4544prmreclem1 14939 . . . . . . . . . . . . . . . . . 18
4645simp2d 1043 . . . . . . . . . . . . . . . . 17
4743, 46syl 17 . . . . . . . . . . . . . . . 16
4845simp1d 1042 . . . . . . . . . . . . . . . . . . . 20
4943, 48syl 17 . . . . . . . . . . . . . . . . . . 19
5049nnsqcld 12474 . . . . . . . . . . . . . . . . . 18
5150nnzd 11062 . . . . . . . . . . . . . . . . 17
5250nnne0d 10676 . . . . . . . . . . . . . . . . 17
5343nnzd 11062 . . . . . . . . . . . . . . . . 17
54 dvdsval2 14385 . . . . . . . . . . . . . . . . 17
5551, 52, 53, 54syl3anc 1292 . . . . . . . . . . . . . . . 16
5647, 55mpbid 215 . . . . . . . . . . . . . . 15
57 nnre 10638 . . . . . . . . . . . . . . . . . 18
58 nngt0 10660 . . . . . . . . . . . . . . . . . 18
5957, 58jca 541 . . . . . . . . . . . . . . . . 17
60 nnre 10638 . . . . . . . . . . . . . . . . . 18
61 nngt0 10660 . . . . . . . . . . . . . . . . . 18
6260, 61jca 541 . . . . . . . . . . . . . . . . 17
63 divgt0 10495 . . . . . . . . . . . . . . . . 17
6459, 62, 63syl2an 485 . . . . . . . . . . . . . . . 16
6543, 50, 64syl2anc 673 . . . . . . . . . . . . . . 15
66 elnnz 10971 . . . . . . . . . . . . . . 15
6756, 65, 66sylanbrc 677 . . . . . . . . . . . . . 14
6867nnred 10646 . . . . . . . . . . . . 13
6943nnred 10646 . . . . . . . . . . . . 13
7017nnred 10646 . . . . . . . . . . . . . 14
7170adantr 472 . . . . . . . . . . . . 13
72 dvdsmul1 14401 . . . . . . . . . . . . . . . 16
7356, 51, 72syl2anc 673 . . . . . . . . . . . . . . 15
7443nncnd 10647 . . . . . . . . . . . . . . . 16
7550nncnd 10647 . . . . . . . . . . . . . . . 16
7674, 75, 52divcan1d 10406 . . . . . . . . . . . . . . 15
7773, 76breqtrd 4420 . . . . . . . . . . . . . 14
78 dvdsle 14427 . . . . . . . . . . . . . . 15
7956, 43, 78syl2anc 673 . . . . . . . . . . . . . 14
8077, 79mpd 15 . . . . . . . . . . . . 13
81 elfzle2 11829 . . . . . . . . . . . . . 14
8241, 81syl 17 . . . . . . . . . . . . 13
8368, 69, 71, 80, 82letrd 9809 . . . . . . . . . . . 12
84 nnuz 11218 . . . . . . . . . . . . . 14
8567, 84syl6eleq 2559 . . . . . . . . . . . . 13
8617nnzd 11062 . . . . . . . . . . . . . 14
8786adantr 472 . . . . . . . . . . . . 13
88 elfz5 11818 . . . . . . . . . . . . 13
8985, 87, 88syl2anc 673 . . . . . . . . . . . 12
9083, 89mpbird 240 . . . . . . . . . . 11
91 breq2 4399 . . . . . . . . . . . . . . . . 17
9291notbid 301 . . . . . . . . . . . . . . . 16
9392ralbidv 2829 . . . . . . . . . . . . . . 15
9493, 2elrab2 3186 . . . . . . . . . . . . . 14
9540, 94sylib 201 . . . . . . . . . . . . 13
9695simprd 470 . . . . . . . . . . . 12
9777adantr 472 . . . . . . . . . . . . . . 15
98 eldifi 3544 . . . . . . . . . . . . . . . . . 18
99 prmz 14705 . . . . . . . . . . . . . . . . . 18
10098, 99syl 17 . . . . . . . . . . . . . . . . 17
101100adantl 473 . . . . . . . . . . . . . . . 16
10256adantr 472 . . . . . . . . . . . . . . . 16
10353adantr 472 . . . . . . . . . . . . . . . 16
104 dvdstr 14414 . . . . . . . . . . . . . . . 16
105101, 102, 103, 104syl3anc 1292 . . . . . . . . . . . . . . 15
10697, 105mpan2d 688 . . . . . . . . . . . . . 14
107106con3d 140 . . . . . . . . . . . . 13
108107ralimdva 2805 . . . . . . . . . . . 12
10996, 108mpd 15 . . . . . . . . . . 11
110 breq2 4399 . . . . . . . . . . . . . 14
111110notbid 301 . . . . . . . . . . . . 13
112111ralbidv 2829 . . . . . . . . . . . 12
113112, 2elrab2 3186 . . . . . . . . . . 11
11490, 109, 113sylanbrc 677 . . . . . . . . . 10
11544prmreclem1 14939 . . . . . . . . . . . . 13
116115simp2d 1043 . . . . . . . . . . . 12
11767, 116syl 17 . . . . . . . . . . 11
118115simp1d 1042 . . . . . . . . . . . . . . 15
11967, 118syl 17 . . . . . . . . . . . . . 14
120 elnn1uz2 11258 . . . . . . . . . . . . . 14
121119, 120sylib 201 . . . . . . . . . . . . 13
122121ord 384 . . . . . . . . . . . 12
12344prmreclem1 14939 . . . . . . . . . . . . 13
124123simp3d 1044 . . . . . . . . . . . 12
12543, 122, 124sylsyld 57 . . . . . . . . . . 11
126117, 125mt4d 145 . . . . . . . . . 10
127 fveq2 5879 . . . . . . . . . . . 12
128127eqeq1d 2473 . . . . . . . . . . 11
129128elrab 3184 . . . . . . . . . 10
130114, 126, 129sylanbrc 677 . . . . . . . . 9
13150nnred 10646 . . . . . . . . . . . . . 14
132 dvdsle 14427 . . . . . . . . . . . . . . . 16
13351, 43, 132syl2anc 673 . . . . . . . . . . . . . . 15
13447, 133mpd 15 . . . . . . . . . . . . . 14
135131, 69, 71, 134, 82letrd 9809 . . . . . . . . . . . . 13
13671recnd 9687 . . . . . . . . . . . . . 14
137136sqsqrtd 13578 . . . . . . . . . . . . 13
138135, 137breqtrrd 4422 . . . . . . . . . . . 12
13949nnrpd 11362 . . . . . . . . . . . . 13
14019adantr 472 . . . . . . . . . . . . 13
141 rprege0 11339 . . . . . . . . . . . . . 14
142 rprege0 11339 . . . . . . . . . . . . . 14
143 le2sq 12387 . . . . . . . . . . . . . 14
144141, 142, 143syl2an 485 . . . . . . . . . . . . 13
145139, 140, 144syl2anc 673 . . . . . . . . . . . 12
146138, 145mpbird 240 . . . . . . . . . . 11
14726adantr 472 . . . . . . . . . . . 12
14849nnzd 11062 . . . . . . . . . . . 12
149 flge 12074 . . . . . . . . . . . 12
150147, 148, 149syl2anc 673 . . . . . . . . . . 11
151146, 150mpbid 215 . . . . . . . . . 10
15249, 84syl6eleq 2559 . . . . . . . . . . 11
15322nn0zd 11061 . . . . . . . . . . . 12
154153adantr 472 . . . . . . . . . . 11
155 elfz5 11818 . . . . . . . . . . 11
156152, 154, 155syl2anc 673 . . . . . . . . . 10
157151, 156mpbird 240 . . . . . . . . 9
158 opelxpi 4871 . . . . . . . . 9
159130, 157, 158syl2anc 673 . . . . . . . 8
160159ex 441 . . . . . . 7
161 ovex 6336 . . . . . . . . . . . 12
162 fvex 5889 . . . . . . . . . . . 12
163161, 162opth 4676 . . . . . . . . . . 11
164 oveq1 6315 . . . . . . . . . . . 12
165 oveq12 6317 . . . . . . . . . . . 12
166164, 165sylan2 482 . . . . . . . . . . 11
167163, 166sylbi 200 . . . . . . . . . 10
16876adantrr 731 . . . . . . . . . . 11
16942ssriv 3422 . . . . . . . . . . . . . . 15
1704, 169sstri 3427 . . . . . . . . . . . . . 14
171 simprr 774 . . . . . . . . . . . . . 14
172170, 171sseldi 3416 . . . . . . . . . . . . 13
173172nncnd 10647 . . . . . . . . . . . 12
17444prmreclem1 14939 . . . . . . . . . . . . . . . 16
175174simp1d 1042 . . . . . . . . . . . . . . 15
176172, 175syl 17 . . . . . . . . . . . . . 14
177176nnsqcld 12474 . . . . . . . . . . . . 13
178177nncnd 10647 . . . . . . . . . . . 12
179177nnne0d 10676 . . . . . . . . . . . 12
180173, 178, 179divcan1d 10406 . . . . . . . . . . 11
181168, 180eqeq12d 2486 . . . . . . . . . 10
182167, 181syl5ib 227 . . . . . . . . 9
183 id 22 . . . . . . . . . . 11
184 fveq2 5879 . . . . . . . . . . . 12
185184oveq1d 6323 . . . . . . . . . . 11
186183, 185oveq12d 6326 . . . . . . . . . 10
187186, 184opeq12d 4166 . . . . . . . . 9
188182, 187impbid1 208 . . . . . . . 8
189188ex 441 . . . . . . 7
190160, 189dom2d 7628 . . . . . 6
19139, 190mpi 20 . . . . 5
192 hashdom 12596 . . . . . 6
1936, 39, 192mp2an 686 . . . . 5
194191, 193sylibr 217 . . . 4
195 hashxp 12647 . . . . . 6
19630, 37, 195mp2an 686 . . . . 5
197 hashfz1 12567 . . . . . . 7
19822, 197syl 17 . . . . . 6
199198oveq2d 6324 . . . . 5
200196, 199syl5eq 2517 . . . 4
201194, 200breqtrd 4420 . . 3
20233a1i 11 . . . 4
20322nn0ge0d 10952 . . . 4
204 prmrec.1 . . . . 5
205204, 12, 17, 2, 44prmreclem2 14940 . . . 4
206202, 25, 34, 203, 205lemul1ad 10568 . . 3
20710, 36, 24, 201, 206letrd 9809 . 2
20815nnrpd 11362 . . . 4
209208rprege0d 11371 . . 3
210 fllelt 12066 . . . . 5
21126, 210syl 17 . . . 4
212211simpld 466 . . 3
213 lemul2a 10482 . . 3
21434, 26, 209, 212, 213syl31anc 1295 . 2
21510, 24, 27, 207, 214letrd 9809 1
 Colors of variables: wff setvar class Syntax hints:   wn 3   wi 4   wb 189   wo 375   wa 376   wceq 1452   wcel 1904   wne 2641  wral 2756  crab 2760   cdif 3387   wss 3390  cif 3872  cop 3965   class class class wbr 4395   cmpt 4454   cxp 4837  cfv 5589  (class class class)co 6308   cdom 7585  cfn 7587  csup 7972  cr 9556  cc0 9557  c1 9558   caddc 9560   cmul 9562   clt 9693   cle 9694   cdiv 10291  cn 10631  c2 10681  cn0 10893  cz 10961  cuz 11182  crp 11325  cfz 11810  cfl 12059  cexp 12310  chash 12553  csqrt 13373   cdvds 14382  cprime 14701 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1677  ax-4 1690  ax-5 1766  ax-6 1813  ax-7 1859  ax-8 1906  ax-9 1913  ax-10 1932  ax-11 1937  ax-12 1950  ax-13 2104  ax-ext 2451  ax-rep 4508  ax-sep 4518  ax-nul 4527  ax-pow 4579  ax-pr 4639  ax-un 6602  ax-cnex 9613  ax-resscn 9614  ax-1cn 9615  ax-icn 9616  ax-addcl 9617  ax-addrcl 9618  ax-mulcl 9619  ax-mulrcl 9620  ax-mulcom 9621  ax-addass 9622  ax-mulass 9623  ax-distr 9624  ax-i2m1 9625  ax-1ne0 9626  ax-1rid 9627  ax-rnegex 9628  ax-rrecex 9629  ax-cnre 9630  ax-pre-lttri 9631  ax-pre-lttrn 9632  ax-pre-ltadd 9633  ax-pre-mulgt0 9634  ax-pre-sup 9635 This theorem depends on definitions:  df-bi 190  df-or 377  df-an 378  df-3or 1008  df-3an 1009  df-tru 1455  df-ex 1672  df-nf 1676  df-sb 1806  df-eu 2323  df-mo 2324  df-clab 2458  df-cleq 2464  df-clel 2467  df-nfc 2601  df-ne 2643  df-nel 2644  df-ral 2761  df-rex 2762  df-reu 2763  df-rmo 2764  df-rab 2765  df-v 3033  df-sbc 3256  df-csb 3350  df-dif 3393  df-un 3395  df-in 3397  df-ss 3404  df-pss 3406  df-nul 3723  df-if 3873  df-pw 3944  df-sn 3960  df-pr 3962  df-tp 3964  df-op 3966  df-uni 4191  df-int 4227  df-iun 4271  df-br 4396  df-opab 4455  df-mpt 4456  df-tr 4491  df-eprel 4750  df-id 4754  df-po 4760  df-so 4761  df-fr 4798  df-we 4800  df-xp 4845  df-rel 4846  df-cnv 4847  df-co 4848  df-dm 4849  df-rn 4850  df-res 4851  df-ima 4852  df-pred 5387  df-ord 5433  df-on 5434  df-lim 5435  df-suc 5436  df-iota 5553  df-fun 5591  df-fn 5592  df-f 5593  df-f1 5594  df-fo 5595  df-f1o 5596  df-fv 5597  df-riota 6270  df-ov 6311  df-oprab 6312  df-mpt2 6313  df-om 6712  df-1st 6812  df-2nd 6813  df-wrecs 7046  df-recs 7108  df-rdg 7146  df-1o 7200  df-2o 7201  df-oadd 7204  df-er 7381  df-map 7492  df-pm 7493  df-en 7588  df-dom 7589  df-sdom 7590  df-fin 7591  df-sup 7974  df-inf 7975  df-card 8391  df-cda 8616  df-pnf 9695  df-mnf 9696  df-xr 9697  df-ltxr 9698  df-le 9699  df-sub 9882  df-neg 9883  df-div 10292  df-nn 10632  df-2 10690  df-3 10691  df-n0 10894  df-z 10962  df-uz 11183  df-q 11288  df-rp 11326  df-fz 11811  df-fl 12061  df-mod 12130  df-seq 12252  df-exp 12311  df-hash 12554  df-cj 13239  df-re 13240  df-im 13241  df-sqrt 13375  df-abs 13376  df-dvds 14383  df-gcd 14548  df-prm 14702  df-pc 14866 This theorem is referenced by:  prmreclem5  14943
 Copyright terms: Public domain W3C validator