1
$\begingroup$

It seems that for any base $b\geq 2$, and for any number of digits $k\geq 2$, there is always some prime number that is $k$ digits long in base $b$.

For example, in base $10$, for $2\leq k\leq 10$ we have

$$\{11, 101, 1009, 10007, 100003, 1000003, 10000019, 100000007, 1000000007, 10000000019\}$$

and in base $2$ we have

$$\left\{11_2,101_2,1011_2,10001_2,100101_2,1000011_2,10000011_2,100000001_2,1000001001_2,10000000111_2\right\}$$

are there any counterexamples to this or is there a proof that this is always the case?

$\endgroup$
  • 3
    $\begingroup$ Look up "Bertrand's postulate." $\endgroup$ – Mark Dickinson Jan 12 '15 at 18:09
5
$\begingroup$

Bertrand's postulate (proven later by Chebyshev) says that for any $n>1$, there exists some prime $p$ such that $n<p<2n$.

In particular, for base $b\ge2$ with $k\ge2$, this gives us that there exists a prime strictly between $b^{k-1}$ and $2b^{k-1}$, so we have that there exists a $k$-digit prime base $b$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.