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?
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.
