A nice property of primes

by phimuemue

A while ago, a friend of mine told me that he once knew a number with the following property: “You can prepend any number before that number and will always obtain a prime number.”

Of course, he was just kidding: Such a number can’t exist, because a number is divisible by 3 if and only if its digit sum is divisible by 3. So, it is no problem to find a number to prepend such the digit sum of the resulting number is divisible by 3. That implies that the resulting number is not a prime.

However, it’s possible to prove a similar theorem…

We prove the following: For any number m, there is a number with m digits, such there are infinitely many primes ending with this m-digit number.

To prove this, let us first consider the case m=1. This means, that we want to show that there is a number n \in \left\{ 0,1,2,3,4,5,6,7,8,9 \right\} such there are infinitely many primes ending in this number n.

It’s a well-known fact that there are infinitely many primes. Thus, due to the pigeonhole principle, there must be a number in n \in \left\{ 0,1,2,3,4,5,6,7,8,9 \right\} to occur infinitely many often. Thus, such a number exists.

Now, it’s no big step to generalize this to more digits: Assume we found our number n with the desired property. I.e. there are infinitely many primes ending with n. Now, we “cross out” all primes ending not in n. So, we are now only considering the infinitely many primes ending in n

But now, according to the pigeonhole principle, there must be a number n' \in \left\{ 0,1,2,3,4,5,6,7,8,9 \right\} such that there are infinitely many primes whose next-to-last digit is n'. That means, there are infinitely many primes ending in the digits n' n.

Now, we iterate the procedure: We cross out all primes not ending in n' n. This yields – again – infinitely many primes ending in n' n. So we can argument the same way as before: There must be – due to pigeonhole principle – a number $n”$ such that infinitely many primes end in n'' n' n.

We can continue this procedure as long as we want – since there are infinitely many primes.

So, this means, there are arbitrarily large numbers n_m n_{m-1} n_{m-2} \dots n_2 n_1 n_0 (concatenated digits n_i) such that there are infinitely many primes ending with exactly the digits n_m n_{m-1} n_{m-2} \dots n_2 n_1 n_0.

I like this proof because it is – once again – a proof of existence that does not explicitly construct a solution to the problem, but just shows that there is one.