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) Avoid ax-mulf . (Revised by GG, 18-Apr-2025)

Ref Expression
Hypotheses mpodvdsmulf1o.1 
|- ( ph -> M e. NN )
mpodvdsmulf1o.2 
|- ( ph -> N e. NN )
mpodvdsmulf1o.3 
|- ( ph -> ( M gcd N ) = 1 )
mpodvdsmulf1o.x 
|- X = { x e. NN | x || M }
mpodvdsmulf1o.y 
|- Y = { x e. NN | x || N }
mpodvdsmulf1o.z 
|- Z = { x e. NN | x || ( M x. N ) }
fsumdvdsmul.4 
|- ( ( ph /\ j e. X ) -> A e. CC )
fsumdvdsmul.5 
|- ( ( ph /\ k e. Y ) -> B e. CC )
fsumdvdsmul.6 
|- ( ( ph /\ ( j e. X /\ k e. Y ) ) -> ( A x. B ) = D )
fsumdvdsmul.7 
|- ( i = ( j x. k ) -> C = D )
Assertion fsumdvdsmul 
|- ( ph -> ( sum_ j e. X A x. sum_ k e. Y B ) = sum_ i e. Z C )

Proof

Step Hyp Ref Expression
1 mpodvdsmulf1o.1 
 |-  ( ph -> M e. NN )
2 mpodvdsmulf1o.2 
 |-  ( ph -> N e. NN )
3 mpodvdsmulf1o.3 
 |-  ( ph -> ( M gcd N ) = 1 )
4 mpodvdsmulf1o.x 
 |-  X = { x e. NN | x || M }
5 mpodvdsmulf1o.y 
 |-  Y = { x e. NN | x || N }
6 mpodvdsmulf1o.z 
 |-  Z = { x e. NN | x || ( M x. N ) }
7 fsumdvdsmul.4 
 |-  ( ( ph /\ j e. X ) -> A e. CC )
8 fsumdvdsmul.5 
 |-  ( ( ph /\ k e. Y ) -> B e. CC )
9 fsumdvdsmul.6 
 |-  ( ( ph /\ ( j e. X /\ k e. Y ) ) -> ( A x. B ) = D )
10 fsumdvdsmul.7 
 |-  ( i = ( j x. k ) -> C = D )
11 fzfid 
 |-  ( ph -> ( 1 ... M ) e. Fin )
12 dvdsssfz1 
 |-  ( M e. NN -> { x e. NN | x || M } C_ ( 1 ... M ) )
13 1 12 syl 
 |-  ( ph -> { x e. NN | x || M } C_ ( 1 ... M ) )
14 4 13 eqsstrid 
 |-  ( ph -> X C_ ( 1 ... M ) )
15 11 14 ssfid 
 |-  ( ph -> X e. Fin )
16 fzfid 
 |-  ( ph -> ( 1 ... N ) e. Fin )
17 dvdsssfz1 
 |-  ( N e. NN -> { x e. NN | x || N } C_ ( 1 ... N ) )
18 2 17 syl 
 |-  ( ph -> { x e. NN | x || N } C_ ( 1 ... N ) )
19 5 18 eqsstrid 
 |-  ( ph -> Y C_ ( 1 ... N ) )
20 16 19 ssfid 
 |-  ( ph -> Y e. Fin )
21 20 8 fsumcl 
 |-  ( ph -> sum_ k e. Y B e. CC )
22 15 21 7 fsummulc1 
 |-  ( ph -> ( sum_ j e. X A x. sum_ k e. Y B ) = sum_ j e. X ( A x. sum_ k e. Y B ) )
23 20 adantr 
 |-  ( ( ph /\ j e. X ) -> Y e. Fin )
24 8 adantlr 
 |-  ( ( ( ph /\ j e. X ) /\ k e. Y ) -> B e. CC )
25 23 7 24 fsummulc2 
 |-  ( ( ph /\ j e. X ) -> ( A x. sum_ k e. Y B ) = sum_ k e. Y ( A x. B ) )
26 9 anassrs 
 |-  ( ( ( ph /\ j e. X ) /\ k e. Y ) -> ( A x. B ) = D )
27 26 sumeq2dv 
 |-  ( ( ph /\ j e. X ) -> sum_ k e. Y ( A x. B ) = sum_ k e. Y D )
28 25 27 eqtrd 
 |-  ( ( ph /\ j e. X ) -> ( A x. sum_ k e. Y B ) = sum_ k e. Y D )
29 28 sumeq2dv 
 |-  ( ph -> sum_ j e. X ( A x. sum_ k e. Y B ) = sum_ j e. X sum_ k e. Y D )
30 elxpi 
 |-  ( z e. ( X X. Y ) -> E. u E. v ( z = <. u , v >. /\ ( u e. X /\ v e. Y ) ) )
31 fveq2 
 |-  ( <. u , v >. = z -> ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` <. u , v >. ) = ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) )
32 31 eqcoms 
 |-  ( z = <. u , v >. -> ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` <. u , v >. ) = ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) )
33 fveq2 
 |-  ( <. u , v >. = z -> ( x. ` <. u , v >. ) = ( x. ` z ) )
34 33 eqcoms 
 |-  ( z = <. u , v >. -> ( x. ` <. u , v >. ) = ( x. ` z ) )
35 32 34 eqeq12d 
 |-  ( z = <. u , v >. -> ( ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` <. u , v >. ) = ( x. ` <. u , v >. ) <-> ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) = ( x. ` z ) ) )
36 35 biimpd 
 |-  ( z = <. u , v >. -> ( ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` <. u , v >. ) = ( x. ` <. u , v >. ) -> ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) = ( x. ` z ) ) )
37 4 ssrab3 
 |-  X C_ NN
38 nnsscn 
 |-  NN C_ CC
39 37 38 sstri 
 |-  X C_ CC
40 39 sseli 
 |-  ( u e. X -> u e. CC )
41 5 ssrab3 
 |-  Y C_ NN
42 41 38 sstri 
 |-  Y C_ CC
43 42 sseli 
 |-  ( v e. Y -> v e. CC )
44 ovmpot 
 |-  ( ( u e. CC /\ v e. CC ) -> ( u ( x e. CC , y e. CC |-> ( x x. y ) ) v ) = ( u x. v ) )
45 df-ov 
 |-  ( u ( x e. CC , y e. CC |-> ( x x. y ) ) v ) = ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` <. u , v >. )
46 df-ov 
 |-  ( u x. v ) = ( x. ` <. u , v >. )
47 44 45 46 3eqtr3g 
 |-  ( ( u e. CC /\ v e. CC ) -> ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` <. u , v >. ) = ( x. ` <. u , v >. ) )
48 40 43 47 syl2an 
 |-  ( ( u e. X /\ v e. Y ) -> ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` <. u , v >. ) = ( x. ` <. u , v >. ) )
49 36 48 impel 
 |-  ( ( z = <. u , v >. /\ ( u e. X /\ v e. Y ) ) -> ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) = ( x. ` z ) )
50 49 exlimivv 
 |-  ( E. u E. v ( z = <. u , v >. /\ ( u e. X /\ v e. Y ) ) -> ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) = ( x. ` z ) )
51 30 50 syl 
 |-  ( z e. ( X X. Y ) -> ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) = ( x. ` z ) )
52 51 eqcomd 
 |-  ( z e. ( X X. Y ) -> ( x. ` z ) = ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) )
53 52 csbeq1d 
 |-  ( z e. ( X X. Y ) -> [_ ( x. ` z ) / i ]_ C = [_ ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) / i ]_ C )
54 53 sumeq2i 
 |-  sum_ z e. ( X X. Y ) [_ ( x. ` z ) / i ]_ C = sum_ z e. ( X X. Y ) [_ ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) / i ]_ C
55 fveq2 
 |-  ( z = <. j , k >. -> ( x. ` z ) = ( x. ` <. j , k >. ) )
56 df-ov 
 |-  ( j x. k ) = ( x. ` <. j , k >. )
57 55 56 eqtr4di 
 |-  ( z = <. j , k >. -> ( x. ` z ) = ( j x. k ) )
58 57 csbeq1d 
 |-  ( z = <. j , k >. -> [_ ( x. ` z ) / i ]_ C = [_ ( j x. k ) / i ]_ C )
59 ovex 
 |-  ( j x. k ) e. _V
60 59 10 csbie 
 |-  [_ ( j x. k ) / i ]_ C = D
61 58 60 eqtrdi 
 |-  ( z = <. j , k >. -> [_ ( x. ` z ) / i ]_ C = D )
62 7 adantrr 
 |-  ( ( ph /\ ( j e. X /\ k e. Y ) ) -> A e. CC )
63 8 adantrl 
 |-  ( ( ph /\ ( j e. X /\ k e. Y ) ) -> B e. CC )
64 62 63 mulcld 
 |-  ( ( ph /\ ( j e. X /\ k e. Y ) ) -> ( A x. B ) e. CC )
65 9 64 eqeltrrd 
 |-  ( ( ph /\ ( j e. X /\ k e. Y ) ) -> D e. CC )
66 61 15 20 65 fsumxp 
 |-  ( ph -> sum_ j e. X sum_ k e. Y D = sum_ z e. ( X X. Y ) [_ ( x. ` z ) / i ]_ C )
67 csbeq1a 
 |-  ( i = w -> C = [_ w / i ]_ C )
68 nfcv 
 |-  F/_ w C
69 nfcsb1v 
 |-  F/_ i [_ w / i ]_ C
70 67 68 69 cbvsum 
 |-  sum_ i e. Z C = sum_ w e. Z [_ w / i ]_ C
71 csbeq1 
 |-  ( w = ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) -> [_ w / i ]_ C = [_ ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) / i ]_ C )
72 xpfi 
 |-  ( ( X e. Fin /\ Y e. Fin ) -> ( X X. Y ) e. Fin )
73 15 20 72 syl2anc 
 |-  ( ph -> ( X X. Y ) e. Fin )
74 1 2 3 4 5 6 mpodvdsmulf1o 
 |-  ( ph -> ( ( x e. CC , y e. CC |-> ( x x. y ) ) |` ( X X. Y ) ) : ( X X. Y ) -1-1-onto-> Z )
75 fvres 
 |-  ( z e. ( X X. Y ) -> ( ( ( x e. CC , y e. CC |-> ( x x. y ) ) |` ( X X. Y ) ) ` z ) = ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) )
76 75 adantl 
 |-  ( ( ph /\ z e. ( X X. Y ) ) -> ( ( ( x e. CC , y e. CC |-> ( x x. y ) ) |` ( X X. Y ) ) ` z ) = ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) )
77 65 ralrimivva 
 |-  ( ph -> A. j e. X A. k e. Y D e. CC )
78 61 eleq1d 
 |-  ( z = <. j , k >. -> ( [_ ( x. ` z ) / i ]_ C e. CC <-> D e. CC ) )
79 78 ralxp 
 |-  ( A. z e. ( X X. Y ) [_ ( x. ` z ) / i ]_ C e. CC <-> A. j e. X A. k e. Y D e. CC )
80 77 79 sylibr 
 |-  ( ph -> A. z e. ( X X. Y ) [_ ( x. ` z ) / i ]_ C e. CC )
81 fveq2 
 |-  ( z = w -> ( x. ` z ) = ( x. ` w ) )
82 81 csbeq1d 
 |-  ( z = w -> [_ ( x. ` z ) / i ]_ C = [_ ( x. ` w ) / i ]_ C )
83 82 eleq1d 
 |-  ( z = w -> ( [_ ( x. ` z ) / i ]_ C e. CC <-> [_ ( x. ` w ) / i ]_ C e. CC ) )
84 83 cbvralvw 
 |-  ( A. z e. ( X X. Y ) [_ ( x. ` z ) / i ]_ C e. CC <-> A. w e. ( X X. Y ) [_ ( x. ` w ) / i ]_ C e. CC )
85 id 
 |-  ( z e. ( X X. Y ) -> z e. ( X X. Y ) )
86 82 eqcoms 
 |-  ( w = z -> [_ ( x. ` z ) / i ]_ C = [_ ( x. ` w ) / i ]_ C )
87 86 adantl 
 |-  ( ( z e. ( X X. Y ) /\ w = z ) -> [_ ( x. ` z ) / i ]_ C = [_ ( x. ` w ) / i ]_ C )
88 87 eleq1d 
 |-  ( ( z e. ( X X. Y ) /\ w = z ) -> ( [_ ( x. ` z ) / i ]_ C e. CC <-> [_ ( x. ` w ) / i ]_ C e. CC ) )
89 53 eleq1d 
 |-  ( z e. ( X X. Y ) -> ( [_ ( x. ` z ) / i ]_ C e. CC <-> [_ ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) / i ]_ C e. CC ) )
90 89 adantr 
 |-  ( ( z e. ( X X. Y ) /\ w = z ) -> ( [_ ( x. ` z ) / i ]_ C e. CC <-> [_ ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) / i ]_ C e. CC ) )
91 88 90 bitr3d 
 |-  ( ( z e. ( X X. Y ) /\ w = z ) -> ( [_ ( x. ` w ) / i ]_ C e. CC <-> [_ ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) / i ]_ C e. CC ) )
92 85 91 rspcdv 
 |-  ( z e. ( X X. Y ) -> ( A. w e. ( X X. Y ) [_ ( x. ` w ) / i ]_ C e. CC -> [_ ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) / i ]_ C e. CC ) )
93 92 com12 
 |-  ( A. w e. ( X X. Y ) [_ ( x. ` w ) / i ]_ C e. CC -> ( z e. ( X X. Y ) -> [_ ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) / i ]_ C e. CC ) )
94 93 ralrimiv 
 |-  ( A. w e. ( X X. Y ) [_ ( x. ` w ) / i ]_ C e. CC -> A. z e. ( X X. Y ) [_ ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) / i ]_ C e. CC )
95 84 94 sylbi 
 |-  ( A. z e. ( X X. Y ) [_ ( x. ` z ) / i ]_ C e. CC -> A. z e. ( X X. Y ) [_ ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) / i ]_ C e. CC )
96 80 95 syl 
 |-  ( ph -> A. z e. ( X X. Y ) [_ ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) / i ]_ C e. CC )
97 mpomulf 
 |-  ( x e. CC , y e. CC |-> ( x x. y ) ) : ( CC X. CC ) --> CC
98 ffn 
 |-  ( ( x e. CC , y e. CC |-> ( x x. y ) ) : ( CC X. CC ) --> CC -> ( x e. CC , y e. CC |-> ( x x. y ) ) Fn ( CC X. CC ) )
99 97 98 ax-mp 
 |-  ( x e. CC , y e. CC |-> ( x x. y ) ) Fn ( CC X. CC )
100 xpss12 
 |-  ( ( X C_ CC /\ Y C_ CC ) -> ( X X. Y ) C_ ( CC X. CC ) )
101 39 42 100 mp2an 
 |-  ( X X. Y ) C_ ( CC X. CC )
102 71 eleq1d 
 |-  ( w = ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) -> ( [_ w / i ]_ C e. CC <-> [_ ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) / i ]_ C e. CC ) )
103 102 ralima 
 |-  ( ( ( x e. CC , y e. CC |-> ( x x. y ) ) Fn ( CC X. CC ) /\ ( X X. Y ) C_ ( CC X. CC ) ) -> ( A. w e. ( ( x e. CC , y e. CC |-> ( x x. y ) ) " ( X X. Y ) ) [_ w / i ]_ C e. CC <-> A. z e. ( X X. Y ) [_ ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) / i ]_ C e. CC ) )
104 99 101 103 mp2an 
 |-  ( A. w e. ( ( x e. CC , y e. CC |-> ( x x. y ) ) " ( X X. Y ) ) [_ w / i ]_ C e. CC <-> A. z e. ( X X. Y ) [_ ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) / i ]_ C e. CC )
105 df-ima 
 |-  ( ( x e. CC , y e. CC |-> ( x x. y ) ) " ( X X. Y ) ) = ran ( ( x e. CC , y e. CC |-> ( x x. y ) ) |` ( X X. Y ) )
106 f1ofo 
 |-  ( ( ( x e. CC , y e. CC |-> ( x x. y ) ) |` ( X X. Y ) ) : ( X X. Y ) -1-1-onto-> Z -> ( ( x e. CC , y e. CC |-> ( x x. y ) ) |` ( X X. Y ) ) : ( X X. Y ) -onto-> Z )
107 forn 
 |-  ( ( ( x e. CC , y e. CC |-> ( x x. y ) ) |` ( X X. Y ) ) : ( X X. Y ) -onto-> Z -> ran ( ( x e. CC , y e. CC |-> ( x x. y ) ) |` ( X X. Y ) ) = Z )
108 74 106 107 3syl 
 |-  ( ph -> ran ( ( x e. CC , y e. CC |-> ( x x. y ) ) |` ( X X. Y ) ) = Z )
109 105 108 eqtrid 
 |-  ( ph -> ( ( x e. CC , y e. CC |-> ( x x. y ) ) " ( X X. Y ) ) = Z )
110 109 raleqdv 
 |-  ( ph -> ( A. w e. ( ( x e. CC , y e. CC |-> ( x x. y ) ) " ( X X. Y ) ) [_ w / i ]_ C e. CC <-> A. w e. Z [_ w / i ]_ C e. CC ) )
111 104 110 bitr3id 
 |-  ( ph -> ( A. z e. ( X X. Y ) [_ ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) / i ]_ C e. CC <-> A. w e. Z [_ w / i ]_ C e. CC ) )
112 96 111 mpbid 
 |-  ( ph -> A. w e. Z [_ w / i ]_ C e. CC )
113 112 r19.21bi 
 |-  ( ( ph /\ w e. Z ) -> [_ w / i ]_ C e. CC )
114 71 73 74 76 113 fsumf1o 
 |-  ( ph -> sum_ w e. Z [_ w / i ]_ C = sum_ z e. ( X X. Y ) [_ ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) / i ]_ C )
115 70 114 eqtrid 
 |-  ( ph -> sum_ i e. Z C = sum_ z e. ( X X. Y ) [_ ( ( x e. CC , y e. CC |-> ( x x. y ) ) ` z ) / i ]_ C )
116 54 66 115 3eqtr4a 
 |-  ( ph -> sum_ j e. X sum_ k e. Y D = sum_ i e. Z C )
117 22 29 116 3eqtrd 
 |-  ( ph -> ( sum_ j e. X A x. sum_ k e. Y B ) = sum_ i e. Z C )