1, 101, 10101, 1010101, 101010101, 10101010101, 1010101010101, 101010101010101, 10101010101010101, 1010101010101010101, 101010101010101010101, 10101010101010101010101, 1010101010101010101010101, 101010101010101010101010101, 10101010101010101010101010101

This is the sequence A094028 of the On-Line Encyclopedia of Integer Sequences (OEIS). According to a comment from Felix Fröhlich on the sequence’s page:

101 is the only term that is prime, since (100^k-1)/99 = (10^k+1)/11 * (10^k-1)/9. When k is odd and not 1, (10^k+1)/11 is an integer > 1 and thus (100^k-1)/99 is nonprime. When k is even and greater than 2, (100^k-1)/99 has the prime factor 101 and is nonprime.

Felix Fröhlich, Oct 17 2015¹

It isn’t particularly striking that it should be the case. Let’s see why 101 is the only prime number of the sequence.

The sequence

First of all, let’s study a bit more the sequence. Let’s call $A(n)$ the $(n-1)$th element of the sequence $A(0)$ is the first element of the sequence).

For the first few elements we have:

We can see that we can write the sequence as $A(n)=\sum _{k=0}^n{100}^k$.

For example, for the first element we have $A(0)={100}^0=1$.

Similarly, for $n=2$, $A(2)=10000+100+1=10101$.

A simpler form

For the $(n-1)$th element of the sequence, we have:

We would like to remove some of terms, let’s consider

This sequence has many similar terms to $A(n)$, let’s subtract $100A(n)$ from $A(n)$.

We can cancel the common terms, we end up with:

To find out what $A(n)$ is, let’s isolate it from the equation.

So, we have: $A(n)=\frac{{100}^{n+1}-1}{99}$, which we can see from the comment in the OEIS’s website.

Cleaning things a bit

We can rewrite $A(n)$ as $A(n)=\frac{({10}^{n+1}{)}^2-1}{99}$, because $100={10}^2$.

We now have a difference of squares, we can factorize it further:

To make it a bit simpler to work with, let’s do a little variable substitution with $k=n-1$.

Therefore,

Okay, now we can write the $(k-1)$th element of the sequence a bit more easily, but it isn’t clear how we could prove that only 101 is prime. Let’s try to simplify this expression a bit more.

First of all, we can see that $({10}^n-1)$ will be of the form $\underset{n\text{-times}}{\underbrace{99\dots 99}}$.

We can split the $99$ in the denominator into $9\cdot 11$. We now have

We can do the same for the $\stackrel{n\text{-times}}{\overbrace{99\dots 99}}$ in the numerator, we get:

We can cancel out the $9$s.

Division by 11

Let’s take a small break from our sequence to discuss the divisibility by 11. For a number $n$ to be divisible by $11$, we must have that $n\equiv 0(\mathrm{mod}11)$

A number in decimal base can be expressed as $n=a_k{a}_{k-1}\dots a_1{a}_0$, so the value of $n$ is ${10}^k{a}_k+{10}^{k-1}{a}_{k-1}+\dots +10a_1+a_0$.

Note that $10\equiv -1(\mathrm{mod}11)$.

So, ${10}^k{a}_k+{10}^{k-1}{a}_{k-1}+\dots +10a_1+a_0\equiv (-1{)}^k{a}_k+(-1{)}^{k-1}{a}_{k-1}+\dots +(-a_1)+a_0(\mathrm{mod}11)$

Since $(-1{)}^{2n}=1\mathrm{\forall }n\in \mathbf{N}$, we deduce that every even placed digit are added, whereas odd placed numbers are subtracted ($(-1{)}^{2n+1}=1\mathrm{\forall }n\in \mathbf{N}$).

So, we can rewrite

Since we want to check if $n$ is divisible by $11$, we must check if

So, $n$ is divisible by $11$ if the sum of even placed digit (starting from the rightmost position) minus the sum of the odd placed digit is divisible by $11$.

The proof

Now that we know that when a number is divisible by $11$, let’s analyse $A(k)$.

$n>1$ is even

First, let’s suppose that $n$ is even. In that case, we get that $\stackrel{n\text{-times}}{\overbrace{11\dots 11}}$ is divisible by $11$, because, since there is as much even placed $1$s as odd placed $1$s, the sum of even placed digit minus the sum of the odd placed digit is 0, which is divisible by $11$.

Now, let’s use the variable $k=n-1$ to link the divisibility of $\stackrel{n\text{-times}}{\overbrace{11\dots 11}}$ by $11$ with the sequence. We notice that for $n>1$ to be even, we must have that $k$ is odd, because $k=n-1$.

For $k\ge 3$, we have $n=k+1\ge 4$, so that $\stackrel{(n\ge 4)\text{-times}}{\overbrace{11\dots 11}}>11$.

Thus, we can deduce that $\frac{\stackrel{(n\ge 4)\text{-times}}{\overbrace{11\dots 11}}}{11}>1$ and that it is an integer.

Posing $a=\frac{\stackrel{(n\ge 4)\text{-times}}{\overbrace{11\dots 11}}}{11}$, we get $A(k)=({10}^n+1)a$.

Since $A(k)$ is the result of the multiplication between two integers, each not equal to one, $A(k)$ is not prime.

$n>1$ is odd

We can use a similar trick for any even $k\ge 2$, this time with the other part of $A(k)$. When $k$ is even (so that $n$ is odd) in $({10}^n+1)$, we have that one $1$ is at a even position and the other at an odd position, thus $1-1=0$ which is divisible by $11$. Similarly, we have that $({10}^n+1)>11$ because $n\ge 3$. Thus, $\frac{({10}^n+1)}{11}>1$ and it is an integer. We can then conclude that $A(k)$ is not prime for even $k=n-1\ge 2$.

The remaining cases

This leaves us with two cases, $k=0$ and $k=1$. $A(0)=1$ is not prime by definition and $A(1)$ is prime. Since for any other $k$, $A(k)$ is not prime, then $A(1)$ is the only prime in the sequence.

$◼$

References