Question from Putnam '89: Primes of the form $101\ldots01$

Question

I'm not a math major, but would like to compete in the Putnam. As suggested in other questions here, I'm working some old contest problems. I'd like some input on this attempted proof--general input is gladly welcomed, but I do have some specific questions (see bottom of post.)

Prompt:

How many primes among the positive integers, written as usual in the base 10, are such that their digits are alternating 1's and 0's, beginning and ending with 1?

Source: http://www.math.ksu.edu//events/ksucomp/putnam/examquestions.htm

Answer: There is only one such prime, namely, $101$.

Proof:

Consider the numbers of the form $101\ldots01$. Let $a_n$ be the number of this form with $n$ ones in its base-10 representation. That is: $$a_n = \sum_{k=0}^{n-1}10^{2k} \tag{1}$$ It follows: $$\begin{align} a_n &= \sum_{k=0}^{n-1}\left(10^2\right)^k \\ &= \frac{\left(10^2\right)^n-1}{10^2-1} \\ &= \frac{(10^n)^2-1}{99} \\ &= \frac{(10^n-1)(10^n+1)}{9\cdot 11} \end{align}$$

We now note that $10^n-1=9\sum_{k=0}^{n-1}10^k$. Thus:

$$a_n = \frac{\left(\sum_{k=0}^{n-1}10^k\right)(10^n+1)}{11} \tag{2}$$

Let $b_n$ be the numerator in $(2)$; that is: $$b_n = \left(\sum_{k=0}^{n-1}10^k\right)(10^n+1)$$

From formula $(1)$, we can see that $a_n$ is the sum of integers, thus, $a_n$ is clearly an integer. For $a_n$ to be a prime, $b_n$ must satisfy the following: $$b_n = 11\cdot p\text{, where $p$ is prime.}$$

Therefore, one of either $\left(\sum_{k=0}^{n-1}10^k\right)$ or $(10^n+1)$ must be $11$, and the other is prime. For $n=1$, we see: $$\left(\sum_{k=0}^{n-1}10^k\right) = 1;\qquad(10^n+1)=11$$ For $n=2$, we see: $$\left(\sum_{k=0}^{n-1}10^k\right) = 11;\qquad(10^n+1)=101$$ As both terms are monotonically increasing, these two are the only ways to have either one equal to $11$. Of these two, only one pair contains a prime (namely, $101$).

---

My questions:

First and foremost, I want to know if my proof is valid/on the right track. :) After that, I'd like to know if I'm covering the proof in enough detail. Specifically:

1. I assert that $10^n-1=9\sum_{k=0}^{n-1}10^k$. Do I need to prove this, or is it obvious enough? (Subtracting $1$ from a power of $10$ leaves a number with as many $9$s as there are $0$'s in the power of $10$.)
2. Do I need to show further why $b_n$ must be $11$ times a prime? Or is it clear that all other cases yield composite $a_n$?
3. Is my reasoning that there are only these two solutions (i.e. monotonically increasing terms) legitimate?

And, finally, is there some well-known theorem that I have totally overlooked that would make solving this problem easy?

Answer 1

You can actually cut your proof short a fair bit earlier — once you have $a_n=(10^n+1)(10^n-1)/99$, you can note that for $n\gt 2$, both of these factors are larger than $2\times 99$ and so there must be a factorization of $a_n$ into two numbers each larger than $2$.

More formally, you can split into the case of even $n$ and odd $n$; for even $n$ then $99|10^n-1$ so you have $a_n=(10^n+1)\times \left((10^n-1)/99\right)$ with each factor $\gt 1$, while for odd $n$ $11| 10^n+1$ and $9|10^n-1$ so $a_n=\left((10^n+1)/11\right)\times\left((10^n-1)/9\right)$ with each factor $\gt 1$. (These divisibility properties are immediate from $10\equiv 1\pmod 9$ and $10\equiv -1\pmod{11}$). This also explains why the proof breaks down at $n=2$; there, you still have $a_n=(10^n+1)\times\left((10^n-1)/99\right)$, but it's no longer the case that the right factor is $\gt 1$.

Answer 2

Your proof looks good to me. Here's an alternative proof, which is not necessarily better but was the first thing that came to my mind:

Let $a_n$ be as in your proof. It is easy to see that if $m\mid n$ then $a_m\mid a_n$ (just consider the process of long division). By inspection, I found that if $n$ is odd then $$a_n=\left(\sum\limits_{k=0}^n 10^k\right)\left(1+\sum\limits_{k=0}^{(n-1)/2}9\cdot 10^{2k}\right).$$ Thus $a_n$ can only be prime when $n$ is an even prime, i.e. $n=2$.