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

Theorem dvdsmulf1o 24109
 Description: If and are two coprime integers, multiplication forms a bijection from the set of pairs where and , to the set of divisors of . (Contributed by Mario Carneiro, 2-Jul-2015.)
Hypotheses
Ref Expression
dvdsmulf1o.1
dvdsmulf1o.2
dvdsmulf1o.3
dvdsmulf1o.x
dvdsmulf1o.y
dvdsmulf1o.z
Assertion
Ref Expression
dvdsmulf1o
Distinct variable groups:   ,   ,
Allowed substitution hints:   ()   ()   ()   ()

Proof of Theorem dvdsmulf1o
Dummy variables are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 ax-mulf 9619 . . . . . . 7
2 ffn 5742 . . . . . . 7
31, 2ax-mp 5 . . . . . 6
4 dvdsmulf1o.x . . . . . . . . 9
5 ssrab2 3546 . . . . . . . . 9
64, 5eqsstri 3494 . . . . . . . 8
7 nnsscn 10614 . . . . . . . 8
86, 7sstri 3473 . . . . . . 7
9 dvdsmulf1o.y . . . . . . . . 9
10 ssrab2 3546 . . . . . . . . 9
119, 10eqsstri 3494 . . . . . . . 8
1211, 7sstri 3473 . . . . . . 7
13 xpss12 4955 . . . . . . 7
148, 12, 13mp2an 676 . . . . . 6
15 fnssres 5703 . . . . . 6
163, 14, 15mp2an 676 . . . . 5
1716a1i 11 . . . 4
18 ovres 6446 . . . . . . 7
1918adantl 467 . . . . . 6
20 breq1 4423 . . . . . . . . . . 11
2120, 4elrab2 3231 . . . . . . . . . 10
2221simplbi 461 . . . . . . . . 9
2322ad2antrl 732 . . . . . . . 8
24 breq1 4423 . . . . . . . . . . 11
2524, 9elrab2 3231 . . . . . . . . . 10
2625simplbi 461 . . . . . . . . 9
2726ad2antll 733 . . . . . . . 8
2823, 27nnmulcld 10657 . . . . . . 7
2925simprbi 465 . . . . . . . . 9
3029ad2antll 733 . . . . . . . 8
3121simprbi 465 . . . . . . . . 9
3231ad2antrl 732 . . . . . . . 8
3327nnzd 11039 . . . . . . . . . 10
34 dvdsmulf1o.2 . . . . . . . . . . . 12
3534adantr 466 . . . . . . . . . . 11
3635nnzd 11039 . . . . . . . . . 10
3723nnzd 11039 . . . . . . . . . 10
38 dvdscmul 14316 . . . . . . . . . 10
3933, 36, 37, 38syl3anc 1264 . . . . . . . . 9
40 dvdsmulf1o.1 . . . . . . . . . . . 12
4140adantr 466 . . . . . . . . . . 11
4241nnzd 11039 . . . . . . . . . 10
43 dvdsmulc 14317 . . . . . . . . . 10
4437, 42, 36, 43syl3anc 1264 . . . . . . . . 9
4528nnzd 11039 . . . . . . . . . 10
4637, 36zmulcld 11046 . . . . . . . . . 10
4742, 36zmulcld 11046 . . . . . . . . . 10
48 dvdstr 14324 . . . . . . . . . 10
4945, 46, 47, 48syl3anc 1264 . . . . . . . . 9
5039, 44, 49syl2and 485 . . . . . . . 8
5130, 32, 50mp2and 683 . . . . . . 7
52 breq1 4423 . . . . . . . 8
53 dvdsmulf1o.z . . . . . . . 8
5452, 53elrab2 3231 . . . . . . 7
5528, 51, 54sylanbrc 668 . . . . . 6
5619, 55eqeltrd 2510 . . . . 5
5756ralrimivva 2846 . . . 4
58 ffnov 6410 . . . 4
5917, 57, 58sylanbrc 668 . . 3
6023adantr 466 . . . . . . . . . 10
6160nnnn0d 10925 . . . . . . . . 9
62 simprll 770 . . . . . . . . . . 11
63 breq1 4423 . . . . . . . . . . . . 13
6463, 4elrab2 3231 . . . . . . . . . . . 12
6564simplbi 461 . . . . . . . . . . 11
6662, 65syl 17 . . . . . . . . . 10
6766nnnn0d 10925 . . . . . . . . 9
6860nnzd 11039 . . . . . . . . . . . 12
6927adantr 466 . . . . . . . . . . . . 13
7069nnzd 11039 . . . . . . . . . . . 12
71 dvdsmul1 14311 . . . . . . . . . . . 12
7268, 70, 71syl2anc 665 . . . . . . . . . . 11
73 simprr 764 . . . . . . . . . . . 12
748, 62sseldi 3462 . . . . . . . . . . . . 13
75 simprlr 771 . . . . . . . . . . . . . . 15
76 breq1 4423 . . . . . . . . . . . . . . . . 17
7776, 9elrab2 3231 . . . . . . . . . . . . . . . 16
7877simplbi 461 . . . . . . . . . . . . . . 15
7975, 78syl 17 . . . . . . . . . . . . . 14
8079nncnd 10625 . . . . . . . . . . . . 13
8174, 80mulcomd 9664 . . . . . . . . . . . 12
8273, 81eqtrd 2463 . . . . . . . . . . 11
8372, 82breqtrd 4445 . . . . . . . . . 10
8479nnzd 11039 . . . . . . . . . . 11
8536adantr 466 . . . . . . . . . . 11
86 gcdcom 14471 . . . . . . . . . . . . 13
8768, 85, 86syl2anc 665 . . . . . . . . . . . 12
8842adantr 466 . . . . . . . . . . . . 13
8934nnzd 11039 . . . . . . . . . . . . . . . 16
9040nnzd 11039 . . . . . . . . . . . . . . . 16
91 gcdcom 14471 . . . . . . . . . . . . . . . 16
9289, 90, 91syl2anc 665 . . . . . . . . . . . . . . 15
93 dvdsmulf1o.3 . . . . . . . . . . . . . . 15
9492, 93eqtrd 2463 . . . . . . . . . . . . . 14
9594ad2antrr 730 . . . . . . . . . . . . 13
9632adantr 466 . . . . . . . . . . . . 13
97 rpdvds 14663 . . . . . . . . . . . . 13
9885, 68, 88, 95, 96, 97syl32anc 1272 . . . . . . . . . . . 12
9987, 98eqtrd 2463 . . . . . . . . . . 11
10077simprbi 465 . . . . . . . . . . . 12
10175, 100syl 17 . . . . . . . . . . 11
102 rpdvds 14663 . . . . . . . . . . 11
10368, 84, 85, 99, 101, 102syl32anc 1272 . . . . . . . . . 10
10466nnzd 11039 . . . . . . . . . . 11
105 coprmdvds 14646 . . . . . . . . . . 11
10668, 84, 104, 105syl3anc 1264 . . . . . . . . . 10
10783, 103, 106mp2and 683 . . . . . . . . 9
108 dvdsmul1 14311 . . . . . . . . . . . 12
109104, 84, 108syl2anc 665 . . . . . . . . . . 11
11060nncnd 10625 . . . . . . . . . . . . 13
11169nncnd 10625 . . . . . . . . . . . . 13
112110, 111mulcomd 9664 . . . . . . . . . . . 12
11373, 112eqtr3d 2465 . . . . . . . . . . 11
114109, 113breqtrd 4445 . . . . . . . . . 10
115 gcdcom 14471 . . . . . . . . . . . . 13
116104, 85, 115syl2anc 665 . . . . . . . . . . . 12
11764simprbi 465 . . . . . . . . . . . . . 14
11862, 117syl 17 . . . . . . . . . . . . 13
119 rpdvds 14663 . . . . . . . . . . . . 13
12085, 104, 88, 95, 118, 119syl32anc 1272 . . . . . . . . . . . 12
121116, 120eqtrd 2463 . . . . . . . . . . 11
12230adantr 466 . . . . . . . . . . 11
123 rpdvds 14663 . . . . . . . . . . 11
124104, 70, 85, 121, 122, 123syl32anc 1272 . . . . . . . . . 10
125 coprmdvds 14646 . . . . . . . . . . 11
126104, 70, 68, 125syl3anc 1264 . . . . . . . . . 10
127114, 124, 126mp2and 683 . . . . . . . . 9
128 dvdseq 14339 . . . . . . . . 9
12961, 67, 107, 127, 128syl22anc 1265 . . . . . . . 8
13060nnne0d 10654 . . . . . . . . 9
131129oveq1d 6316 . . . . . . . . . 10
13273, 131eqtr4d 2466 . . . . . . . . 9
133111, 80, 110, 130, 132mulcanad 10247 . . . . . . . 8
134129, 133opeq12d 4192 . . . . . . 7
135134expr 618 . . . . . 6
136135ralrimivva 2846 . . . . 5
137136ralrimivva 2846 . . . 4
138 fvres 5891 . . . . . . . . 9
139 fvres 5891 . . . . . . . . 9
140138, 139eqeqan12d 2445 . . . . . . . 8
141140imbi1d 318 . . . . . . 7
142141ralbidva 2861 . . . . . 6
143142ralbiia 2855 . . . . 5
144 fveq2 5877 . . . . . . . . . . 11
145 df-ov 6304 . . . . . . . . . . 11
146144, 145syl6eqr 2481 . . . . . . . . . 10
147146eqeq2d 2436 . . . . . . . . 9
148 eqeq2 2437 . . . . . . . . 9
149147, 148imbi12d 321 . . . . . . . 8
150149ralxp 4991 . . . . . . 7
151 fveq2 5877 . . . . . . . . . . 11
152 df-ov 6304 . . . . . . . . . . 11
153151, 152syl6eqr 2481 . . . . . . . . . 10
154153eqeq1d 2424 . . . . . . . . 9
155 eqeq1 2426 . . . . . . . . 9
156154, 155imbi12d 321 . . . . . . . 8
1571562ralbidv 2869 . . . . . . 7
158150, 157syl5bb 260 . . . . . 6
159158ralxp 4991 . . . . 5
160143, 159bitri 252 . . . 4
161137, 160sylibr 215 . . 3
162 dff13 6170 . . 3
16359, 161, 162sylanbrc 668 . 2
164 breq1 4423 . . . . . . . . . . . 12
165164, 53elrab2 3231 . . . . . . . . . . 11
166165simplbi 461 . . . . . . . . . 10
167166adantl 467 . . . . . . . . 9
168167nnzd 11039 . . . . . . . 8
16940adantr 466 . . . . . . . . 9
170169nnzd 11039 . . . . . . . 8
171169nnne0d 10654 . . . . . . . . 9
172 simpr 462 . . . . . . . . . 10
173172necon3ai 2652 . . . . . . . . 9
174171, 173syl 17 . . . . . . . 8
175 gcdn0cl 14463 . . . . . . . 8
176168, 170, 174, 175syl21anc 1263 . . . . . . 7
177 gcddvds 14464 . . . . . . . . 9
178168, 170, 177syl2anc 665 . . . . . . . 8
179178simprd 464 . . . . . . 7
180 breq1 4423 . . . . . . . 8
181180, 4elrab2 3231 . . . . . . 7
182176, 179, 181sylanbrc 668 . . . . . 6
18334adantr 466 . . . . . . . . 9
184183nnzd 11039 . . . . . . . 8
185183nnne0d 10654 . . . . . . . . 9
186 simpr 462 . . . . . . . . . 10
187186necon3ai 2652 . . . . . . . . 9
188185, 187syl 17 . . . . . . . 8
189 gcdn0cl 14463 . . . . . . . 8
190168, 184, 188, 189syl21anc 1263 . . . . . . 7
191 gcddvds 14464 . . . . . . . . 9
192168, 184, 191syl2anc 665 . . . . . . . 8
193192simprd 464 . . . . . . 7
194 breq1 4423 . . . . . . . 8
195194, 9elrab2 3231 . . . . . . 7
196190, 193, 195sylanbrc 668 . . . . . 6
197 opelxpi 4881 . . . . . 6
198182, 196, 197syl2anc 665 . . . . 5
199 fvres 5891 . . . . . . 7
200198, 199syl 17 . . . . . 6
20193adantr 466 . . . . . . . 8
202 rpmulgcd2 14649 . . . . . . . 8
203168, 170, 184, 201, 202syl31anc 1267 . . . . . . 7
204 df-ov 6304 . . . . . . 7
205203, 204syl6eq 2479 . . . . . 6
206165simprbi 465 . . . . . . . 8
207206adantl 467 . . . . . . 7
20840, 34nnmulcld 10657 . . . . . . . 8
209 gcdeq 14507 . . . . . . . 8
210166, 208, 209syl2anr 480 . . . . . . 7
211207, 210mpbird 235 . . . . . 6
212200, 205, 2113eqtr2rd 2470 . . . . 5
213 fveq2 5877 . . . . . . 7
214213eqeq2d 2436 . . . . . 6
215214rspcev 3182 . . . . 5
216198, 212, 215syl2anc 665 . . . 4
217216ralrimiva 2839 . . 3
218 dffo3 6048 . . 3
21959, 217, 218sylanbrc 668 . 2
220 df-f1o 5604 . 2
221163, 219, 220sylanbrc 668 1
 Colors of variables: wff setvar class Syntax hints:   wn 3   wi 4   wb 187   wa 370   wceq 1437   wcel 1868   wne 2618  wral 2775  wrex 2776  crab 2779   wss 3436  cop 4002   class class class wbr 4420   cxp 4847   cres 4851   wfn 5592  wf 5593  wf1 5594  wfo 5595  wf1o 5596  cfv 5597  (class class class)co 6301  cc 9537  cc0 9539  c1 9540   cmul 9544  cn 10609  cn0 10869  cz 10937   cdvds 14292   cgcd 14455 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1665  ax-4 1678  ax-5 1748  ax-6 1794  ax-7 1839  ax-8 1870  ax-9 1872  ax-10 1887  ax-11 1892  ax-12 1905  ax-13 2053  ax-ext 2400  ax-sep 4543  ax-nul 4551  ax-pow 4598  ax-pr 4656  ax-un 6593  ax-cnex 9595  ax-resscn 9596  ax-1cn 9597  ax-icn 9598  ax-addcl 9599  ax-addrcl 9600  ax-mulcl 9601  ax-mulrcl 9602  ax-mulcom 9603  ax-addass 9604  ax-mulass 9605  ax-distr 9606  ax-i2m1 9607  ax-1ne0 9608  ax-1rid 9609  ax-rnegex 9610  ax-rrecex 9611  ax-cnre 9612  ax-pre-lttri 9613  ax-pre-lttrn 9614  ax-pre-ltadd 9615  ax-pre-mulgt0 9616  ax-pre-sup 9617  ax-mulf 9619 This theorem depends on definitions:  df-bi 188  df-or 371  df-an 372  df-3or 983  df-3an 984  df-tru 1440  df-ex 1660  df-nf 1664  df-sb 1787  df-eu 2269  df-mo 2270  df-clab 2408  df-cleq 2414  df-clel 2417  df-nfc 2572  df-ne 2620  df-nel 2621  df-ral 2780  df-rex 2781  df-reu 2782  df-rmo 2783  df-rab 2784  df-v 3083  df-sbc 3300  df-csb 3396  df-dif 3439  df-un 3441  df-in 3443  df-ss 3450  df-pss 3452  df-nul 3762  df-if 3910  df-pw 3981  df-sn 3997  df-pr 3999  df-tp 4001  df-op 4003  df-uni 4217  df-iun 4298  df-br 4421  df-opab 4480  df-mpt 4481  df-tr 4516  df-eprel 4760  df-id 4764  df-po 4770  df-so 4771  df-fr 4808  df-we 4810  df-xp 4855  df-rel 4856  df-cnv 4857  df-co 4858  df-dm 4859  df-rn 4860  df-res 4861  df-ima 4862  df-pred 5395  df-ord 5441  df-on 5442  df-lim 5443  df-suc 5444  df-iota 5561  df-fun 5599  df-fn 5600  df-f 5601  df-f1 5602  df-fo 5603  df-f1o 5604  df-fv 5605  df-riota 6263  df-ov 6304  df-oprab 6305  df-mpt2 6306  df-om 6703  df-2nd 6804  df-wrecs 7032  df-recs 7094  df-rdg 7132  df-er 7367  df-en 7574  df-dom 7575  df-sdom 7576  df-sup 7958  df-inf 7959  df-pnf 9677  df-mnf 9678  df-xr 9679  df-ltxr 9680  df-le 9681  df-sub 9862  df-neg 9863  df-div 10270  df-nn 10610  df-2 10668  df-3 10669  df-n0 10870  df-z 10938  df-uz 11160  df-rp 11303  df-fl 12027  df-mod 12096  df-seq 12213  df-exp 12272  df-cj 13150  df-re 13151  df-im 13152  df-sqrt 13286  df-abs 13287  df-dvds 14293  df-gcd 14456 This theorem is referenced by:  fsumdvdsmul  24110
 Copyright terms: Public domain W3C validator