Metamath Proof Explorer


Theorem fsumdvdsmul

Description: Product of two divisor sums. (This is also the main part of the proof that " sum_ k || N F ( k ) is a multiplicative function if F is".) (Contributed by Mario Carneiro, 2-Jul-2015)

Ref Expression
Hypotheses dvdsmulf1o.1 φ M
dvdsmulf1o.2 φ N
dvdsmulf1o.3 φ M gcd N = 1
dvdsmulf1o.x X = x | x M
dvdsmulf1o.y Y = x | x N
dvdsmulf1o.z Z = x | x M N
fsumdvdsmul.4 φ j X A
fsumdvdsmul.5 φ k Y B
fsumdvdsmul.6 φ j X k Y A B = D
fsumdvdsmul.7 i = j k C = D
Assertion fsumdvdsmul φ j X A k Y B = i Z C

Proof

Step Hyp Ref Expression
1 dvdsmulf1o.1 φ M
2 dvdsmulf1o.2 φ N
3 dvdsmulf1o.3 φ M gcd N = 1
4 dvdsmulf1o.x X = x | x M
5 dvdsmulf1o.y Y = x | x N
6 dvdsmulf1o.z Z = x | x M N
7 fsumdvdsmul.4 φ j X A
8 fsumdvdsmul.5 φ k Y B
9 fsumdvdsmul.6 φ j X k Y A B = D
10 fsumdvdsmul.7 i = j k C = D
11 fzfid φ 1 M Fin
12 dvdsssfz1 M x | x M 1 M
13 1 12 syl φ x | x M 1 M
14 4 13 eqsstrid φ X 1 M
15 11 14 ssfid φ X Fin
16 fzfid φ 1 N Fin
17 dvdsssfz1 N x | x N 1 N
18 2 17 syl φ x | x N 1 N
19 5 18 eqsstrid φ Y 1 N
20 16 19 ssfid φ Y Fin
21 20 8 fsumcl φ k Y B
22 15 21 7 fsummulc1 φ j X A k Y B = j X A k Y B
23 20 adantr φ j X Y Fin
24 8 adantlr φ j X k Y B
25 23 7 24 fsummulc2 φ j X A k Y B = k Y A B
26 9 anassrs φ j X k Y A B = D
27 26 sumeq2dv φ j X k Y A B = k Y D
28 25 27 eqtrd φ j X A k Y B = k Y D
29 28 sumeq2dv φ j X A k Y B = j X k Y D
30 fveq2 z = j k × z = × j k
31 df-ov j k = × j k
32 30 31 eqtr4di z = j k × z = j k
33 32 csbeq1d z = j k × z / i C = j k / i C
34 ovex j k V
35 34 10 csbie j k / i C = D
36 33 35 eqtrdi z = j k × z / i C = D
37 7 adantrr φ j X k Y A
38 8 adantrl φ j X k Y B
39 37 38 mulcld φ j X k Y A B
40 9 39 eqeltrrd φ j X k Y D
41 36 15 20 40 fsumxp φ j X k Y D = z X × Y × z / i C
42 nfcv _ w C
43 nfcsb1v _ i w / i C
44 csbeq1a i = w C = w / i C
45 42 43 44 cbvsumi i Z C = w Z w / i C
46 csbeq1 w = × z w / i C = × z / i C
47 xpfi X Fin Y Fin X × Y Fin
48 15 20 47 syl2anc φ X × Y Fin
49 1 2 3 4 5 6 dvdsmulf1o φ × X × Y : X × Y 1-1 onto Z
50 fvres z X × Y × X × Y z = × z
51 50 adantl φ z X × Y × X × Y z = × z
52 40 ralrimivva φ j X k Y D
53 36 eleq1d z = j k × z / i C D
54 53 ralxp z X × Y × z / i C j X k Y D
55 52 54 sylibr φ z X × Y × z / i C
56 ax-mulf × : ×
57 ffn × : × × Fn ×
58 56 57 ax-mp × Fn ×
59 4 ssrab3 X
60 nnsscn
61 59 60 sstri X
62 5 ssrab3 Y
63 62 60 sstri Y
64 xpss12 X Y X × Y ×
65 61 63 64 mp2an X × Y ×
66 46 eleq1d w = × z w / i C × z / i C
67 66 ralima × Fn × X × Y × w × X × Y w / i C z X × Y × z / i C
68 58 65 67 mp2an w × X × Y w / i C z X × Y × z / i C
69 df-ima × X × Y = ran × X × Y
70 f1ofo × X × Y : X × Y 1-1 onto Z × X × Y : X × Y onto Z
71 forn × X × Y : X × Y onto Z ran × X × Y = Z
72 49 70 71 3syl φ ran × X × Y = Z
73 69 72 syl5eq φ × X × Y = Z
74 73 raleqdv φ w × X × Y w / i C w Z w / i C
75 68 74 bitr3id φ z X × Y × z / i C w Z w / i C
76 55 75 mpbid φ w Z w / i C
77 76 r19.21bi φ w Z w / i C
78 46 48 49 51 77 fsumf1o φ w Z w / i C = z X × Y × z / i C
79 45 78 syl5eq φ i Z C = z X × Y × z / i C
80 41 79 eqtr4d φ j X k Y D = i Z C
81 22 29 80 3eqtrd φ j X A k Y B = i Z C