# Professor Halfbrain and numbers with many zeros

Yesterday I met professor Halfbrain at the opera. During the break, the professor told me that he has made the following amazing discovery:

Professor Halfbrain's theorem:
With a finite number of exceptions, all integers with decimal representation $100\cdots0003$ are prime numbers.

Is the professor's theorem indeed true, or has the professor once again made one of his famous mathematical blunders?

• What are the finite number of exceptions? – question_asker Apr 12 '16 at 12:52
• I guess it's a part of the expected answer. – Shkeil Apr 12 '16 at 12:56
• Prove 10^n + 3 is prime for some n > k – Chris Cudmore Apr 12 '16 at 12:57
• So far you have gotten two answers with similar but yet different proofs. I suspect there is an infinite number of different proofs all following the same structure as the first two answers. – kasperd Apr 12 '16 at 19:17
• Which opera did you attend? – Oliphaunt - reinstate Monica Apr 12 '16 at 19:30

The Professor is:

Wrong.

Because:

$10^{6n + 4} + 3$ is divisible by 7 for all whole values of $n$

From number theory we have for any prime $p$:
If $a \equiv b \pmod {p-1}$ then $c^a \equiv c^b \pmod p$
Because $7$ is prime and $6n + 4 \equiv 4 \pmod {7-1}$

We have $10^{6n + 4} \equiv 10^4 \equiv 4 \pmod 7 \;\forall n \in \Bbb N$
This can be extended to $10^{(p-1)n + q} +3$ (where $10^{q} \equiv {-3} \pmod p$) is divisible by prime $p \;\forall n \in \Bbb N$

No! Unfortunately for the Professor, $10^6 \equiv 1$ (mod $13$), and so for any $n$, $10^{6n+1} + 3 \equiv 10 \cdot (10^6)^n + 3 \equiv 10 \cdot 1^n + 3 \equiv 13 \equiv 0$. That is, $10^{6n+1}+3$ is always divisible by 13, so is never prime. So there are infinitely many exceptions to his rule.

How I found this solution:

Looked up the prime factorisations of 13, 103, 1003, …; noticed that 10000003 (with 6 zeros) was divisible by 13, guessed that this might recur after at intervals of 6; checked the numbers with 12 and 18 zeros respectively to see that it did indeed recur; and then thought about arithmetic mod 13 to see why it is a general pattern.

Given how the search for patterns in the occurrence of prime numbers have found almost no patterns, it would be highly surprising if Professor Halfbrain's theorem was correct.

But that doesn't prove anything. We need a rigorous analysis to decide whether Professor Halfbrain has achieved a mathematical breakthrough. And from a rigorous analysis it turns out that Professor Halfbrain's theorem is

incorrect.

So why is that the case? It turns out that every number of the form $100\cdots0003$

divides a larger number also of the form $100\cdots0003$

So each time we have found a prime $p$ of the form $100\cdots0003$ we know there must be

an infinite number of composite numbers of the form $100\cdots0003$ divisible by $p$. This is because we can first find a larger number $n$ divisible by $p$. But $n$ itself must also divide a larger number etc.

Now I just have to prove my claim that every number of the form $100\cdots0003$

divides a larger number also of the form $100\cdots0003$.

So let's start doing some math modulus $n = 10^k + 3$ for $k>0$. First we observe that since $n$ is obviously not divisible by $2$ or $5$ it must be the case that $n$ is co-prime to $10$. This implies that $10$ will have a multiplicative inverse mod $n$. Since there are only $n$ possible values mod $n$ it is given that two different exponents $e_1<e_2$ exist such that $10^{e_1}$ and $10^{e_2}$ are congruent mod $n$. And since $10$ has a multiplicative inverse it implies that $10^{e_2-e_1}$ is congruent to $1$. That then implies that $10^{k+e_2-e_1}+3$ is congruent to $10^k + 3 = n$. So $n$ divides $10^{k+e_2-e_1}+3$. QED.

Two earlier answer has already proven special cases for 7 and 13, which would be enough to answer the question. I wanted to also provide a more general proof such we now know that there are infinitely many integers that those answers could have used in place of 7 or 13.

• My answer has a general case for a prime $p$ where $10^q \equiv -3 \pmod p$ – Paul Evans Apr 13 '16 at 12:02
• @PaulEvans Oh, that's right. Well my proof applies to every number of the form 100...0003 prime or not. And yours applies to some primes not of the form 100...0003. You have not exactly proven that there is an infinite number of primes satisfying the criteria required for your proof, though I think it is likely that there is an infinite number of them. – kasperd Apr 13 '16 at 12:29