Intuitionistic Logic Explorer < Previous   Next > Nearby theorems Mirrors  >  Home  >  ILE Home  >  Th. List  >  crth Unicode version

Theorem crth 11934
 Description: The Chinese Remainder Theorem: the function that maps to its remainder classes and is 1-1 and onto when and are coprime. (Contributed by Mario Carneiro, 24-Feb-2014.) (Proof shortened by Mario Carneiro, 2-May-2016.)
Hypotheses
Ref Expression
crth.1 ..^
crth.2 ..^ ..^
crth.3
crth.4
Assertion
Ref Expression
crth
Distinct variable groups:   ,   ,   ,   ,   ,
Allowed substitution hint:   ()

Proof of Theorem crth
Dummy variables are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 elfzoelz 9954 . . . . . 6 ..^
2 crth.1 . . . . . 6 ..^
31, 2eleq2s 2235 . . . . 5
4 simpr 109 . . . . . . . 8
5 crth.4 . . . . . . . . . 10
65simp1d 994 . . . . . . . . 9
76adantr 274 . . . . . . . 8
8 zmodfzo 10150 . . . . . . . 8 ..^
94, 7, 8syl2anc 409 . . . . . . 7 ..^
105simp2d 995 . . . . . . . . 9
1110adantr 274 . . . . . . . 8
12 zmodfzo 10150 . . . . . . . 8 ..^
134, 11, 12syl2anc 409 . . . . . . 7 ..^
14 opelxpi 4578 . . . . . . 7 ..^ ..^ ..^ ..^
159, 13, 14syl2anc 409 . . . . . 6 ..^ ..^
16 crth.2 . . . . . 6 ..^ ..^
1715, 16eleqtrrdi 2234 . . . . 5
183, 17sylan2 284 . . . 4
19 crth.3 . . . 4
2018, 19fmptd 5581 . . 3
21 simprl 521 . . . . . . . 8
22 elfzoelz 9954 . . . . . . . . . . . . 13 ..^
2322, 2eleq2s 2235 . . . . . . . . . . . 12
2423ad2antrl 482 . . . . . . . . . . 11
25 zq 9444 . . . . . . . . . . 11
2624, 25syl 14 . . . . . . . . . 10
276adantr 274 . . . . . . . . . . 11
28 nnq 9451 . . . . . . . . . . 11
2927, 28syl 14 . . . . . . . . . 10
3027nngt0d 8787 . . . . . . . . . 10
3126, 29, 30modqcld 10131 . . . . . . . . 9
3210adantr 274 . . . . . . . . . . 11
33 nnq 9451 . . . . . . . . . . 11
3432, 33syl 14 . . . . . . . . . 10
3532nngt0d 8787 . . . . . . . . . 10
3626, 34, 35modqcld 10131 . . . . . . . . 9
37 opexg 4157 . . . . . . . . 9
3831, 36, 37syl2anc 409 . . . . . . . 8
39 oveq1 5788 . . . . . . . . . 10
40 oveq1 5788 . . . . . . . . . 10
4139, 40opeq12d 3720 . . . . . . . . 9
4241, 19fvmptg 5504 . . . . . . . 8
4321, 38, 42syl2anc 409 . . . . . . 7
44 simprr 522 . . . . . . . 8
45 elfzoelz 9954 . . . . . . . . . . . . 13 ..^
4645, 2eleq2s 2235 . . . . . . . . . . . 12
4744, 46syl 14 . . . . . . . . . . 11
48 zq 9444 . . . . . . . . . . 11
4947, 48syl 14 . . . . . . . . . 10
5049, 29, 30modqcld 10131 . . . . . . . . 9
5149, 34, 35modqcld 10131 . . . . . . . . 9
52 opexg 4157 . . . . . . . . 9
5350, 51, 52syl2anc 409 . . . . . . . 8
54 oveq1 5788 . . . . . . . . . 10
55 oveq1 5788 . . . . . . . . . 10
5654, 55opeq12d 3720 . . . . . . . . 9
5756, 19fvmptg 5504 . . . . . . . 8
5844, 53, 57syl2anc 409 . . . . . . 7
5943, 58eqeq12d 2155 . . . . . 6
60 opthg 4167 . . . . . . 7
6131, 36, 60syl2anc 409 . . . . . 6
6259, 61bitrd 187 . . . . 5
6327nnzd 9195 . . . . . . 7
6432nnzd 9195 . . . . . . 7
6521, 2eleqtrdi 2233 . . . . . . . . 9 ..^
6665, 22syl 14 . . . . . . . 8
6744, 2eleqtrdi 2233 . . . . . . . . 9 ..^
6867, 45syl 14 . . . . . . . 8
6966, 68zsubcld 9201 . . . . . . 7
705simp3d 996 . . . . . . . 8
7170adantr 274 . . . . . . 7
72 coprmdvds2 11808 . . . . . . 7
7363, 64, 69, 71, 72syl31anc 1220 . . . . . 6
74 moddvds 11536 . . . . . . . 8
7527, 66, 68, 74syl3anc 1217 . . . . . . 7
76 moddvds 11536 . . . . . . . 8
7732, 66, 68, 76syl3anc 1217 . . . . . . 7
7875, 77anbi12d 465 . . . . . 6
79 qmulcl 9455 . . . . . . . . . 10
8029, 34, 79syl2anc 409 . . . . . . . . 9
81 elfzole1 9962 . . . . . . . . . 10 ..^
8265, 81syl 14 . . . . . . . . 9
83 elfzolt2 9963 . . . . . . . . . 10 ..^
8465, 83syl 14 . . . . . . . . 9
85 modqid 10152 . . . . . . . . 9
8626, 80, 82, 84, 85syl22anc 1218 . . . . . . . 8
87 elfzole1 9962 . . . . . . . . . 10 ..^
8867, 87syl 14 . . . . . . . . 9
89 elfzolt2 9963 . . . . . . . . . 10 ..^
9067, 89syl 14 . . . . . . . . 9
91 modqid 10152 . . . . . . . . 9
9249, 80, 88, 90, 91syl22anc 1218 . . . . . . . 8
9386, 92eqeq12d 2155 . . . . . . 7
9427, 32nnmulcld 8792 . . . . . . . 8
95 moddvds 11536 . . . . . . . 8
9694, 66, 68, 95syl3anc 1217 . . . . . . 7
9793, 96bitr3d 189 . . . . . 6
9873, 78, 973imtr4d 202 . . . . 5
9962, 98sylbid 149 . . . 4
10099ralrimivva 2517 . . 3
101 dff13 5676 . . 3
10220, 100, 101sylanbrc 414 . 2
103 nnnn0 9007 . . . . . 6
104 nnnn0 9007 . . . . . 6
105 hashfzo0 10600 . . . . . . . . 9 ..^
106 hashfzo0 10600 . . . . . . . . 9 ..^
107105, 106oveqan12d 5800 . . . . . . . 8 ..^ ..^
108 0z 9088 . . . . . . . . . 10
109 simpl 108 . . . . . . . . . . 11
110109nn0zd 9194 . . . . . . . . . 10
111 fzofig 10235 . . . . . . . . . 10 ..^
112108, 110, 111sylancr 411 . . . . . . . . 9 ..^
113 nn0z 9097 . . . . . . . . . . 11
114113adantl 275 . . . . . . . . . 10
115 fzofig 10235 . . . . . . . . . 10 ..^
116108, 114, 115sylancr 411 . . . . . . . . 9 ..^
117 hashxp 10603 . . . . . . . . 9 ..^ ..^ ..^ ..^ ..^ ..^
118112, 116, 117syl2anc 409 . . . . . . . 8 ..^ ..^ ..^ ..^
119 nn0mulcl 9036 . . . . . . . . 9
120 hashfzo0 10600 . . . . . . . . 9 ..^
121119, 120syl 14 . . . . . . . 8 ..^
122107, 118, 1213eqtr4rd 2184 . . . . . . 7 ..^ ..^ ..^
123119nn0zd 9194 . . . . . . . . 9
124 fzofig 10235 . . . . . . . . 9 ..^
125108, 123, 124sylancr 411 . . . . . . . 8 ..^
126 xpfi 6825 . . . . . . . . 9 ..^ ..^ ..^ ..^
127112, 116, 126syl2anc 409 . . . . . . . 8 ..^ ..^
128 hashen 10561 . . . . . . . 8 ..^ ..^ ..^ ..^ ..^ ..^ ..^ ..^ ..^
129125, 127, 128syl2anc 409 . . . . . . 7 ..^ ..^ ..^ ..^ ..^ ..^
130122, 129mpbid 146 . . . . . 6 ..^ ..^ ..^
131103, 104, 130syl2an 287 . . . . 5 ..^ ..^ ..^
1326, 10, 131syl2anc 409 . . . 4 ..^ ..^ ..^
133132, 2, 163brtr4g 3969 . . 3
1346nnnn0d 9053 . . . . 5
13510nnnn0d 9053 . . . . 5
136134, 135, 127syl2anc 409 . . . 4 ..^ ..^
13716, 136eqeltrid 2227 . . 3
138 f1finf1o 6842 . . 3
139133, 137, 138syl2anc 409 . 2
140102, 139mpbid 146 1
 Colors of variables: wff set class Syntax hints:   wi 4   wa 103   wb 104   w3a 963   wceq 1332   wcel 1481  wral 2417  cvv 2689  cop 3534   class class class wbr 3936   cmpt 3996   cxp 4544  wf 5126  wf1 5127  wf1o 5129  cfv 5130  (class class class)co 5781   cen 6639  cfn 6641  cc0 7643  c1 7644   cmul 7648   clt 7823   cle 7824   cmin 7956  cn 8743  cn0 9000  cz 9077  cq 9437  ..^cfzo 9949   cmo 10125  ♯chash 10552   cdvds 11527   cgcd 11669 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 105  ax-ia2 106  ax-ia3 107  ax-in1 604  ax-in2 605  ax-io 699  ax-5 1424  ax-7 1425  ax-gen 1426  ax-ie1 1470  ax-ie2 1471  ax-8 1483  ax-10 1484  ax-11 1485  ax-i12 1486  ax-bndl 1487  ax-4 1488  ax-13 1492  ax-14 1493  ax-17 1507  ax-i9 1511  ax-ial 1515  ax-i5r 1516  ax-ext 2122  ax-coll 4050  ax-sep 4053  ax-nul 4061  ax-pow 4105  ax-pr 4138  ax-un 4362  ax-setind 4459  ax-iinf 4509  ax-cnex 7734  ax-resscn 7735  ax-1cn 7736  ax-1re 7737  ax-icn 7738  ax-addcl 7739  ax-addrcl 7740  ax-mulcl 7741  ax-mulrcl 7742  ax-addcom 7743  ax-mulcom 7744  ax-addass 7745  ax-mulass 7746  ax-distr 7747  ax-i2m1 7748  ax-0lt1 7749  ax-1rid 7750  ax-0id 7751  ax-rnegex 7752  ax-precex 7753  ax-cnre 7754  ax-pre-ltirr 7755  ax-pre-ltwlin 7756  ax-pre-lttrn 7757  ax-pre-apti 7758  ax-pre-ltadd 7759  ax-pre-mulgt0 7760  ax-pre-mulext 7761  ax-arch 7762  ax-caucvg 7763 This theorem depends on definitions:  df-bi 116  df-dc 821  df-3or 964  df-3an 965  df-tru 1335  df-fal 1338  df-nf 1438  df-sb 1737  df-eu 2003  df-mo 2004  df-clab 2127  df-cleq 2133  df-clel 2136  df-nfc 2271  df-ne 2310  df-nel 2405  df-ral 2422  df-rex 2423  df-reu 2424  df-rmo 2425  df-rab 2426  df-v 2691  df-sbc 2913  df-csb 3007  df-dif 3077  df-un 3079  df-in 3081  df-ss 3088  df-nul 3368  df-if 3479  df-pw 3516  df-sn 3537  df-pr 3538  df-op 3540  df-uni 3744  df-int 3779  df-iun 3822  df-br 3937  df-opab 3997  df-mpt 3998  df-tr 4034  df-id 4222  df-po 4225  df-iso 4226  df-iord 4295  df-on 4297  df-ilim 4298  df-suc 4300  df-iom 4512  df-xp 4552  df-rel 4553  df-cnv 4554  df-co 4555  df-dm 4556  df-rn 4557  df-res 4558  df-ima 4559  df-iota 5095  df-fun 5132  df-fn 5133  df-f 5134  df-f1 5135  df-fo 5136  df-f1o 5137  df-fv 5138  df-riota 5737  df-ov 5784  df-oprab 5785  df-mpo 5786  df-1st 6045  df-2nd 6046  df-recs 6209  df-irdg 6274  df-frec 6295  df-1o 6320  df-oadd 6324  df-er 6436  df-en 6642  df-dom 6643  df-fin 6644  df-sup 6878  df-pnf 7825  df-mnf 7826  df-xr 7827  df-ltxr 7828  df-le 7829  df-sub 7958  df-neg 7959  df-reap 8360  df-ap 8367  df-div 8456  df-inn 8744  df-2 8802  df-3 8803  df-4 8804  df-n0 9001  df-z 9078  df-uz 9350  df-q 9438  df-rp 9470  df-fz 9821  df-fzo 9950  df-fl 10073  df-mod 10126  df-seqfrec 10249  df-exp 10323  df-ihash 10553  df-cj 10645  df-re 10646  df-im 10647  df-rsqrt 10801  df-abs 10802  df-dvds 11528  df-gcd 11670 This theorem is referenced by:  phimullem  11935
 Copyright terms: Public domain W3C validator