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.

  • 2
    $\begingroup$ Hint: If $n$ is even, then $10^n + 1$ is divisible by $11$. That takes care of half these numbers right off the bat. $\endgroup$ – user155234 Jan 9 '15 at 21:44
  • $\begingroup$ Actually, if $n$ is odd that's when $10^n + 1$ is divisible by 11. Still, your second point is still essentially correct. $\endgroup$ – 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%.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.