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

Theorem hashdvds 14305
Description: The number of numbers in a given residue class in a finite set of integers. (Contributed by Mario Carneiro, 12-Mar-2014.) (Proof shortened by Mario Carneiro, 7-Jun-2016.)
Hypotheses
Ref Expression
hashdvds.1
hashdvds.2
hashdvds.3
hashdvds.4
Assertion
Ref Expression
hashdvds
Distinct variable groups:   ,   ,   ,   ,N

Proof of Theorem hashdvds
Dummy variables are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 1zzd 10920 . . . . . 6
2 hashdvds.3 . . . . . . . . . . . 12
3 eluzelz 11119 . . . . . . . . . . . 12
42, 3syl 16 . . . . . . . . . . 11
5 hashdvds.4 . . . . . . . . . . 11
64, 5zsubcld 10999 . . . . . . . . . 10
76zred 10994 . . . . . . . . 9
8 hashdvds.1 . . . . . . . . 9
97, 8nndivred 10609 . . . . . . . 8
109flcld 11935 . . . . . . 7
11 hashdvds.2 . . . . . . . . . . . 12
12 peano2zm 10932 . . . . . . . . . . . 12
1311, 12syl 16 . . . . . . . . . . 11
1413, 5zsubcld 10999 . . . . . . . . . 10
1514zred 10994 . . . . . . . . 9
1615, 8nndivred 10609 . . . . . . . 8
1716flcld 11935 . . . . . . 7
1810, 17zsubcld 10999 . . . . . 6
19 fzen 11732 . . . . . 6
201, 18, 17, 19syl3anc 1228 . . . . 5
21 ax-1cn 9571 . . . . . . 7
2217zcnd 10995 . . . . . . 7
23 addcom 9787 . . . . . . 7
2421, 22, 23sylancr 663 . . . . . 6
2510zcnd 10995 . . . . . . 7
2625, 22npcand 9958 . . . . . 6
2724, 26oveq12d 6314 . . . . 5
2820, 27breqtrd 4476 . . . 4
29 ovex 6324 . . . . . 6
3029a1i 11 . . . . 5
31 fzfi 12082 . . . . . 6
32 rabexg 4602 . . . . . 6
3331, 32mp1i 12 . . . . 5
34 elfzle1 11718 . . . . . . . . . . . . . 14
3534adantl 466 . . . . . . . . . . . . 13
36 elfzelz 11717 . . . . . . . . . . . . . 14
37 zltp1le 10938 . . . . . . . . . . . . . 14
3817, 36, 37syl2an 477 . . . . . . . . . . . . 13
3935, 38mpbird 232 . . . . . . . . . . . 12
40 fllt 11943 . . . . . . . . . . . . 13
4116, 36, 40syl2an 477 . . . . . . . . . . . 12
4239, 41mpbird 232 . . . . . . . . . . 11
4315adantr 465 . . . . . . . . . . . 12
4436adantl 466 . . . . . . . . . . . . 13
4544zred 10994 . . . . . . . . . . . 12
468nnred 10576 . . . . . . . . . . . . . 14
478nngt0d 10604 . . . . . . . . . . . . . 14
4846, 47jca 532 . . . . . . . . . . . . 13
4948adantr 465 . . . . . . . . . . . 12
50 ltdivmul2 10445 . . . . . . . . . . . 12
5143, 45, 49, 50syl3anc 1228 . . . . . . . . . . 11
5242, 51mpbid 210 . . . . . . . . . 10
5313zred 10994 . . . . . . . . . . . 12
5453adantr 465 . . . . . . . . . . 11
555zred 10994 . . . . . . . . . . . 12
5655adantr 465 . . . . . . . . . . 11
578nnzd 10993 . . . . . . . . . . . . . 14
5857adantr 465 . . . . . . . . . . . . 13
5944, 58zmulcld 11000 . . . . . . . . . . . 12
6059zred 10994 . . . . . . . . . . 11
6154, 56, 60ltsubaddd 10173 . . . . . . . . . 10
6252, 61mpbid 210 . . . . . . . . 9
6311adantr 465 . . . . . . . . . 10
645adantr 465 . . . . . . . . . . 11
6559, 64zaddcld 10998 . . . . . . . . . 10
66 zlem1lt 10940 . . . . . . . . . 10
6763, 65, 66syl2anc 661 . . . . . . . . 9
6862, 67mpbird 232 . . . . . . . 8
69 elfzle2 11719 . . . . . . . . . . . 12
7069adantl 466 . . . . . . . . . . 11
71 flge 11942 . . . . . . . . . . . 12
729, 36, 71syl2an 477 . . . . . . . . . . 11
7370, 72mpbird 232 . . . . . . . . . 10
747adantr 465 . . . . . . . . . . 11
75 lemuldiv 10449 . . . . . . . . . . 11
7645, 74, 49, 75syl3anc 1228 . . . . . . . . . 10
7773, 76mpbird 232 . . . . . . . . 9
784zred 10994 . . . . . . . . . . 11
7978adantr 465 . . . . . . . . . 10
80 leaddsub 10053 . . . . . . . . . 10
8160, 56, 79, 80syl3anc 1228 . . . . . . . . 9
8277, 81mpbird 232 . . . . . . . 8
834adantr 465 . . . . . . . . 9
84 elfz 11707 . . . . . . . . 9
8565, 63, 83, 84syl3anc 1228 . . . . . . . 8
8668, 82, 85mpbir2and 922 . . . . . . 7
87 dvdsmul2 14006 . . . . . . . . 9
8844, 58, 87syl2anc 661 . . . . . . . 8
8959zcnd 10995 . . . . . . . . 9
905zcnd 10995 . . . . . . . . . 10
9190adantr 465 . . . . . . . . 9
9289, 91pncand 9955 . . . . . . . 8
9388, 92breqtrrd 4478 . . . . . . 7
94 oveq1 6303 . . . . . . . . 9
9594breq2d 4464 . . . . . . . 8
9695elrab 3257 . . . . . . 7
9786, 93, 96sylanbrc 664 . . . . . 6
9897ex 434 . . . . 5
99 oveq1 6303 . . . . . . . 8
10099breq2d 4464 . . . . . . 7
101100elrab 3257 . . . . . 6
10253adantr 465 . . . . . . . . . . . 12
103 elfzelz 11717 . . . . . . . . . . . . . 14
104103ad2antrl 727 . . . . . . . . . . . . 13
105104zred 10994 . . . . . . . . . . . 12
10655adantr 465 . . . . . . . . . . . 12
107 elfzle1 11718 . . . . . . . . . . . . . 14
108107ad2antrl 727 . . . . . . . . . . . . 13
10911adantr 465 . . . . . . . . . . . . . 14
110 zlem1lt 10940 . . . . . . . . . . . . . 14
111109, 104, 110syl2anc 661 . . . . . . . . . . . . 13
112108, 111mpbid 210 . . . . . . . . . . . 12
113102, 105, 106, 112ltsub1dd 10189 . . . . . . . . . . 11
11415adantr 465 . . . . . . . . . . . 12
1155adantr 465 . . . . . . . . . . . . . 14
116104, 115zsubcld 10999 . . . . . . . . . . . . 13
117116zred 10994 . . . . . . . . . . . 12
11848adantr 465 . . . . . . . . . . . 12
119 ltdiv1 10431 . . . . . . . . . . . 12
120114, 117, 118, 119syl3anc 1228 . . . . . . . . . . 11
121113, 120mpbid 210 . . . . . . . . . 10
12216adantr 465 . . . . . . . . . . 11
123 simprr 757 . . . . . . . . . . . 12
12457adantr 465 . . . . . . . . . . . . 13
1258nnne0d 10605 . . . . . . . . . . . . . 14
126125adantr 465 . . . . . . . . . . . . 13
127 dvdsval2 13989 . . . . . . . . . . . . 13
128124, 126, 116, 127syl3anc 1228 . . . . . . . . . . . 12
129123, 128mpbid 210 . . . . . . . . . . 11
130 fllt 11943 . . . . . . . . . . 11
131122, 129, 130syl2anc 661 . . . . . . . . . 10
132121, 131mpbid 210 . . . . . . . . 9
13317adantr 465 . . . . . . . . . 10
134 zltp1le 10938 . . . . . . . . . 10
135133, 129, 134syl2anc 661 . . . . . . . . 9
136132, 135mpbid 210 . . . . . . . 8
13778adantr 465 . . . . . . . . . . 11
138 elfzle2 11719 . . . . . . . . . . . 12
139138ad2antrl 727 . . . . . . . . . . 11
140105, 137, 106, 139lesub1dd 10193 . . . . . . . . . 10
1417adantr 465 . . . . . . . . . . 11
142 lediv1 10432 . . . . . . . . . . 11
143117, 141, 118, 142syl3anc 1228 . . . . . . . . . 10
144140, 143mpbid 210 . . . . . . . . 9
1459adantr 465 . . . . . . . . . 10
146 flge 11942 . . . . . . . . . 10
147145, 129, 146syl2anc 661 . . . . . . . . 9
148144, 147mpbid 210 . . . . . . . 8
14917peano2zd 10997 . . . . . . . . . 10
150149adantr 465 . . . . . . . . 9
15110adantr 465 . . . . . . . . 9
152 elfz 11707 . . . . . . . . 9
153129, 150, 151, 152syl3anc 1228 . . . . . . . 8
154136, 148, 153mpbir2and 922 . . . . . . 7
155154ex 434 . . . . . 6
156101, 155syl5bi 217 . . . . 5
157101anbi2i 694 . . . . . . 7
158116zcnd 10995 . . . . . . . . . . 11
159158adantrl 715 . . . . . . . . . 10
16044zcnd 10995 . . . . . . . . . . 11
161160adantrr 716 . . . . . . . . . 10
1628nncnd 10577 . . . . . . . . . . 11
163162adantr 465 . . . . . . . . . 10
164125adantr 465 . . . . . . . . . 10
165159, 161, 163, 164divmul3d 10379 . . . . . . . . 9
166104zcnd 10995 . . . . . . . . . . 11
167166adantrl 715 . . . . . . . . . 10
16890adantr 465 . . . . . . . . . 10
16989adantrr 716 . . . . . . . . . 10
170167, 168, 169subadd2d 9973 . . . . . . . . 9
171165, 170bitrd 253 . . . . . . . 8
172 eqcom 2466 . . . . . . . 8
173 eqcom 2466 . . . . . . . 8
174171, 172, 1733bitr4g 288 . . . . . . 7
175157, 174sylan2b 475 . . . . . 6
176175ex 434 . . . . 5
17730, 33, 98, 156, 176en3d 7572 . . . 4
178 entr 7587 . . . 4
17928, 177, 178syl2anc 661 . . 3
180 fzfi 12082 . . . 4
181 ssrab2 3584 . . . . 5
182 ssfi 7760 . . . . 5
18331, 181, 182mp2an 672 . . . 4
184 hashen 12420 . . . 4
185180, 183, 184mp2an 672 . . 3
186179, 185sylibr 212 . 2
187 eluzle 11122 . . . . . . 7
1882, 187syl 16 . . . . . 6
189 zre 10893 . . . . . . . 8
190 zre 10893 . . . . . . . 8
191 zre 10893 . . . . . . . 8
192 lesub1 10071 . . . . . . . 8
193189, 190, 191, 192syl3an 1270 . . . . . . 7
19413, 4, 5, 193syl3anc 1228 . . . . . 6
195188, 194mpbid 210 . . . . 5
196 lediv1 10432 . . . . . 6
19715, 7, 48, 196syl3anc 1228 . . . . 5
198195, 197mpbid 210 . . . 4
199 flword2 11949 . . . 4
20016, 9, 198, 199syl3anc 1228 . . 3