# Is there at least one prime between $n \times 100$ and $(n \times 100) + 100$ where $n \in \mathbb{N}$

Is there at least one prime between the number $n \times 100$ and $(n \times 100) + 100$ for any $n \in \mathbb{N}$ that can be $0$ ?

Question originally formulated by one of my friends.

-

Not necessarily. For example none of the numbers between $200!+100$ and $200!+200$ can be prime, because $200!+k$ is divisible by $k$ when $2\le k\le 200$.

So a concrete counterexample would be $n=\frac{200!}{100}+1$.

For a smaller counterexample one could let $100n$ be the product of all primes up to 109, times 3, plus 10. That gives an $n$ with "only" $43$ digits.

Heuristically, based on the prime number theorem, one would expect counterexamples to start showing up as early as for $n$ in the mid-thousands. The "probability" that a random $n$ works is roughly $(1-\frac{1}{\ln(100n)})^{100}$, and at $n=4000$ this is more than $1/4000$.

An exhaustive search, however, shows that the smallest counterexample is n=16,718. That's not too far from the above heuristic estimate, considering how crude it is.

-

No.

Consider $n=99!$. $100n = 100!$ is composite, and $100!+1$ is divisible by $101$ (Wilson's theorem) and so is composite. $100n+i$ is divisible by $i$ for $2\leq i \leq 100$.

-
See also Henning's answer for a larger, but more elementary counterexample that does not require Wilson's theorem. – user7530 Sep 12 '13 at 21:21
So this depends on the lucky shot that $101$ is prime. So if you want interval sizes that always contain a prime, look for (at minimum) something which isn't one less than a prime. – Jack M Sep 12 '13 at 22:14
     4652400 = 2^4 * 3 * 5^2 * 3877
4652401 = 13^2 * 27529
4652402 = 2 * 401 * 5801
4652403 = 3 * 7^2 * 31649
4652404 = 2^2 * 619 * 1879
4652405 = 5 * 930481
4652406 = 2 * 3^2 * 11 * 23497
4652407 = 17 * 103 * 2657
4652408 = 2^3 * 581551
4652409 = 3 * 61 * 25423
4652410 = 2 * 5 * 7 * 66463
4652411 = 97 * 47963
4652412 = 2^2 * 3 * 29^2 * 461
4652413 = 67 * 69439
4652414 = 2 * 13 * 178939
4652415 = 3^2 * 5 * 103387
4652416 = 2^7 * 19 * 1913
4652417 = 7 * 11 * 23 * 37 * 71
4652418 = 2 * 3 * 31 * 25013
4652419 = 823 * 5653
4652420 = 2^2 * 5 * 232621
4652421 = 3 * 199 * 7793
4652422 = 2 * 2326211
4652423 = 1567 * 2969
4652424 = 2^3 * 3^3 * 7 * 17 * 181
4652425 = 5^2 * 186097
4652426 = 2 * 2326213
4652427 = 3 * 13 * 119293
4652428 = 2^2 * 11 * 43 * 2459
4652429 = 373 * 12473
4652430 = 2 * 3 * 5 * 155081
4652431 = 7 * 664633
4652432 = 2^4 * 313 * 929
4652433 = 3^2 * 599 * 863
4652434 = 2 * 41 * 56737
4652435 = 5 * 19 * 48973
4652436 = 2^2 * 3 * 47 * 73 * 113
4652437 = 1583 * 2939
4652438 = 2 * 7 * 332317
4652439 = 3 * 11 * 140983
4652440 = 2^3 * 5 * 13 * 23 * 389
4652441 = 17 * 29 * 9437
4652442 = 2 * 3^2 * 258469
4652443 = 397 * 11719
4652444 = 2^2 * 1163111
4652445 = 3 * 5 * 7 * 59 * 751
4652446 = 2 * 53 * 43891
4652447 = 109 * 42683
4652448 = 2^5 * 3 * 48463
4652449 = 31 * 223 * 673
4652450 = 2 * 5^2 * 11^2 * 769
4652451 = 3^3 * 172313
4652452 = 2^2 * 7^3 * 3391
4652453 = 13 * 167 * 2143
4652454 = 2 * 3 * 19 * 37 * 1103
4652455 = 5 * 930491
4652456 = 2^3 * 581557
4652457 = 3 * 1550819
4652458 = 2 * 17 * 193 * 709
4652459 = 7 * 367 * 1811
4652460 = 2^2 * 3^2 * 5 * 25847
4652461 = 11 * 151 * 2801
4652462 = 2 * 1327 * 1753
4652463 = 3 * 23 * 67427
4652464 = 2^4 * 101 * 2879
4652465 = 5 * 131 * 7103
4652466 = 2 * 3 * 7 * 13 * 8521
4652467 = 107 * 43481
4652468 = 2^2 * 79 * 14723
4652469 = 3^2 * 139 * 3719
4652470 = 2 * 5 * 29 * 61 * 263
4652471 = 43 * 257 * 421
4652472 = 2^3 * 3 * 11 * 17623
4652473 = 7 * 19 * 34981
4652474 = 2 * 977 * 2381
4652475 = 3 * 5^2 * 17 * 41 * 89
4652476 = 2^2 * 1163119
4652477 = 911 * 5107
4652478 = 2 * 3^6 * 3191
4652479 = 13 * 357883
4652480 = 2^6 * 5 * 7 * 31 * 67
4652481 = 3 * 1550827
4652482 = 2 * 83 * 28027
4652483 = 11 * 47 * 8999
4652484 = 2^2 * 3 * 387707
4652485 = 5 * 877 * 1061
4652486 = 2 * 23 * 101141
4652487 = 3^2 * 7 * 73849
4652488 = 2^3 * 71 * 8191
4652489 = 173 * 26893
4652490 = 2 * 3 * 5 * 155083
4652491 = 37 * 125743
4652492 = 2^2 * 13 * 17 * 19 * 277
4652493 = 3 * 1550831
4652494 = 2 * 7 * 11 * 30211
4652495 = 5 * 930499
4652496 = 2^4 * 3^2 * 32309
4652497 = 2029 * 2293
4652498 = 2 * 2326249
4652499 = 3 * 29 * 53 * 1009
4652500 = 2^2 * 5^4 * 1861
jagy@phobeusjunior:~$ - Awesome as usual. – Pedro Tamaroff Sep 13 '13 at 3:02 You use Linux! Awesome! – user93957 Sep 13 '13 at 15:44 @Adobe, yes, C++ with STL, and, for Pell equations, GMP, as some kinds of numbers stay small (the "digits" or "quotients") but the values of$x,y$in$x^2 - n y^2 = m$can become huge. Meanwhile, see the table with the first 75 maximal prime gaps in en.wikipedia.org/wiki/Prime_gap#Numerical_results which is how I knew 4652400 would work, after which I did an exhaustive search and repeated Henning's find of the first failure. In any case, read about prime gaps. – Will Jagy Sep 13 '13 at 19:00 Thank you so much @WillJagy – user93957 Sep 13 '13 at 19:41 @Adobe, a relatively early counterexample for your 1000 problem begins with 80873624627235000 and has all composite numbers up to 80873624627236000. There will always be counterexamples for these, finding the earliest counterexample for one of them becomes arduous. Compare this information from the Prime Gaps table, gap = 1220, beginning prime = 80873624627234849. That is, the next prime is 80873624627236069. – Will Jagy Sep 13 '13 at 20:07 Earliest failure:  1671800 = 2^3 * 5^2 * 13 * 643 1671801 = 3 * 23 * 24229 1671802 = 2 * 11 * 75991 1671803 = 7 * 238829 1671804 = 2^2 * 3^2 * 46439 1671805 = 5 * 239 * 1399 1671806 = 2 * 769 * 1087 1671807 = 3 * 557269 1671808 = 2^7 * 37 * 353 1671809 = 599 * 2791 1671810 = 2 * 3 * 5 * 7 * 19 * 419 1671811 = 137 * 12203 1671812 = 2^2 * 417953 1671813 = 3^3 * 11 * 13 * 433 1671814 = 2 * 17 * 49171 1671815 = 5 * 334363 1671816 = 2^3 * 3 * 41 * 1699 1671817 = 7 * 241 * 991 1671818 = 2 * 835909 1671819 = 3 * 557273 1671820 = 2^2 * 5 * 83591 1671821 = 29 * 57649 1671822 = 2 * 3^2 * 131 * 709 1671823 = 191 * 8753 1671824 = 2^4 * 7 * 11 * 23 * 59 1671825 = 3 * 5^2 * 22291 1671826 = 2 * 13 * 64301 1671827 = 61 * 27407 1671828 = 2^2 * 3 * 127 * 1097 1671829 = 19 * 87991 1671830 = 2 * 5 * 31 * 5393 1671831 = 3^2 * 7^2 * 17 * 223 1671832 = 2^3 * 53 * 3943 1671833 = 1289 * 1297 1671834 = 2 * 3 * 278639 1671835 = 5 * 11 * 113 * 269 1671836 = 2^2 * 417959 1671837 = 3 * 47 * 71 * 167 1671838 = 2 * 7 * 119417 1671839 = 13 * 128603 1671840 = 2^5 * 3^5 * 5 * 43 1671841 = 1223 * 1367 1671842 = 2 * 109 * 7669 1671843 = 3 * 557281 1671844 = 2^2 * 417961 1671845 = 5 * 7 * 37 * 1291 1671846 = 2 * 3 * 11 * 73 * 347 1671847 = 23 * 72689 1671848 = 2^3 * 17 * 19 * 647 1671849 = 3^2 * 431^2 1671850 = 2 * 5^2 * 29 * 1153 1671851 = 67 * 24953 1671852 = 2^2 * 3 * 7 * 13 * 1531 1671853 = 101 * 16553 1671854 = 2 * 835927 1671855 = 3 * 5 * 227 * 491 1671856 = 2^4 * 104491 1671857 = 11^2 * 41 * 337 1671858 = 2 * 3^2 * 293 * 317 1671859 = 7 * 238837 1671860 = 2^2 * 5 * 179 * 467 1671861 = 3 * 31 * 17977 1671862 = 2 * 835931 1671863 = 359 * 4657 1671864 = 2^3 * 3 * 69661 1671865 = 5 * 13 * 17^2 * 89 1671866 = 2 * 7 * 119419 1671867 = 3^3 * 19 * 3259 1671868 = 2^2 * 11 * 37997 1671869 = 83 * 20143 1671870 = 2 * 3 * 5 * 23 * 2423 1671871 = 487 * 3433 1671872 = 2^6 * 151 * 173 1671873 = 3 * 7 * 79613 1671874 = 2 * 835937 1671875 = 5^6 * 107 1671876 = 2^2 * 3^2 * 46441 1671877 = 79 * 21163 1671878 = 2 * 13 * 64303 1671879 = 3 * 11 * 29 * 1747 1671880 = 2^3 * 5 * 7^2 * 853 1671881 = 331 * 5051 1671882 = 2 * 3 * 17 * 37 * 443 1671883 = 43 * 59 * 659 1671884 = 2^2 * 47 * 8893 1671885 = 3^2 * 5 * 53 * 701 1671886 = 2 * 19 * 43997 1671887 = 7 * 238841 1671888 = 2^4 * 3 * 61 * 571 1671889 = 521 * 3209 1671890 = 2 * 5 * 11 * 15199 1671891 = 3 * 13 * 163 * 263 1671892 = 2^2 * 31 * 97 * 139 1671893 = 23 * 157 * 463 1671894 = 2 * 3^3 * 7 * 4423 1671895 = 5 * 334379 1671896 = 2^3 * 103 * 2029 1671897 = 3 * 181 * 3079 1671898 = 2 * 41 * 20389 1671899 = 17 * 98347 1671900 = 2^2 * 3 * 5^2 * 5573  - I see, Henning indicated the first failure late in his answer. – Will Jagy Sep 13 '13 at 3:41 As a generalization of some of the other answers, there are arbitrarily long sequences of composites: Namely, consider the numbers$N! + 2, N! + 3, N! + 4, ..., N!+N$which has length$N - 1\$.

-