# Is 75986⋯69 ever prime or is there a 6 padded prime for every prime $p > 5$?

I came across this question: How can we turn any number into a prime number by simply adding more digits? While trying different approaches to find an algorithm that increases the chances of finding a prime this way I discovered the six padded primes:

Start with an prime $p>5$ then add a digit 6 before the last digit, repeat the process until the result is prime. This table shows the results for p up to 100: \begin{align*} 7 && 67 \\ 11 && 16661 \\ 13 && 163 \\ 17 && 167 \\ 19 && 1669 \\ 23 && 263 \\ 29 && 269 \\ 31 && 3666661 \\ 37 && 367 \\ 41 && 461 \\ 43 && 463 \\ 47 && 467 \\ 53 && 563 \\ 59 && 569 \\ 61 && 661 \\ 67 && 666667 \\ 71 && 761 \\ 73 && 76666663 \\ 79 && 769 \\ 83 && 863 \\ 89 && 8669 \\ 97 && 967 \\ \end{align*} There were only 2 numbers below $200000$ for which I could not find a result: $15731$ and $75989$. My computer finally found a solution for the first padded with 7460 sixes resulting in a 7465 digit prime number. $75989$ was checked up to 15000 digits.

Question:

Is $75986\cdots69$ ever prime or can it be proved there is a six padded prime for every prime > 5

• For an odd number of $6$'s, it is easy to prove that the number is divisible by $11$. For an even number of added $6$'s of the form $n=2+6k$ Mathematica suggests the number to be a multiple of $13$, while for $n=4+6k$ the number seems to be a multiple of $37$. For $n=6k$ I couldn't detect any easy pattern. Aug 5, 2017 at 10:35
• 75986⋯69 is a strong possible prime for n=32190. The next p with a larger solution is 212627 no result for n<=27877. Aug 15, 2017 at 7:05
• I just tried that with Mathematica and it tells it's indeed a prime! I don't know if Mathematica's function PrimeQ can be considered a conclusive test, but that's a strong indication that for $n=32190$ the number is prime. Aug 15, 2017 at 7:35

If you insert an odd number of $6$'s, it is simple to check that the resulting number is a multiple of $11$ (just use the divisibility criterion).

For an even number $n$ of $6$'s, notice that $$759866\equiv 3\pmod{13},\quad 1000000\equiv 1\pmod{13},\quad 666666\equiv 0\pmod{13},$$ and $$75986666\equiv 25\pmod{37},\quad 1000000\equiv 1\pmod{37},\quad 666666\equiv 0\pmod{37}.$$ Hence when $n=2+6k$ the number is a multiple of $13$, and when $n=4+6k$ the number is a multiple of $37$.

At the moment, I can say nothing for the case $n=6k$.

EDIT.

Playing around with Mathematica I noticed some other regularities (which I didn't bother to prove):

• for $n=6(1+7k)$ the number is a multiple of $43$;
• for $n=6(4+8k)$ the number is a multiple of $17$;
• for $n=6(4+5k)$ the number is a multiple of $31$.

On the other hand, there are several cases where the number has only two prime factors, both large. At the moment, however, I could find no trace of a prime number.