Введение
Простое число p, такое что p² делит 2^(p-1) - 1.
В теории чисел, число Вифериха – это простое число p, для которого p² делит 2^(p-1) - 1, тем самым связывая эти простые числа с малой теоремой Ферма, которая утверждает, что каждое нечетное простое число p делит 2^(p-1) - 1. Числа Вифериха были впервые описаны Артуром Виферихом в 1909 году в работах, касающихся последней теоремы Ферма, в то время как обе теоремы Ферма уже были хорошо известны математикам. С тех пор были обнаружены связи между числами Вифериха и различными другими областями математики, включая другие типы чисел и простых чисел, такие как числа Мерсенна и Ферма, специфические типы псевдопростых чисел и некоторые типы чисел, обобщенные из первоначального определения числа Вифериха. Со временем эти обнаруженные связи расширились, охватывая больше свойств определенных простых чисел, а также более общие темы, такие как поля чисел и гипотеза abc. На данный момент известны только два числа Вифериха: 1093 и 3511.
Эквивалентные определения
Более сильная версия малой теоремы Ферма, которую удовлетворяет простое число Вифериха, обычно выражается как сравнение 2^(p-1) ≡ 1 (mod p^2). Из определения сравнения для целых чисел следует, что это свойство эквивалентно определению, данному в начале. Таким образом, если простое число p удовлетворяет этому сравнению, то это простое число делит частное Ферма. Следующие два примера иллюстрируют это на простых числах 11 и 1093:
Для p = 11 получаем 2^(11-1) = 2^10 = 1024, что равно 93 и дает остаток 5 при делении на 11, следовательно, 11 не является простым числом Вифериха. Для p = 1093 получаем 2^(1093-1) = 2^1092, что равно 485439490310852893958515 (302 промежуточные цифры опущены для ясности), и это число дает остаток 0 при делении на 1093, таким образом, 1093 является простым числом Вифериха. Простые числа Вифериха могут быть определены другими эквивалентными сравнениями. Если p – простое число Вифериха, то можно умножить обе стороны сравнения 2^(p-1) ≡ 1 (mod p^2) на 2 и получить 2^p ≡ 2 (mod p^2). Возводя обе стороны сравнения в степень p, получаем, что простое число Вифериха также удовлетворяет 2^(p^2) ≡ 2^p ≡ 2 (mod p^2), и, следовательно, 2^(p^k) ≡ 2 (mod p^2) для всех k ≥ 1. Обратное также верно: если 2^(p^k) ≡ 2 (mod p^2) для некоторого k ≥ 1, то мультипликативный порядок 2 по модулю p^2 делит НОД(p^k - 1, φ(p^2)) = p - 1, то есть 2^(p-1) ≡ 1 (mod p^2), и, таким образом, p является простым числом Вифериха. Это также означает, что простые числа Вифериха можно определить как простые числа p, для которых мультипликативные порядки 2 по модулям p и p^2 совпадают: ord_(p^2) 2 = ord_p 2. (К слову, ord_1093 2 = 364, а ord_3511 2 = 1755). H. S. Vandiver доказал, что 2^(p-1) ≡ 1 (mod p^3) тогда и только тогда, когда…
For p = 11, we get which is 93 and leaves a remainder of 5 after division by 11, hence 11 is not a Wieferich prime. For p = 1093, we get or 485439490310 852893958515 (302 intermediate digits omitted for clarity), which leaves a remainder of 0 after division by 1093 and thus 1093 is a Wieferich prime. Wieferich primes can be defined by other equivalent congruences. If p is a Wieferich prime, one can multiply both sides of the congruence 1=2^(p−1) ≡ 1 (mod p^(2)) by 2 to get 1=2^(p) ≡ 2 (mod p^(2)). Raising both sides of the congruence to the power p shows that a Wieferich prime also satisfies 1=2^(p^(2)) ≡2^(p) ≡ 2 (mod p^(2)), and hence 1=2^(p^(k)) ≡ 2 (mod p^(2)) for all 1=k ≥ 1. The converse is also true: 1=2^(p^(k)) ≡ 2 (mod p^(2)) for some 1=k ≥ 1 implies that the multiplicative order of 2 modulo p2 divides gcd1=(p^(k) − 1, φ1=(p^(2))) = p − 1, that is, 1=2^(p−1) ≡ 1 (mod p^(2)) and thus p is a Wieferich prime. This also implies that Wieferich primes can be defined as primes p such that the multiplicative orders of 2 modulo p and modulo p2 coincide: 1=ordp^(2) 2 = ordp 2, (By the way, ord10932 = 364, and ord35112 = 1755). H. S. Vandiver proved that 1=2^(p−1) ≡ 1 (mod p^(3)) if and only if .
История и статус поиска
В 1902 году Мейер доказал теорему о решениях конгруэнции ap − 1 ≡ 1 (mod pr). Позже в этом десятилетии Артур Виферих показал, что если первый случай последней теоремы Ферма имеет решения для нечетного простого показателя, то этот простой должен удовлетворять конгруэнции для a = 2 и r = 2. Иными словами, если существуют решения xp + yp + zp = 0 в целых числах x, y, z и p – нечетный простой, причём p не делит xyz, то p удовлетворяет 2p − 1 ≡ 1 (mod p2). В 1913 году Бахман исследовал остатки, задаваясь вопросом, когда этот остаток обращается в ноль, и пытался найти выражения для ответа на этот вопрос. Простое число 1093 было обнаружено как простое число Вифериха lt=W. Мейснером в 1913 году и подтверждено как единственное такое число меньше 2000. Он вычислил наименьший остаток для всех простых чисел p < 2000 и обнаружил, что этот остаток равен нулю при t = 364 и p = 1093, тем самым предоставив контрпример к предположению Грейва о невозможности конгруэнции Вифериха. lt=E. Хаенцшель позже распорядился проверить правильность конгруэнции Мейснера исключительно элементарными вычислениями. Вдохновленный более ранней работой Эйлера, он упростил доказательство Мейснера, показав, что 10932 делит (2182 + 1) и отметил, что (2182 + 1) является делителем (2364 − 1). Также было показано, что можно доказать, что 1093 является простым числом Вифериха без использования комплексных чисел, в отличие от метода, использованного Мейснером, хотя сам Мейснер намекал, что он знал доказательство без комплексных значений. И еще одно доказательство того, что это простое число Вифериха, было опубликовано в 1965 году Гаем. В 1960 году Кравиц удвоил предыдущий рекорд, установленный lt=Фрёбергом, а в 1961 году Рисел расширил поиск до 500000 с помощью BESK. Около 1980 года Лемер смог достичь лимита поиска в 6. В 2006 году этот предел был увеличен до более чем 2,5. В 2007–2016 годах поиск простых чисел Вифериха осуществлялся распределенным вычислительным проектом Wieferich@Home. В 2011–2017 годах другой поиск был проведен проектом PrimeGrid, хотя позже работа, выполненная в этом проекте, была признана бесполезной. Хотя эти проекты достигли границ поиска выше 1, ни один из них не сообщил об устойчивых результатах. В 2020 году PrimeGrid начал новый проект, который одновременно ищет простые числа Вифериха и Уолл–Сан–Сан. Новый проект использует контрольные суммы для обеспечения независимой двойной проверки каждого подинтервала, тем самым минимизируя риск пропуска экземпляра из-за неисправного оборудования. Проект завершился в декабре 2022 года, окончательно доказав, что третье простое число Вифериха должно превышать 264 (около 18). Предполагается (как и для простых чисел Вильсона), что существует бесконечно много простых чисел Вифериха, и что количество простых чисел Вифериха, меньших x, приблизительно равно log(log(x)), что является эвристическим результатом, вытекающим из правдоподобного предположения, что для простого числа p корни 1-й степени из единицы по модулю p2 равномерно распределены в мультипликативной группе целых чисел по модулю p2. И FLTI считается неверным для простого p, если решения уравнения Ферма существуют для этого p, в противном случае FLTI выполняется для p. В 1910 году Мириманов расширил теорему, показав, что если предварительные условия теоремы выполняются для некоторого простого p, то p2 также должно делить 3^(p − 1) − 1. Гранвилл и Монаган дополнительно доказали, что p2 действительно должно делить m^(p − 1) − 1 для каждого простого m ≤ 89. Судзуки расширил доказательство на все простые числа m ≤ 113. Пусть Hp – это множество пар целых чисел с наибольшим общим делителем 1, причём p взаимно просто с x, y и x + y, (x + y)^(p−1) ≡ 1 (mod p2), (x + ξy) является p-й степенью идеала K, где ξ определено как cos 2π/p + i sin 2π/p. K = Q(ξ) – это расширение поля, полученное присоединением всех многочленов в алгебраическом числе ξ к полю рациональных чисел (такое расширение известно как числовое поле или, в этом конкретном случае, где ξ является корнем из единицы, циклотомическое числовое поле). Более точно он показал, что гипотеза abc подразумевает существование константы, зависящей только от α, такой что количество не-виферихских простых чисел до основания α с p, меньшим или равным переменной X, больше, чем log(X), когда X стремится к бесконечности. Численные данные свидетельствуют о том, что очень немногие из простых чисел в заданном интервале являются простыми числами Вифериха. Множество простых чисел Вифериха и множество не-Виферихских простых чисел, иногда обозначаемые W2 и W2c соответственно, являются дополнительными множествами, поэтому, если одно из них будет показано конечным, другое обязательно должно быть бесконечным. Позже было показано, что существование бесконечного числа не-Виферихских простых чисел уже следует из более слабой версии гипотезы abc, называемой ABC (k, ε)-гипотезой. Кроме того, существование бесконечного числа не-Виферихских простых чисел также будет следовать, если существует бесконечно много квадратных свободных чисел Мерсенна, а также если существует действительное число ξ такое, что множество {n ∈ N : λ(2n − 1) < 2 − ξ} имеет плотность 1, где индекс композиции λ(n) целого числа n определяется как и , что означает, что дает произведение всех простых множителей n. Таким образом, простое число Мерсенна не может быть также простым числом Вифериха. Заметной открытой проблемой является определение того, являются ли все числа Мерсенна с простым индексом квадратными свободными или нет. Если q – простое число, и число Мерсенна Mq не является квадратным свободным, то есть существует простое число p, для которого p2 делит Mq, то p является простым числом Вифериха. Следовательно, если существует только конечное число простых чисел Вифериха, то существует не более чем конечное число чисел Мерсенна с простым индексом, которые не являются квадратными свободными. Роткович показал связанный результат: если существует бесконечно много квадратных свободных чисел Мерсенна, то существует бесконечно много не-Виферихских простых чисел. Аналогично, если p – простое число, и p2 делит некоторое число Ферма Fn = 2^(2^n) + 1, то p должно быть простым числом Вифериха. Фактически, существует натуральное число n и простое число p, такое что p2 делит (где – n-й циклотомический многочлен) тогда и только тогда, когда p является простым числом Вифериха. Например, 10932 делит , 35112 делит . Числа Мерсенна и Ферма – это лишь частные случаи. Таким образом, если 1093 и 3511 – только два простых числа Вифериха, то все являются квадратными свободными, за исключением и (На самом деле, когда существует простое число p, для которого p2 делит некоторое , то это простое число Вифериха); и, очевидно, если является простым числом, то оно не может быть простым числом Вифериха. (Любое нечетное простое число p делит только одно и n делит 1=p − 1, и тогда и только тогда, когда длина периода 1/p в двоичной системе равна n, то p делит ). Кроме того, тогда и только тогда, когда p является простым числом Вифериха, длина периода 1/p и 1/p2 одинакова (в двоичной системе). В противном случае это p раз больше, чем это.) Для простых чисел 1093 и 3511 было показано, что ни одно из них не является делителем какого-либо числа Мерсенна с простым индексом и ни одного числа Ферма, поскольку 364 и 1755 не являются ни простыми числами, ни степенями 2.
In 2007–2016, a search for Wieferich primes was performed by the distributed computing project Wieferich@Home. In 2011–2017, another search was performed by the PrimeGrid project, although later the work done in this project was claimed wasted. While these projects reached search bounds above 1, neither of them reported any sustainable results. In 2020, PrimeGrid started another project that searches for Wieferich and Wall–Sun–Sun primes simultaneously. The new project uses checksums to enable independent double checking of each subinterval, thus minimizing the risk of missing an instance because of faulty hardware. The project ended in December 2022, definitely proving that a third Wieferich prime must exceed 264 (about 18). It has been conjectured (as for Wilson primes) that infinitely many Wieferich primes exist, and that the number of Wieferich primes below x is approximately log(log(x)), which is a heuristic result that follows from the plausible assumption that for a prime p, the 1=(p − 1) th degree roots of unity modulo p2 are uniformly distributed in the multiplicative group of integers modulo p2. and FLTI is said to fail for a prime p, if solutions to the Fermat equation exist for that p, otherwise FLTI holds for p.
In 1910, Mirimanoff expanded the theorem by showing that, if the preconditions of the theorem hold true for some prime p, then p2 must also divide 1=3^(p − 1) − 1. Granville and Monagan further proved that p2 must actually divide 1=m^(p − 1) − 1 for every prime m ≤ 89. Suzuki extended the proof to all primes m ≤ 113. Let Hp be a set of pairs of integers with 1 as their greatest common divisor, p being prime to x, y and x + y, (x + y)p−1 ≡ 1 (mod p2), (x + ξy) being the pth power of an ideal of K with ξ defined as cos 2π/p + i sin 2π/p. K = Q(ξ) is the field extension obtained by adjoining all polynomials in the algebraic number ξ to the field of rational numbers (such an extension is known as a number field or in this particular case, where ξ is a root of unity, a cyclotomic number field). More precisely he showed that the abc conjecture implies the existence of a constant only depending on α such that the number of non Wieferich primes to base α with p less than or equal to a variable X is greater than log(X) as X goes to infinity. Numerical evidence suggests that very few of the prime numbers in a given interval are Wieferich primes. The set of Wieferich primes and the set of non Wieferich primes, sometimes denoted by W2 and W2c respectively, are complementary sets, so if one of them is shown to be finite, the other one would necessarily have to be infinite. It was later shown that the existence of infinitely many non Wieferich primes already follows from a weaker version of the abc conjecture, called the ABC (k, ε) conjecture. Additionally, the existence of infinitely many non Wieferich primes would also follow if there exist infinitely many square free Mersenne numbers as well as if there exists a real number ξ such that the set {n ∈ N : λ(2n − 1) < 2 − ξ} is of density one, where the index of composition λ(n) of an integer n is defined as and , meaning gives the product of all prime factors of n.
Thus, a Mersenne prime cannot also be a Wieferich prime. A notable open problem is to determine whether or not all Mersenne numbers of prime index are square free. If q is prime and the Mersenne number Mq is not square free, that is, there exists a prime p for which p2 divides Mq, then p is a Wieferich prime. Therefore, if there are only finitely many Wieferich primes, then there will be at most finitely many Mersenne numbers with prime index that are not square free. Rotkiewicz showed a related result: if there are infinitely many square free Mersenne numbers, then there are infinitely many non Wieferich primes. Similarly, if p is prime and p2 divides some Fermat number Fn 1== 2^(2^(n)) + 1, then p must be a Wieferich prime. In fact, there exists a natural number n and a prime p that p2 divides (where is the n th cyclotomic polynomial) if and only if p is a Wieferich prime. For example, 10932 divides , 35112 divides Mersenne and Fermat numbers are just special situations of Thus, if 1093 and 3511 are only two Wieferich primes, then all are square free except and (In fact, when there exists a prime p which p2 divides some , then it is a Wieferich prime); and clearly, if is a prime, then it cannot be Wieferich prime. (Any odd prime p divides only one and n divides 1=p − 1, and if and only if the period length of 1/p in binary is n, then p divides Besides, if and only if p is a Wieferich prime, then the period length of 1/p and 1/p2 are the same (in binary). Otherwise, this is p times than that.) For the primes 1093 and 3511, it was shown that neither of them is a divisor of any Mersenne number with prime index nor a divisor of any Fermat number, because 364 and 1755 are neither prime nor powers of 2.
Связь с другими уравнениями
Скотт и Стайер показали, что уравнение px – 2y = d имеет не более одного решения в положительных целых числах (x, y), за исключением случаев, когда p⁴ делит 2ordp 2 – 1, если p не сравнимо с 65 по модулю 192, или безусловно, когда p² делит 2ordp 2 – 1, где ordp 2 обозначает мультипликативный порядок 2 по модулю p. Они также показали, что решение уравнения ±ax₁ ± 2y₁ = ±ax₂ ± 2y₂ = c должно принадлежать определенному набору уравнений, но это не выполняется, если a является простым числом Вейфериха, большим 1,25 x 10¹⁵.
Бинарная периодичность p - 1
Джонсон заметил, что два известных простых числа Вифериха на единицу больше чисел с периодическим двоичным представлением (1092 = 0100010001002 = 44416; 3510 = 1101101101102 = 66668). Проект Wieferich@Home искал простые числа Вифериха, проверяя числа, которые на единицу больше числа с периодическим двоичным представлением, но до "псевдодлины битов" в 3500 среди протестированных двоичных чисел, сгенерированных комбинацией битовых строк длиной до 24 бит, новых простых чисел Вифериха обнаружено не было.
Обычность p - 1
Было отмечено, что известные простые числа Вифериха на единицу больше, чем взаимно дружественные числа (общий индекс избыточности равен 112/39).
Связь с псевдопримами
Было замечено, что два известных простых числа Вифериха являются квадратными факторами всех не свободно-квадратных псевдопримов Ферма с основанием 2 до 25. Последующие вычисления показали, что единственными повторяющимися факторами псевдопримов до 1012 являются 1093 и 3511. Кроме того, существует следующая связь: пусть n – псевдопростое число с основанием 2, а p – простое делитель n. Если , то также . Было показано, что для всех нечетных простых чисел либо 1=L(p^(n+1)) = p · L(p^(n)) или 1=L(p^(n+1)) = L(p^(n)). Более того, был получен следующий результат: пусть q – нечетное простое число, k и p – простые числа, такие что 1=p = 2k + 1, k ≡ 3 (mod 4), p ≡ −1 (mod q), p ≢ −1 (mod q^(3)), а порядок q по модулю k равен . Предположим, что q делит h+, число класса действительного циклотомического поля , циклотомического поля, полученного присоединением суммы p-го корня из единицы и его обратной величины к полю рациональных чисел. Тогда q является простым числом Вифериха. Это также верно, если условия p ≡ −1 (mod q) и p ≢ −1 (mod q^(3)) заменяются условиями p ≡ −3 (mod q) и p ≢ −3 (mod q^(3)), а также когда условие p ≡ −1 (mod q) заменяется условием p ≡ −5 (mod q) (в этом случае q является простым числом Уолл-Сан-Сан) и условие несовместимости заменяется условием p ≢ −5 (mod q^(3)).
Let n be a base 2 pseudoprime and p be a prime divisor of n. If , then also It was shown, that for all odd prime numbers either 1=L(p^(n+1)) = p · L(p^(n)) or 1=L(p^(n+1)) = L(p^(n)). Furthermore, the following result was obtained: Let q be an odd prime number, k and p are primes such that 1=p = 2k + 1, k ≡ 3 (mod 4), p ≡ −1 (mod q), p ≢ −1 (mod q^(3)) and the order of q modulo k is Assume that q divides h+, the class number of the real cyclotomic field , the cyclotomic field obtained by adjoining the sum of a p th root of unity and its reciprocal to the field of rational numbers. Then q is a Wieferich prime. This also holds if the conditions p ≡ −1 (mod q) and p ≢ −1 (mod q^(3)) are replaced by p ≡ −3 (mod q) and p ≢ −3 (mod q^(3)) as well as when the condition p ≡ −1 (mod q) is replaced by p ≡ −5 (mod q) (in which case q is a Wall–Sun–Sun prime) and the incongruence condition replaced by p ≢ −5 (mod q^(3)).
Числа Вифериха
Число Вифериха — это нечётное натуральное число n, удовлетворяющее конгруэнции 2(n) ≡ 1 (mod n²), где φ обозначает функцию Эйлера (согласно теореме Эйлера, 2(n) ≡ 1 (mod n) для каждого нечётного натурального числа n). Если число Вифериха n является простым, то оно называется простым числом Вифериха. Первые несколько чисел Вифериха: 1, 1093, 3279, 3511, 7651, 10533, 14209, 17555, 22953, 31599, 42627, 45643, 52665, 68859, 94797, 99463. Можно показать, что если существует лишь конечное число простых чисел Вифериха, то существует лишь конечное число чисел Вифериха. В частности, если единственными простыми числами Вифериха являются 1093 и 3511, то существует ровно 104 числа Вифериха, что соответствует количеству чисел Вифериха, известных на данный момент. Другое определение определяет число Вифериха как нечётное натуральное число n, такое, что n и φ(n) не являются взаимно простыми, где φ(n) — мультипликативный порядок 2 по модулю n. Первые из этих чисел: 21, 39, 55, 57, 105, 111, 147, 155, 165, 171, 183, 195, 201, 203, 205, 219, 231, 237, 253, 273, 285, 291, 301, 305, 309, 327, 333, 355, 357, 385, 399. Как и выше, если число Вифериха q является простым, то оно называется простым числом Вифериха.
1, 1093, 3279, 3511, 7651, 10533, 14209, 17555, 22953, 31599, 42627, 45643, 52665, 68859, 94797, 99463,
It can be shown that if there are only finitely many Wieferich primes, then there are only finitely many Wieferich numbers. In particular, if the only Wieferich primes are 1093 and 3511, then there exist exactly 104 Wieferich numbers, which matches the number of Wieferich numbers currently known. Another definition specifies a Wieferich number as odd natural number n such that n and are not coprime, where m is the multiplicative order of 2 modulo n. The first of these numbers are:
21, 39, 55, 57, 105, 111, 147, 155, 165, 171, 183, 195, 201, 203, 205, 219, 231, 237, 253, 273, 285, 291, 301, 305, 309, 327, 333, 355, 357, 385, 399,
As above, if Wieferich number q is prime, then it is a Wieferich prime.
LucasWieferich простые числа
Пусть P и Q – целые числа. Последовательность Лукаса первого рода, связанная с парой (P, Q), определяется для всех A. Простым числом Лукаса–Вифериха, связанным с (P, Q), называется простое число p, такое что Up−ε(P, Q) ≡ 0 (mod p2), где ε – символ Лежандра. Все простые числа Вифериха являются простыми числами Лукаса–Вифериха, связанными с парой (3, 2).
for all A Lucas–Wieferich prime associated with (P, Q) is a prime p such that Up−ε(P, Q) ≡ 0 (mod p2), where ε equals the Legendre symbol All Wieferich primes are Lucas–Wieferich primes associated with the pair (3, 2).