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

Theorem musum 20844
 Description: The sum of the Möbius function over the divisors of gives one if , but otherwise always sums to zero. This makes the Möbius function useful for inverting divisor sums; see also muinv 20846. (Contributed by Mario Carneiro, 2-Jul-2015.)
Assertion
Ref Expression
musum
Distinct variable group:   ,,

Proof of Theorem musum
Dummy variables are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 fveq2 5669 . . . . . . . 8
21neeq1d 2564 . . . . . . 7
3 breq1 4157 . . . . . . 7
42, 3anbi12d 692 . . . . . 6
54elrab 3036 . . . . 5
6 muval2 20785 . . . . . 6
76adantrr 698 . . . . 5
85, 7sylbi 188 . . . 4
98adantl 453 . . 3
109sumeq2dv 12425 . 2
11 simpr 448 . . . . 5
1211a1i 11 . . . 4
1312ss2rabdv 3368 . . 3
14 ssrab2 3372 . . . . . 6
15 simpr 448 . . . . . 6
1614, 15sseldi 3290 . . . . 5
17 mucl 20792 . . . . 5
1816, 17syl 16 . . . 4
1918zcnd 10309 . . 3
20 difrab 3559 . . . . . . 7
21 pm3.21 436 . . . . . . . . . . 11
2221necon1bd 2619 . . . . . . . . . 10
2322imp 419 . . . . . . . . 9
2423a1i 11 . . . . . . . 8
2524ss2rabi 3369 . . . . . . 7
2620, 25eqsstri 3322 . . . . . 6
2726sseli 3288 . . . . 5
281eqeq1d 2396 . . . . . . 7
2928elrab 3036 . . . . . 6
3029simprbi 451 . . . . 5
3127, 30syl 16 . . . 4
3231adantl 453 . . 3
33 fzfid 11240 . . . 4
34 sgmss 20757 . . . 4
35 ssfi 7266 . . . 4
3633, 34, 35syl2anc 643 . . 3
3713, 19, 32, 36fsumss 12447 . 2
38 fveq2 5669 . . . . 5
3938oveq2d 6037 . . . 4
40 ssfi 7266 . . . . 5
4136, 13, 40syl2anc 643 . . . 4
42 eqid 2388 . . . . 5
43 eqid 2388 . . . . 5
44 oveq1 6028 . . . . . . . 8
4544cbvmptv 4242 . . . . . . 7
46 oveq2 6029 . . . . . . . 8
4746mpteq2dv 4238 . . . . . . 7
4845, 47syl5eq 2432 . . . . . 6
4948cbvmptv 4242 . . . . 5
5042, 43, 49sqff1o 20833 . . . 4
51 breq2 4158 . . . . . . 7
5251rabbidv 2892 . . . . . 6
53 zex 10224 . . . . . . . 8
54 prmz 13011 . . . . . . . . 9
5554ssriv 3296 . . . . . . . 8
5653, 55ssexi 4290 . . . . . . 7
5756rabex 4296 . . . . . 6
5852, 43, 57fvmpt 5746 . . . . 5
5958adantl 453 . . . 4
60 neg1cn 10000 . . . . 5
61 prmdvdsfi 20758 . . . . . . 7
62 elpwi 3751 . . . . . . 7
63 ssfi 7266 . . . . . . 7
6461, 62, 63syl2an 464 . . . . . 6
65 hashcl 11567 . . . . . 6
6664, 65syl 16 . . . . 5
67 expcl 11327 . . . . 5
6860, 66, 67sylancr 645 . . . 4
6939, 41, 50, 59, 68fsumf1o 12445 . . 3
70 fzfid 11240 . . . . 5
7161adantr 452 . . . . . . 7
72 pwfi 7338 . . . . . . 7
7371, 72sylib 189 . . . . . 6
74 ssrab2 3372 . . . . . 6
75 ssfi 7266 . . . . . 6
7673, 74, 75sylancl 644 . . . . 5
77 simprr 734 . . . . . . . 8
78 fveq2 5669 . . . . . . . . . . 11
7978eqeq1d 2396 . . . . . . . . . 10
8079elrab 3036 . . . . . . . . 9
8180simprbi 451 . . . . . . . 8
8277, 81syl 16 . . . . . . 7
8382ralrimivva 2742 . . . . . 6
84 invdisj 4143 . . . . . 6 Disj
8583, 84syl 16 . . . . 5 Disj
8661adantr 452 . . . . . . . 8
8774, 77sseldi 3290 . . . . . . . . 9
8887, 62syl 16 . . . . . . . 8
8986, 88, 63syl2anc 643 . . . . . . 7
9089, 65syl 16 . . . . . 6
9160, 90, 67sylancr 645 . . . . 5
9270, 76, 85, 91fsumiun 12528 . . . 4
9361adantr 452 . . . . . . . . . . . 12
94 elpwi 3751 . . . . . . . . . . . . 13
9594adantl 453 . . . . . . . . . . . 12
96 ssdomg 7090 . . . . . . . . . . . 12
9793, 95, 96sylc 58 . . . . . . . . . . 11
98 ssfi 7266 . . . . . . . . . . . . 13
9961, 94, 98syl2an 464 . . . . . . . . . . . 12
100 hashdom 11581 . . . . . . . . . . . 12
10199, 93, 100syl2anc 643 . . . . . . . . . . 11
10297, 101mpbird 224 . . . . . . . . . 10
103 hashcl 11567 . . . . . . . . . . . . 13
10499, 103syl 16 . . . . . . . . . . . 12
105 nn0uz 10453 . . . . . . . . . . . 12
106104, 105syl6eleq 2478 . . . . . . . . . . 11
107 hashcl 11567 . . . . . . . . . . . . . 14
10861, 107syl 16 . . . . . . . . . . . . 13
109108adantr 452 . . . . . . . . . . . 12
110109nn0zd 10306 . . . . . . . . . . 11
111 elfz5 10984 . . . . . . . . . . 11
112106, 110, 111syl2anc 643 . . . . . . . . . 10
113102, 112mpbird 224 . . . . . . . . 9
114 eqidd 2389 . . . . . . . . 9
115 eqeq2 2397 . . . . . . . . . 10
116115rspcev 2996 . . . . . . . . 9
117113, 114, 116syl2anc 643 . . . . . . . 8
118117ralrimiva 2733 . . . . . . 7
119 rabid2 2829 . . . . . . 7
120118, 119sylibr 204 . . . . . 6
121 iunrab 4080 . . . . . 6
122120, 121syl6reqr 2439 . . . . 5
123122sumeq1d 12423 . . . 4
124 elfznn0 11016 . . . . . . . . . 10
125124adantl 453 . . . . . . . . 9
126 expcl 11327 . . . . . . . . 9
12760, 125, 126sylancr 645 . . . . . . . 8
128 fsumconst 12501 . . . . . . . 8
12976, 127, 128syl2anc 643 . . . . . . 7
13081adantl 453 . . . . . . . . 9
131130oveq2d 6037 . . . . . . . 8
132131sumeq2dv 12425 . . . . . . 7
133 elfzelz 10992 . . . . . . . . 9
134 hashbc 11630 . . . . . . . . 9
13561, 133, 134syl2an 464 . . . . . . . 8
136135oveq1d 6036 . . . . . . 7
137129, 132, 1363eqtr4d 2430 . . . . . 6
138137sumeq2dv 12425 . . . . 5
139 ax-1cn 8982 . . . . . . . 8
140139negidi 9302 . . . . . . 7
141140oveq1i 6031 . . . . . 6
142 binom1p 12538 . . . . . . 7
14360, 108, 142sylancr 645 . . . . . 6
144141, 143syl5eqr 2434 . . . . 5
145 eqeq2 2397 . . . . . 6
146 eqeq2 2397 . . . . . 6
147 nprmdvds1 13039 . . . . . . . . . . . . 13
148 simpr 448 . . . . . . . . . . . . . . 15
149148breq2d 4166 . . . . . . . . . . . . . 14
150149notbid 286 . . . . . . . . . . . . 13
151147, 150syl5ibr 213 . . . . . . . . . . . 12
152151ralrimiv 2732 . . . . . . . . . . 11
153 rabeq0 3593 . . . . . . . . . . 11
154152, 153sylibr 204 . . . . . . . . . 10
155154fveq2d 5673 . . . . . . . . 9
156 hash0 11574 . . . . . . . . 9
157155, 156syl6eq 2436 . . . . . . . 8
158157oveq2d 6037 . . . . . . 7
159 0cn 9018 . . . . . . . 8
160 exp0 11314 . . . . . . . 8
161159, 160ax-mp 8 . . . . . . 7
162158, 161syl6eq 2436 . . . . . 6
163 df-ne 2553 . . . . . . . . . . 11
164 eluz2b3 10482 . . . . . . . . . . . 12
165164biimpri 198 . . . . . . . . . . 11
166163, 165sylan2br 463 . . . . . . . . . 10
167 exprmfct 13038 . . . . . . . . . 10
168166, 167syl 16 . . . . . . . . 9
169 rabn0 3591 . . . . . . . . 9
170168, 169sylibr 204 . . . . . . . 8
17161adantr 452 . . . . . . . . 9
172 hashnncl 11573 . . . . . . . . 9
173171, 172syl 16 . . . . . . . 8
174170, 173mpbird 224 . . . . . . 7
1751740expd 11467 . . . . . 6
176145, 146, 162, 175ifbothda 3713 . . . . 5
177138, 144, 1763eqtr2d 2426 . . . 4
17892, 123, 1773eqtr3d 2428 . . 3
17969, 178eqtr3d 2422 . 2
18010, 37, 1793eqtr3d 2428 1
 Colors of variables: wff set class Syntax hints:   wn 3   wi 4   wb 177   wa 359   wceq 1649   wcel 1717   wne 2551  wral 2650  wrex 2651  crab 2654   cdif 3261   wss 3264  c0 3572  cif 3683  cpw 3743  ciun 4036  Disj wdisj 4124   class class class wbr 4154   cmpt 4208  cfv 5395  (class class class)co 6021   cdom 7044  cfn 7046  cc 8922  cc0 8924  c1 8925   caddc 8927   cmul 8929   cle 9055  cneg 9225  cn 9933  c2 9982  cn0 10154  cz 10215  cuz 10421  cfz 10976  cexp 11310   cbc 11521  chash 11546  csu 12407   cdivides 12780  cprime 13007   cpc 13138  cmu 20745 This theorem is referenced by:  musumsum  20845  muinv  20846 This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1552  ax-5 1563  ax-17 1623  ax-9 1661  ax-8 1682  ax-13 1719  ax-14 1721  ax-6 1736  ax-7 1741  ax-11 1753  ax-12 1939  ax-ext 2369  ax-rep 4262  ax-sep 4272  ax-nul 4280  ax-pow 4319  ax-pr 4345  ax-un 4642  ax-inf2 7530  ax-cnex 8980  ax-resscn 8981  ax-1cn 8982  ax-icn 8983  ax-addcl 8984  ax-addrcl 8985  ax-mulcl 8986  ax-mulrcl 8987  ax-mulcom 8988  ax-addass 8989  ax-mulass 8990  ax-distr 8991  ax-i2m1 8992  ax-1ne0 8993  ax-1rid 8994  ax-rnegex 8995  ax-rrecex 8996  ax-cnre 8997  ax-pre-lttri 8998  ax-pre-lttrn 8999  ax-pre-ltadd 9000  ax-pre-mulgt0 9001  ax-pre-sup 9002 This theorem depends on definitions:  df-bi 178  df-or 360  df-an 361  df-3or 937  df-3an 938  df-tru 1325  df-ex 1548  df-nf 1551  df-sb 1656  df-eu 2243  df-mo 2244  df-clab 2375  df-cleq 2381  df-clel 2384  df-nfc 2513  df-ne 2553  df-nel 2554  df-ral 2655  df-rex 2656  df-reu 2657  df-rmo 2658  df-rab 2659  df-v 2902  df-sbc 3106  df-csb 3196  df-dif 3267  df-un 3269  df-in 3271  df-ss 3278  df-pss 3280  df-nul 3573  df-if 3684  df-pw 3745  df-sn 3764  df-pr 3765  df-tp 3766  df-op 3767  df-uni 3959  df-int 3994  df-iun 4038  df-disj 4125  df-br 4155  df-opab 4209  df-mpt 4210  df-tr 4245  df-eprel 4436  df-id 4440  df-po 4445  df-so 4446  df-fr 4483  df-se 4484  df-we 4485  df-ord 4526  df-on 4527  df-lim 4528  df-suc 4529  df-om 4787  df-xp 4825  df-rel 4826  df-cnv 4827  df-co 4828  df-dm 4829  df-rn 4830  df-res 4831  df-ima 4832  df-iota 5359  df-fun 5397  df-fn 5398  df-f 5399  df-f1 5400  df-fo 5401  df-f1o 5402  df-fv 5403  df-isom 5404  df-ov 6024  df-oprab 6025  df-mpt2 6026  df-1st 6289  df-2nd 6290  df-riota 6486  df-recs 6570  df-rdg 6605  df-1o 6661  df-2o 6662  df-oadd 6665  df-er 6842  df-map 6957  df-en 7047  df-dom 7048  df-sdom 7049  df-fin 7050  df-sup 7382  df-oi 7413  df-card 7760  df-cda 7982  df-pnf 9056  df-mnf 9057  df-xr 9058  df-ltxr 9059  df-le 9060  df-sub 9226  df-neg 9227  df-div 9611  df-nn 9934  df-2 9991  df-3 9992  df-n0 10155  df-z 10216  df-uz 10422  df-q 10508  df-rp 10546  df-fz 10977  df-fzo 11067  df-fl 11130  df-mod 11179  df-seq 11252  df-exp 11311  df-fac 11495  df-bc 11522  df-hash 11547  df-cj 11832  df-re 11833  df-im 11834  df-sqr 11968  df-abs 11969  df-clim 12210  df-sum 12408  df-dvds 12781  df-gcd 12935  df-prm 13008  df-pc 13139  df-mu 20751
 Copyright terms: Public domain W3C validator