To ask in another way: Is it guaranteed that any given sequence of digits will be at the beginning of some prime number?
We know from Dirichlet's theorem that there are an infinite number of values of $n$ such that $k*n+b$ is prime, as long as $k$ and $b$ share no factors.
Adding digits to the end of some number $k$ in base $B$ can be written in the form
$k*B^{n} + b$. Can we use Dirichlet's theorem to guarantee that this will generate some prime number?
Motivation: This is how so-called "illegal primes" were found, but I'd like to be familiar with the theory of why it works.
Best Answer
I also don't see how to use Dirichlet's arithmetic progression theorem. But I see an easy proof using the prime number theorem. I don't see a more elementary way yet.
The solution goes like this. Take an arbitrary number $k$. We want to prove that there is a natural $n$ such that interval $[k \cdot B^n, (k+1) \cdot B^n)$ contains at least one prime. We will show that this is in fact true for all $n$ starting from some $n_0$ (that may depend on $k$, of course).
In terms of the prime counting function, we want to show that $\pi((k+1)B^n) > \pi(k \cdot B^n)$, where $\pi$ is the prime counting function and $n$ is large enough.
Pick an arbitrary $\varepsilon > 0$. By the prime counting theorem, when $x$ is large enough, we have $1 - \varepsilon < \pi(x) \ln x / x < 1 + \varepsilon$. Then, when $n$ is large enough, we have $$ \begin{array}{rcl} \pi(k B^n) & < & (1+\varepsilon) \frac{k B^n}{\ln k + n \ln B} \qquad \text{and} \\ (1 - \varepsilon) \frac{(k+1)B^n}{\ln (k+1) + n \ln B} & < & \pi((k+1)B^n). \end{array} $$
Now, $\varepsilon$ is arbitrary. Let us pick $\varepsilon$ in such a way that $(1 + \varepsilon) k < (1-\varepsilon)(k+1)$. Then, for $n$ large enough, we have $\pi(kB^n) < \pi((k+1)B^n)$, QED.