Making a number composite by appending one digit at time.

Question

Given a prime number. Any time a single digit other than 9 is appended to the number (i.e written at the end of it). Prove that the number will eventually become composite.

---

Quite obviously appending an even digit or digit 5 turns the number immediately into a composite.

Adding 1 or 7 will make it   $+1 \mod 3$, while adding a 3 doesn't change the residue mod 3. Therefore after at most two appends of either 1 or 7 the number becomes a multiple of 3.

---

The problem raises when digit 3 keeps being appended all the time. So far I can see the following:

For any prime number $p \gt 3$ there are numbers $a$ whose residue mod p stays after appending 3, i.e.$$ 10a + 3 \equiv a \mod p \tag{1} $$

This comes from the observation that the difference between new and old numbers is $$ (10a+3)-a = 9a+3 = 3(3a+1) $$

The equation $3r+1 \equiv 0\mod p$ has a solution, as 3 and $p$ are co-prime, so $\{3r\}_{r=1}^{p-1}$ gives a complete set of residues modulo $p$ and will be $p-1$ for certain value $r_0$. Then any $a \equiv r_0 \mod p$ satisfies $(1)$.

This makes the problem a bit tough, since a certain prime number cannot be expected to give a clue to the solution.

Answer 1

Suppose your starting prime is $x_0 \ne 2, 3, 5$, so the sequence of numbers obtained by appending digit $3$ is $x_n = 10^n x_0 + (10^n - 1)/3$. This is divisible by $x_0$ if $10^n \equiv 1 \mod x_0$. Now use Fermat's "little" theorem.

Answer 2

Suppose the number before a very long string of $3$s is prime $p$

Then $10^{p-1}-1$ is divisible by $p$ (Fermat's little theorem) and also by $3$ (since it is a long string of $9$s). So $\frac{10^{p-1}-1}{3}$ is divisible by $p$

So $p$ followed by $p-1$ copies of $3$ is divisible by $p$ and will be composite

(For completeness, $33$ and $533$ are also composite)

Answer 3

.For someone who may not fully understand the hint by Robert.

Let $p$ be the original prime number

For p=2,3,5 we get

$$ 233333 = 353 \times 661 \\ 33 = 3 \times 11 \\ 533 = 13 \times 41 $$ (Тhanks to Divisor's Calculator)

So, assume $p$ to be different from all those.

By appending $n$ 3-s we get: $10^np+\frac{10^n-1}{3}$, so if we prove that $10^n-1$ is a multiple of $p$ for certain $n$, it means that so is also $\frac{10^n-1}{3}$, as $3$ and $p$ are co-prime, therefore the whole number is a multiple of $p$. This is a direct consequence of Little Fermat theorem, given that $10$ and $p$ are co-prime.

Here is another approach not based on Little Fermat's theorem, given that not everyone is familiar with it. Consider $p+1$ numbers of type 33...33. According to pigeonhole principle there will be two numbers A and B (А > B), having the same remainder when divided by $p$. Therefore $A-B=33..3300...0$ is divisible by $p$ while trailing zeroes can be dropped, as $10^k$ and $p$ are co-prime, as long as $p$ is different from 2 or 5.

Answer 4

Expanding on my comments above, this does not require primality at all. Let $N$ be the number obtained after appending one $3$, i.e. $10p+3$. Since $N$ is coprime to $10$, there exists some $k>0$ such that the concatenation of $k$ 3’s is divisible by $N$ (this does not require Euler’s theorem, just the pigeonhole principle to see that some pair of the sequence $3,33,333,\ldots$ are congruent mod $N$ and then factoring out powers of $10$).

It follows that $p$ appended with $k+1$ copies of $3$ is greater than $N$ and divisible by $N$, hence it is composite.

This avoids any special cases for small primes, simply by going forward one iteration to a prefix that is guaranteed to be coprime to $10$ (though not necessarily prime).