No primes in this sequence

Question

Here's a fun little problem:

Prove that the sequence $$10001, 100010001, 1000100010001, \cdots$$ contains no prime numbers.

Answer 1

The sequence $a$ to be proved all-composite is $(10001, 100010001, 1000100010001,\ldots)$

By inspection, $a(1) = 10001 = 11025 - 1024 = 105^2 - 32^2 = (105 + 32) * (105 - 32)$ and so $a(1)$ is composite. As it happens, both factors found above are primes, though that is not relevant.

And that was the tough bit. Also, it sets the theme (the difference of two squares being the product of the sum and difference of the underlying numbers) employed throughout the proof.

It does, however, still leave us with an infinity of terms of the sequence to prove are composite. But that's the easy bit, as you will see.

---

Observe that $(10000 + 1) * (10000 - 1) = 10000^2 - 1^2 = 99999999 = 10^8 - 1$.

So, if the $n$-th term of the sequence is $a(n)$, where $n$ is a natural number, we have:

$$9999 * a(n) = 10^{4n + 4} - 1\tag 1$$

Check that when $n = 1$ the R.H.S. of $(1)$ equals $10^8 - 1$, when $n = 2$ it is $10^{12} - 1$, etc., i.e. in each case it is $(10000 - 1)$ times the corresponding term of the sequence. This follows from the well known formula for the sum of a geometric series.

Now $n$ is either even or odd; we shall consider each case separately.

---

CASE "E": $n$ is even $$ 10^{4n + 4} - 1 = (10^{2n + 2} + 1) * (10^{2n + 2} - 1) $$ and $9999 = 10^4 - 1 = (10^2 + 1) * (10^2 - 1) = 101 * 99$

So $a(n) = [(10^{2n + 2} + 1) / 101] * [(10^{2n + 2} - 1) / 99]$

Consider in turn the contents of each pair of square brackets.

$101$ always divides $(10^{2n + 2} + 1)$ exactly.

We see if $n = 2$, the quotient is $9901$, if $n = 4$, $99009901$, etc. The pattern is:

• $9901 = 1 - 100 + 10000 = \sum_{k=0}^2(-100)^k$

• $99009901 = 1 - 100 + 10000 - 1000000 + 100000000 = \sum_{k=0}^4(-100)^k$

etc.

$99$ always divides $(10^{2n + 2} - 1)$ exactly, as that number comprises a string of an even number of $9$s.

We see if $n = 2$, the quotient is $10101$, if $n = 4$ it is $101010101$, etc. The pattern is obvious.

Thus each pair of square brackets contains a natural number greater than $1$.

Thus when $n$ is even, $a(n)$ is always the product of two natural numbers, each being greater than $1$, i.e., $a(n)$ is composite.

---

CASE "O": $n$ is odd. We can write $n = 2m + 1$ where $m>0$ (we do not need to cater for $n = 1$, as we have already proved that a(1) is composite).

$$10^{4n + 4} - 1 = 10^{8m + 8} – 1 = (10^{4m + 4} + 1) * (10^{4m + 4} - 1)$$

So $a(n) = (10^{4m + 4} + 1) * [(10^{4m + 4} - 1) / 9999]$

$9999$ always divides $(10^{4m + 4} - 1)$ exactly, as that number comprises a string of $9$s which is a multiple of $4$ in length.

We see if $m = 1$, the quotient is $10001$, if $m = 2$ it is $100010001$, etc. The pattern is obvious.

Thus when $n$ is odd, $a(n)$ is always the product of two natural numbers, each being greater than $1$, i.e., $a(n)$ is composite.

---

Therefore, irrespective of whether $n$ is even or odd, $a(n)$ is composite. Q.E.D.