# At least 99% of these numbers are composite

This is from a contest preparation:

Prove that at least 99% of these numbers

$$10^1+1,10^2+1, 10^3+1, ..., 10^{2010}+1$$

are composite.

The problem is from 2010, obviously. I was tempted to replace 2010 with 2015, but was afraid that the statement actually may not be true for 2015.

I tried congruences, but they did not work as I expected.

• Hint: If $n$ is even, then $10^n + 1$ is divisible by $11$. That takes care of half these numbers right off the bat. – user155234 Jan 9 '15 at 21:44
• Actually, if $n$ is odd that's when $10^n + 1$ is divisible by 11. Still, your second point is still essentially correct. – Robert Soupe Jan 10 '15 at 4:19

Suppose that $n$ has an odd prime divisor greater than $1$. Then $10^n+1$ is composite. So the only candidates for primality are the numbers $10^{(2^k)}+1$.

The powers of $2$ less than $2010$ are $2^0$ up to $2^{10}$, a total of $11$. Of course for some of these $10^n+1$ may not be prime. But for sure the proportion of primes is $\frac{11}{2010}$ or less, well under $1\%$.

Remark: We used the fact that if $d$ is odd then $x+1$ divides $x^d+1$. If $n=dq$, with $d$ odd, it follows that $10^q+1$ divides $10^n+1$. If $d\gt 1$, then $10^q+1$ is a proper divisor of $10^n+1$.

Let's assume the statement is true going up to 2010. Going up to 2015 doesn't even add a percentage point: $10^{2011} + 1, \ldots, 10^{2015} + 5$ could all be prime but when you round to a percentage point, you'd still get 99%.

But that's not the case, those five numbers are composite. As Albert already mentioned, if $n$ is odd, then $10^n + 1$ is divisible by 11. So we have something like 50% of these numbers guaranteed to be composite, except of course 11 which is trivially divisible by itself.

If $n \equiv 2 \pmod 4$, then $10^n + 1$ is a multiple of 101. So that's about another 25% guaranteed to be composite, aside from 101.

Now, 1001 doesn't give us much mileage, because these odd exponents are already taken care of. But with 75% of the potential primes knocked off as composites, you're well on your way to reaching 99%.