8
$\begingroup$

Let $a_1$ be any number. Create a sequence $a_1, a_2, a_3$, where $a_n$ is formed by appending a digit from 0 to 8 to the end of $a_{n-1}$. Show that this sequence contains infinitely many composite numbers. What happens if you allow for 9? Can you still guarantee that infinitely many composite numbers must occur?

$\endgroup$
  • $\begingroup$ Do you always append the same digit or can it be any digit at each $n$? $\endgroup$ – Nikolai Dec 6 '17 at 22:17
  • 3
    $\begingroup$ For what it's worth: 1, 13, 131, 1319, because 1311 is divisible by 3, 1313 is obviously divisible by 13, and 1317 is also divisible by 3. $\endgroup$ – Lisa Dec 6 '17 at 22:46
8
$\begingroup$

Assume the sequence contains only prime numbers from some point on. We can even assume it consists of primes only. Then we can never append $0,2,4,6$ or $8,$ (it would be divisible by $2$), nor $5$ (it would be divisible by $5$). This leaves $1,3$ and $7.$ The residue modulo 3 is thus either unchanged or increased by $1.$

As the numbers can not be divisible by $3$ this means that from some point onward we can only append a 3. Again, we can assume we only append 3s. So the numbers have the form $$ a_n = 10^{n-1} a_1 + \frac{10^{n-1}-1}{3}. $$ We need to show that $3a_1$ divides $10^{n-1}-1$ infinitely often. But if $a_1$ and $10$ are relative prime, this follows from the Fermat–Euler theorem which implies $$ 10^{\varphi(3a_1)}-1\equiv 0 \pmod {3a_1}, $$ where $\varphi$ is Euler's totient function. If not, we replace $a_1$ by $a_2=10a_1+3.$

$\endgroup$
4
$\begingroup$

The prime number theorem tells us that $$\pi(n) \sim \frac{n}{\log n}.$$ Granted that this is rather inaccurate for small $n$. But as $n$ gets larger and larger, it becomes more accurate.

So, for example, $$\pi(10^{20}) \sim \frac{10^{20}}{\log 10^{20}} \sim 2171472409516259138$$ and $$\pi(10^{20} + 10) \sim \frac{10^{20} + 10}{\log (10^{20} + 10)} \sim 2171472409516259138.$$ This suggests there are no primes between $10^{20}$ and $10^{20} + 10$. Indeed the next prime is $10^{20} + 39$.

This is relevant to your question because $10a_n < a_{n + 1} < 10a_n + 9$. As $a_n$ gets longer and longer, appending a digit to make a prime becomes more and more difficult. Sure, you'll occasionally run into primes. But for the most part, it's gonna be composite numbers no matter which digit you choose to append. Allowing the digit $9$ might make no difference at all.

To continue the $10^{19}$ example, let's say you append $1$. Then $10^{20} + 1$ is divisible by $73$ and $137$, and a couple other primes I don't feel like typing out. And the next prime after $10^{21} + 10$ is $10^{21} + 117$. You get the idea.

$\endgroup$

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.