Перемутируемые простые числа: свойства и критерии

Введение

Пермутабельное простое число, также известное как анаграмматическое простое число, — это простое число, которое в заданной системе счисления остаётся простым числом при любой перестановке его цифр. Г. Э. Рихерт, предположительно первый, кто изучал такие простые числа, назвал их пермутабельными простыми числами, но позже они также стали называться абсолютными простыми числами.

База 2

В системе счисления по основанию 2 пермитуемыми простыми числами могут быть только репуниты, поскольку любая цифра 0, переставленная в разряд единиц, приводит к четному числу. Следовательно, пермитуемые простые числа в двоичной системе счисления – это числа Мерсена. Можно с уверенностью утверждать, что для любой позиционной системы счисления пермитуемые простые числа, состоящие более чем из одной цифры, могут содержать только цифры, взаимно простые с основанием системы счисления. Однозначные простые числа, то есть любые простые числа, меньшие основания, всегда являются тривиально пермутируемыми.

Свободные основания

Пусть P(b, n, x, y) – переставляемое простое число в основании b, и пусть p – простое число, такое что n ≥ p. Если b – примитивный корень по модулю p, и p не делит x или |x − y|, то n кратно (p − 1). (Поскольку b – примитивный корень по модулю p и p не делит |x − y|, то числа xxxx…xxxy, xxxx…xxyx, xxxx…xyxx, …, xxxx…xyxx…xxxx (только bp−2-я цифра – y, остальные – все x), xxxx…yxxx…xxxx (только bp−1-я цифра – y, остальные – все x), xxxx…xxxx (репунит с n цифрами x) по модулю p различны. То есть, одно равно 0, другое – 1, другое – 2, …, другое – p − 1. Таким образом, поскольку первые p − 1 чисел – простые, последнее число (репунит с n цифрами x) должно делиться на p. Поскольку p не делит x, то p должно делить репунит с n единицами. Поскольку b – примитивный корень по модулю p, мультипликативный порядок n по модулю p равен p − 1. Таким образом, n должно быть делимо на p − 1.) Таким образом, если b = 10, то цифры, взаимно простые с 10, – {1, 3, 7, 9}. Поскольку 10 – примитивный корень по модулю 7, то если n ≥ 7, то либо 7 делит x (в этом случае x = 7, поскольку x ∈ {1, 3, 7, 9}) или |x − y| (в этом случае x = y = 1, поскольку x, y ∈ {1, 3, 7, 9}. То есть, простое число – репунит) или n кратно 7 − 1 = 6. Аналогично, поскольку 10 – примитивный корень по модулю 17, то если n ≥ 17, то либо 17 делит x (невозможно, так как x ∈ {1, 3, 7, 9}) или |x − y| (в этом случае x = y = 1, так как x, y ∈ {1, 3, 7, 9}. То есть, простое число – репунит) или n кратно 17 − 1 = 16. Кроме того, 10 также является примитивным корнем по модулю 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, …, поэтому n ≥ 17 крайне маловероятно (поскольку для этих простых чисел p, если n ≥ p, то n делится на p − 1), а если 7 ≤ n < 17, то x = 7 или n кратно 6 (единственное возможное n – 12). Если b = 12, то цифры, взаимно простые с 12, – {1, 5, 7, 11}. Поскольку 12 – примитивный корень по модулю 5, то если n ≥ 5, то либо 5 делит x (в этом случае x = 5, поскольку x ∈ {1, 5, 7, 11}) или |x − y| (в этом случае либо x = y = 1 (то есть, простое число – репунит) или x = 1, y = 11 или x = 11, y = 1, поскольку x, y ∈ {1, 5, 7, 11}.) или n кратно 5 − 1 = 4. Аналогично, поскольку 12 – примитивный корень по модулю 7, то если n ≥ 7, то либо 7 делит x (в этом случае x = 7, поскольку x ∈ {1, 5, 7, 11}) или |x − y| (в этом случае x = y = 1, поскольку x, y ∈ {1, 5, 7, 11}. То есть, простое число – репунит) или n кратно 7 − 1 = 6. Аналогично, поскольку 12 – примитивный корень по модулю 17, то если n ≥ 17, то либо 17 делит x (невозможно, так как x ∈ {1, 5, 7, 11}) или |x − y| (в этом случае x = y = 1, так как x, y ∈ {1, 5, 7, 11}. То есть, простое число – репунит) или n кратно 17 − 1 = 16. Кроме того, 12 также является примитивным корнем по модулю 31, 41, 43, 53, 67, 101, 103, 113, 127, 137, 139, 149, 151, 163, 173, 197, …, поэтому n ≥ 17 крайне маловероятно (поскольку для этих простых чисел p, если n ≥ p, то n делится на p − 1), а если 7 ≤ n < 17, то x = 7 (в этом случае, поскольку 5 не делит x или x − y, то n должно делиться на 4) или n кратно 6 (единственное возможное n – 12).

Let P(b, n, x, y) be a permutable prime in base b and let p be a prime such that n ≥ p. If b is a primitive root of p, and p does not divide x or |x y|, then n is a multiple of p 1. (Since b is a primitive root mod p and p does not divide |x − y|, the p numbers xxxx xxxy, xxxx xxyx, xxxx xyxx, , xxxx xyxx xxxx (only the bp−2 digit is y, others are all x), xxxx yxxx xxxx (only the bp−1 digit is y, others are all x), xxxx xxxx (the repdigit with n xs) mod p are all different. That is, one is 0, another is 1, another is 2, , the other is p − 1. Thus, since the first p − 1 numbers are all primes, the last number (the repdigit with n xs) must be divisible by p. Since p does not divide x, so p must divide the repunit with n 1s. Since b is a primitive root mod p, the multiplicative order of n mod p is p − 1. Thus, n must be divisible by p − 1.) Thus, if b = 10, the digits coprime to 10 are {1, 3, 7, 9}. Since 10 is a primitive root mod 7, so if n ≥ 7, then either 7 divides x (in this case, x = 7, since x ∈ {1, 3, 7, 9}) or |x − y| (in this case, x = y = 1, since x, y ∈ {1, 3, 7, 9}. That is, the prime is a repunit) or n is a multiple of 7 − 1 = 6. Similarly, since 10 is a primitive root mod 17, so if n ≥ 17, then either 17 divides x (not possible, since x ∈ {1, 3, 7, 9}) or |x − y| (in this case, x = y = 1, since x, y ∈ {1, 3, 7, 9}. That is, the prime is a repunit) or n is a multiple of 17 − 1 = 16. Besides, 10 is also a primitive root mod 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, , so n ≥ 17 is very impossible (since for this primes p, if n ≥ p, then n is divisible by p − 1), and if 7 ≤ n < 17, then x = 7, or n is divisible by 6 (the only possible n is 12). If b = 12, the digits coprime to 12 are {1, 5, 7, 11}. Since 12 is a primitive root mod 5, so if n ≥ 5, then either 5 divides x (in this case, x = 5, since x ∈ {1, 5, 7, 11}) or |x − y| (in this case, either x = y = 1 (That is, the prime is a repunit) or x = 1, y = 11 or x = 11, y = 1, since x, y ∈ {1, 5, 7, 11}.) or n is a multiple of 5 − 1 = 4. Similarly, since 12 is a primitive root mod 7, so if n ≥ 7, then either 7 divides x (in this case, x = 7, since x ∈ {1, 5, 7, 11}) or |x − y| (in this case, x = y = 1, since x, y ∈ {1, 5, 7, 11}. That is, the prime is a repunit) or n is a multiple of 7 − 1 = 6. Similarly, since 12 is a primitive root mod 17, so if n ≥ 17, then either 17 divides x (not possible, since x ∈ {1, 5, 7, 11}) or |x − y| (in this case, x = y = 1, since x, y ∈ {1, 5, 7, 11}. That is, the prime is a repunit) or n is a multiple of 17 − 1 = 16. Besides, 12 is also a primitive root mod 31, 41, 43, 53, 67, 101, 103, 113, 127, 137, 139, 149, 151, 163, 173, 197, , so n ≥ 17 is very impossible (since for this primes p, if n ≥ p, then n is divisible by p − 1), and if 7 ≤ n < 17, then x = 7 (in this case, since 5 does not divide x or x − y, so n must be divisible by 4) or n is divisible by 6 (the only possible n is 12).