On the determination of permutable primes

by David Radcliffe

Edit: I have to retract this proof. It was pointed out to me that 10^k covers only 16 of the 17 congruence classes modulo 17, so the last step fails. The other steps are valid, and they show that a permutable prime greater than 991 must be a near-repdigit (all but one of the digits are equal) or a repunit.

A permutable prime (also called an absolute prime) is a prime number such that all of its digit permutations (in base 10) are prime. For example, 113 is a permutable prime, since each of the numbers 113, 131, and 311 are prime. Note that all permutable primes greater than 5 are composed of the digits 1, 3, 7, and 9. The following is a complete list of the permutable primes less than 1000.

2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 199, 311, 337, 373, 733, 919, 991

A repunit prime is a prime number that contains only the digit 1. Every repunit prime is permutable, and it is conjectured (but not proved) that there exist infinitely many repunit primes. I will prove that the above list contains every permutable prime, with the exception of repunit primes greater than 11.

The proof is based on the following observation. If N and m are integers greater than 1 such that the digit permutations of N cover all congruence classes modulo m, then every number containing the digits of N (as a multiset) is composite. We can find a finite number of pairs (N, m) that will cover every case; however, the number of cases is too large to check by hand. The complete proof was generated by a Python script, and the output is available here.

The first step is to find all permutable primes less than 106 by brute force search. We use the Miller-Rabin primality test (code is here). This is a probabilistic test, but we are not overly concerned with false positives, because we would run a separate deterministic test on any new candidate primes that were identified.

The second step is to verify that a permutable prime cannot contain all four of the digits 1, 3, 7, and 9, by showing that the permutations of 1379 cover all congruence classes modulo 7.

The third step is to verify that a permutable prime cannot contain exactly three of the four digits 1, 3, 7, and 9. There are two sub-cases: the number contains two digits that are repeated at least twice, or the number contains a digit that is repeated five or more times These sub-cases are denoted aabbc and aaaaabc, respectively. As in the previous case, we show that the permutations cover all congruence classes modulo 7. These two sub-cases cover all of the remaining possibilities, since we checked all numbers having fewer than seven digits in step 1.

The fourth step is to verify that a permutable prime cannot contain exactly two of the four digits 1, 3, 7, and 9, unless it is less than 106. There are two sub-cases: the number contains two digits that are repeated at least twice (such as 11133), or the number has all digits the same except for one (such as 11113). For the first sub-case, we consider permutations modulo 7 as before. Unfortunately, there is no proof of the second sub-case using modulo 7 arithmetic, so we must work harder.

Suppose that N is a positive integer with at least 17 digits, all of which are equal to a, except for the last digit which is equal to b. Then the following 17 numbers are digit permutations of N.

N - (b-a) + (b-a) 10^k\quad (0 \le k \le 16)

Since 10 is a primitive root modulo 17, these numbers cover all congruence classes. Therefore, N cannot be a permutable prime.

It remains to check that there do not exist any permutable primes of the form aaa…ab that have between 7 and 16 digits. We do this by checking each candidate with a Miller-Rabin primality test. This exhausts all of the possible cases, so the proof is complete.

Since 10 is a primitive root modulo 17, these numbers cover all congruence classes, except the one belonging to N - (b-a). Therefore, N cannot be a permutable prime unless  N - (b-a) \equiv 0 \pmod{17} , which happens when the number of digits of N is a multiple of 16.

Advertisements