Can you make any number prime by adding some digits to the right?

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.

Solution 1:

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.

Solution 2:

The answer to the question in the title is "yes" (and more is in fact true), but I am unsure if Dirichlet's theorem can be used to prove it.

In Sierpinski's book "A Selection of Problems in the Theory of Numbers" he writes:

"If we have two arbitrary sequences of digits (in decimal notation) $a_1, a_2, \dots, a_m$ and $b_1, b_2, \dots, b_n$, where $b_n = 1, 3, 7$ or $9$, then there exist arbitrarily large primes $p$ such that the first $m$ digits are successively $a_1, a_2, \dots, a_m$ and the last $n$ digits are successively $b_1, b_2, \dots, b_n$."

He also says that the proof of this is difficult although it can be carried out in an elementary way, and refers to a paper of his:

"Sur les nombres premiers ayant des chiffres initiaux et finales donnés", Acta Arith. 5 (1959), pp. 1046-1047.