Простое число Вифериха

Следующая теорема, доказанная Виферихом в 1909-м, связывает простые числа Вифериха и великую теорему Ферма:[21]

Пусть ${\displaystyle p}$ – простое, и пусть ${\displaystyle x,y,z}$ – целые числа, такие, что ${\displaystyle x^{p}+y^{p}+z^{p}=0}$. Предположим далее, что ${\displaystyle p}$ не делит произведение ${\displaystyle xyz}$. Тогда ${\displaystyle p}$ – простое число Вифериха.

Условие «где ${\displaystyle p}$ не делит любое из ${\displaystyle x,y}$ или ${\displaystyle z}$» известно как первый случай великой теоремы Ферма (FLTI)[22][23]. FLTI неверна для простого ${\displaystyle p}$, если решение уравнения Ферма существует для ${\displaystyle p}$, в противном случае FLTI для ${\displaystyle p}$ выполняется[24]. В 1910-м году Мириманов расширил[25] теорему, показав, что, если условия теоремы выполняются для некоторого простого ${\displaystyle p}$, то ${\displaystyle p^{2}}$ должно также делить ${\displaystyle 3^{p-1}-1}$. Позднее Гранвиль (Granville) и Монаган (Monagan) доказали, что ${\displaystyle p^{2}}$ должно делить ${\displaystyle m^{p-1}-1}$ для любого простого ${\displaystyle m\leqslant 89}$.[26] Судзуки (Suzuki) распространил доказательство на все простые ${\displaystyle m\leqslant 113}$.[27]

Пусть ${\displaystyle H_{p}}$ – множество пар целых и их наибольший общий делитель равен 1.

Пусть ${\displaystyle \xi =\cos 2\pi /p+i\sin 2\pi /p}$, ${\displaystyle K=\mathbb {Q} (\xi )}$ является расширением поля, получаемого включением всех многочленов от алгебраического числа ${\displaystyle \xi }$ в поле рациональных числ (такое расширение известно как числовое поле или, в данном случае, где ξ — корни из единицы, круговым числовым полем).[26]^:332

Пусть ${\displaystyle H_{p}}$ – множество пар ${\displaystyle (x,y)}$, удовлетворяющих свойствам:

• i НОД${\displaystyle (x,y)=1}$
• ii ${\displaystyle p}$ — взаимно просто с ${\displaystyle x,y}$ и ${\displaystyle x+y}$
• iii ${\displaystyle (x+y)^{p-1}\equiv 1{\pmod {p^{2}}}}$
• iv ${\displaystyle x+\xi y}$ – ${\displaystyle p}$-ая степень идеала ${\displaystyle K}$.

Из единственности факторизации идеалов в ${\displaystyle \mathbb {Q} (\xi )}$ следует, что если ${\displaystyle x,y,z}$ являются решением (первого случая) великой теоремы Ферма, то ${\displaystyle p}$ делит ${\displaystyle x+y+z}$, а ${\displaystyle (x,y),(y,z)}$ и ${\displaystyle (z,x)}$ являются элементами ${\displaystyle H_{p}}$.[26]^:333 Гранвиль (Granville) и Монаган (Monagan) показали, что ${\displaystyle (1,1)\in H_{p}}$ тогда и только тогда, когда ${\displaystyle p}$ является простым числом Вифериха.[26]^:333

Простое число не-Вифериха – это простое ${\displaystyle p}$, удовлетворяющее условию ${\displaystyle 2^{p-1}\not \equiv 1{\pmod {p^{2}}}}$. Д.Х. Силвермен (Joseph H. Silverman) в 1988-м году показал, что если abc-гипотеза верна, то существует бесконечно много простых не-Вифериха.[28]

Говоря точнее, он показал, что из верности abc-гипотезы следует, что количество простых не-Вифериха для ${\displaystyle p<X}$ больше ${\displaystyle C\ln X}$ для некоторой константы ${\displaystyle C}$.[29]^:227

Множество простых чисел Вифериха и множество простых не-Вифериха, иногда обозначаемые как ${\displaystyle W_{1}}$ и ${\displaystyle W_{2}^{c}}$ соответственно,[30] являются дополнительными множествами, так что конечность одного из них влечет бесконечность другого (поскольку вместе они дают множество простых чисел). Было показано, что существование бесконечного количества чисел не-Вифериха следует из ослабленной версии abc-гипотезы, называемой ABC-(k, ε) гипотезой[31].

Вдобавок существование бесконечного количества чисел не-Вифериха вытекает также из существования бесконечного количества свободных от квадратов чисел Мерсенна[32].

Это же вытекает из существования вещественного ${\displaystyle \xi }$, такого, что множество ${\displaystyle \{n\in \mathbb {N}$ :\lambda (2^{n}-1)<2-\xi \}} имеет плотность 1. Здесь индекс сложности ${\displaystyle \lambda (n)}$ для целого ${\displaystyle n}$ определяется как ${\displaystyle {\tfrac {\log n}{\log \gamma (n)}}}$ и ${\displaystyle \gamma (n)=\prod _{p\mid n}p}$, где ${\displaystyle \gamma (n)}$ — произведение всех простых множителй n.[30]^:4

Известно, что ${\displaystyle n}$-ое число Мерсенна ${\displaystyle M_{n}=2^{n}-1}$ является простым, только если ${\displaystyle n}$ – простое. Из малой теоремы Ферма следует, что, если ${\displaystyle p>2}$ является простым, ${\displaystyle M_{p-1}(=2^{p-1}-1)}$ делится на ${\displaystyle p}$. Поскольку числа Мерсенна с простыми индексами ${\displaystyle M_{p}}$ и ${\displaystyle M_{q}}$ взаимно просты, простой делитель ${\displaystyle p}$ числа ${\displaystyle M_{q}}$, где ${\displaystyle q}$ – простое, является простым числом Вифериха тогда и только тогда, когда ${\displaystyle p^{2}}$ делит ${\displaystyle M_{q}}$.[33]

Таким образом, простое число Мерсенна не может быть также простым Вифериха.

Интересная проблема остается нерешенной: все ли числа Мерсенна с простым индексом свободны от квадратов. Если число Мерсенна ${\displaystyle M_{q}}$ не свободно от квадратов, то существует простое ${\displaystyle p}$, для которого ${\displaystyle p^{2}}$ делит ${\displaystyle M_{q}}$, что означает, что ${\displaystyle p}$ – простое число Вифериха. Таким образом, если простых чисел Вифериха конечное число, то должно быть по меньшей мере конечное число не свободных от квадратов чисел Мерсенна. Роткевич (Rotkiewicz) показал, что обратное тоже верно, то есть, если имеется бесконечно много свободных от квадратов чисел Мерсенна, то и простых чисел не-Вифериха тоже бесконечно много.[34]

Подобным образом, если ${\displaystyle p}$ – простое, и ${\displaystyle p^{2}}$ делит число Ферма ${\displaystyle F_{n}=2^{2^{n}}+1}$, то ${\displaystyle p}$ должно быть простым числом Вифериха[35].

Для простых 1093 и 3511 было показано, что ни одно из них не является делителем какого-либо числа Мерсенна или Ферма[36].

Скотт (Scott) и Стайер (Styer) показали, что равенство ${\displaystyle p^{x}-2^{y}=d}$ имеет максимум одно решение в положительных целых ${\displaystyle (x,y)}$, если ${\displaystyle p^{4}\nmid 2^{\operatorname {ord} _{p}(2)}-1}$ при ${\displaystyle p\not \equiv 65{\pmod {192}}}$ или ${\displaystyle p^{2}\nmid 2^{\operatorname {ord} _{p}(2)}-1}$, где ${\displaystyle \operatorname {ord} _{p}(2)}$ означает мультипликативный порядок числа 2 по модулю ${\displaystyle p}$.[37]^{:215, 217–218}

Они также показали, что решения уравнения ${\displaystyle \pm a^{x_{1}}\pm 2^{y_{1}}=\pm a^{x_{2}}\pm 2^{y_{2}}=c}$ должны принадлежать определенному множеству, но утверждение перестает быть верным, если ${\displaystyle a}$ – простое число Вифериха, большее ${\displaystyle 1{,}25\times 10^{15}}$.[38]^:258

Джонсон (Johnson) заметил[39], что два известных простых числа Вифериха на единицу больше чисел с периодическим двоичным представлением (${\displaystyle 1092=010001000100_{2};\ 3510=110110110110_{2}}$). Проект Wieferich@Home ищет простые числа Вифериха путём проверки чисел, на единицу больших чисел с периодическим двоичным представлением, но среди чисел длиной до 3500 бит и периодом до 24 бит не было найдено ни одного нового простого числа Вифериха[40].

Простые числа Вифериха могут быть определены другим сравнением, эквивалентным тому, которое обычно используют.

Если ${\displaystyle p}$ простое число Вифериха, можно умножить обе части сравнения ${\displaystyle 2^{p-1}\equiv 1{\pmod {p^{2}}}}$ на 2 и получим ${\displaystyle 2^{p}\equiv 2{\pmod {p^{2}}}}$. Возведя обе части сравнения в степень ${\displaystyle p}$, получим ${\displaystyle 2^{p^{2}}\equiv 2^{p}\equiv 2{\pmod {p^{2}}}}$, откуда ${\displaystyle 2^{p^{k}}\equiv 2{\pmod {p^{2}}}}$ для всех ${\displaystyle k\geqslant 1}$.

Обратное тоже верно: Из ${\displaystyle 2^{p^{k}}\equiv 2{\pmod {p^{2}}}}$ для всех ${\displaystyle k\geqslant 1}$ следует, что мультипликативный порядок числа 2 по модулю ${\displaystyle p^{2}}$ делит НОД${\displaystyle (p^{k}-1,\varphi (p^{2}))=p-1}$, где ${\displaystyle \varphi }$ -функция Эйлера, так что, ${\displaystyle 2^{p-1}\equiv 1{\pmod {p^{2}}}}$ и число ${\displaystyle p}$ является простым Вифериха.

Бояи показал, что если ${\displaystyle p}$ и ${\displaystyle q}$ просты, ${\displaystyle a}$ – положительное целое, не делящееся на ${\displaystyle p}$ и ${\displaystyle q}$, такое, что ${\displaystyle a^{p-1}\equiv 1{\pmod {q}},\ a^{q-1}\equiv 1{\pmod {p}}}$, то ${\displaystyle a^{pq-1}\equiv 1{\pmod {pq}}}$. Полагая ${\displaystyle p=q}$, получим ${\displaystyle a^{p^{2}-1}\equiv 1{\pmod {p^{2}}}}$.[41]^:284 А ${\displaystyle a^{p^{2}-1}\equiv 1{\pmod {p^{2}}}}$ в силу теоремы Эйлера равносильно ${\displaystyle a^{p-1}\equiv 1{\pmod {p^{2}}}}$.[41]^:285-286

Было замечено, что оба известных простых числа Вифериха делят все несвободные от квадратов по базе 2 псевдопростые числа до ${\displaystyle 25\cdot 10^{9}}$.[42] Более поздние вычисления показали, что повторяющимися множителями псевдопростых чисел до ${\displaystyle 10^{12}}$ являются только 1093 и 3511.[43]

Существует следующая связь: Пусть ${\displaystyle n}$ — псевдопростое по базису 2 и ${\displaystyle p}$ — простой делитель ${\displaystyle n}$. Если ${\displaystyle {\tfrac {2^{n-1}-1}{n}}\not \equiv 0{\pmod {p}}}$, то ${\displaystyle {\tfrac {2^{p-1}-1}{p}}\not \equiv 0{\pmod {p}}}$.[24]^:378

Далее, если ${\displaystyle p}$ — простое число Вифериха, то ${\displaystyle p^{2}}$ псевдопростое Каталана (Catalan)[44].

Для всех простых до 100000 ${\displaystyle L(p^{n+1})=L(p^{n})}$ только в двух случаях: ${\displaystyle L(1093^{2})=L(1093)=364}$ и ${\displaystyle L(3511^{2})=L(3511)=1755}$, где ${\displaystyle m}$ – модуль диаграммы удваивания и ${\displaystyle L(m)}$ дает число вершин в цикле, образованном единицей. Термин диаграмма удваивания относится к ориентированному графу с 0 и натуральными числами, меньшими ${\displaystyle m}$ в качестве вершин и дугами, идущими из вершины ${\displaystyle x}$ в вершину ${\displaystyle 2x}$ по модулю ${\displaystyle m}$.[45]^:74 Было установлено, что для всех нечетных простых чисел либо ${\displaystyle L(p^{n+1})=p\times L(p^{n})}$, либо ${\displaystyle L(p^{n+1})=L(p^{n})}$.[45]^:75

Было установлено, что ${\displaystyle \chi _{D_{0}}{\big (}p{\big )}=1}$ и ${\displaystyle \lambda \,\!_{p}{\big (}\mathbb {Q} {\big (}{\sqrt {D_{0}}}{\big )}{\big )}=1}$ тогда и только тогда, когда ${\displaystyle 2^{p-1}\not \equiv 1{\pmod {p^{2}}}}$, где ${\displaystyle p}$ – нечетное простое и ${\displaystyle D_{0}<0}$ — фундаментальный дискриминант комплексного квадратичного поля ${\displaystyle \mathbb {Q} {\big (}{\sqrt {1-p^{2}}}{\big )}}$.

Также было показано следующее:

Пусть ${\displaystyle p}$ – простое число Вифериха. Если ${\displaystyle p\equiv 3{\pmod {4}}}$, пусть ${\displaystyle D_{0}<0}$ — фундаментальный дискриминант комплексного квадратичного поля ${\displaystyle \mathbb {Q} {\big (}{\sqrt {1-p}}{\big )}}$

Если ${\displaystyle p\equiv 1{\pmod {4}}}$, пусть ${\displaystyle D_{0}<0}$ — фундаментальный дискриминант комплексного квадратичного поля ${\displaystyle \mathbb {Q} {\big (}{\sqrt {4-p}}{\big )}}$.

Тогда ${\displaystyle \chi _{D_{0}}{\big (}p{\big )}=1}$ и ${\displaystyle \lambda \,\!_{p}{\big (}\mathbb {Q} {\big (}{\sqrt {D_{0}}}{\big )}{\big )}=1}$ (${\displaystyle \chi }$ и ${\displaystyle \lambda }$ в этом контексте означают инвариант Ивасава (Iwasawa)).[46]^:27

Также было установлено:

Пусть ${\displaystyle q}$ – нечетное простое число, ${\displaystyle k}$ и ${\displaystyle p}$ – простые, такие, что ${\displaystyle p=2k+1,k\equiv 3{\pmod {4}},p\equiv -1{\pmod {q}},p\not \equiv -1{\pmod {q^{3}}}}$ и порядок ${\displaystyle q}$ по модулю ${\displaystyle k}$ равен ${\displaystyle {\tfrac {k-1}{2}}}$.

Предположим, что ${\displaystyle q}$ делит ${\displaystyle h^{+}}$ — число классов вещественного кругового поля ${\displaystyle \mathbb {Q} {\big (}\zeta \,\!_{p}+\zeta \,\!_{p}^{-1}{\big )}}$, полученного добавлением к полю рациональных чисел суммы ${\displaystyle p}$-го корня из единицы и обратного к нему элемента.

Тогда ${\displaystyle q}$ – простое число Вифериха.[47]^:55

Это остается верным, если условия ${\displaystyle p\equiv -1{\pmod {q}},p\not \equiv -1{\pmod {q^{3}}}}$ заменить на ${\displaystyle p\equiv -3{\pmod {q}},p\not \equiv -3{\pmod {q^{3}}}}$

Утверждение остается верным и при замене условия ${\displaystyle p\equiv -1{\pmod {q}}}$ на ${\displaystyle p\equiv -5{\pmod {q}},}$ (в этом случае ${\displaystyle q}$ будет простым числом Фибоначи-Вифериха), а неравенство заменится на ${\displaystyle p\not \equiv -5{\pmod {q^{3}}}}$.[48]^:376

Пусть период ${\displaystyle p}$ числа ${\displaystyle x}$ по базису ${\displaystyle b}$ – период дроби ${\displaystyle {\tfrac {1}{x}}}$ по базису ${\displaystyle b}$. Например, период числа 3 по базису 10 равен 1, что обычно записывается как 0,(3), в то время как период числа 3 по базису 2 равен 2 и число можно записать как 0,(01). В общем случае, период ${\displaystyle p}$ числа ${\displaystyle x}$ является показателем ${\displaystyle b}$ по модулю ${\displaystyle x}$.[49]^:314 Простое число Вифериха по базису ${\displaystyle b}$ – это простое ${\displaystyle x}$, удовлетворяющее сравнению ${\displaystyle b^{x-1}\equiv 1{\pmod {x^{2}}}}$. Если ${\displaystyle x^{2}}$ делит ${\displaystyle b^{p-1}-1}$, период ${\displaystyle x^{2}}$ имеет тот же период, что и ${\displaystyle x}$, и такие простые известны как простые с квадратным периодом.[49]^:316 Гарца (Garza) и Янг (Young) утверждают, что период числа 1093 равен 1092 и он равен периоду числа 1093²,[49]^:314.

Только простые 1093 и 3511 среди чисел до ${\displaystyle 4\cdot 10^{12}}$ удовлетворяют ${\displaystyle \operatorname {ord} _{p^{2}}(2)=\operatorname {ord} _{p}(2)}$ и известно, что ${\displaystyle \operatorname {ord} _{1093}(2)=364}$ и ${\displaystyle \operatorname {ord} _{3511}(2)=1755}$.[50][51]

Х. С. Вандивер (H. S. Vandiver) показал, что ${\displaystyle 2^{p-1}\equiv 1{\pmod {p^{3}}}}$ тогда и только тогда, когда ${\displaystyle 1+{\tfrac {1}{3}}+\dots +{\tfrac {1}{p-2}}\equiv 0{\pmod {p^{2}}}}$.[52]^:187

Простое ${\displaystyle p}$, удовлетворяющее сравнению ${\displaystyle 2^{\frac {p-1}{2}}\equiv \pm 1+Ap{\pmod {p^{2}}}}$ с малым ${\displaystyle |A|}$, обычно называются почти простым числа Вифериха (последовательность A195988 в OEIS).[20][53] Почти простые числа Вифериха с ${\displaystyle A=0}$ представляют собой простые числа Вифериха.

Проекты распределенных вычислений с недавнего времени в дополнение к основному поиску простых чисел Вифериха пытались обнаружить и почти простые числа Вифериха.[17][54]

Следующая таблица представляет все почти простые числа Вифериха с ${\displaystyle |A|\leqslant 10}$ в интервале ${\displaystyle [10^{9},3\cdot 10^{15}]}$.[55] Этот интервал был достигнут поиском, организованным Карлайлом (P. Carlisle), Крэндаллом (R. Crandall) и Роденкирхом (M. Rodenkirch).[16][56]

Доре (Dorais) и Клайв (Klyve)[17] использовали другое определение почти простых чисел Вифериха, а именно, как простое p с малым значением ${\displaystyle \left|{\tfrac {\omega (p)}{p}}\right|}$, где ${\displaystyle \omega (p)={\tfrac {2^{p-1}-1}{p}}\,{\bmod {\,}}p}$ — частное Ферма для числа 2 по модулю p'.

Следующая таблица показывает все простые ${\displaystyle p\leqslant 6{,}7\times 10^{15}}$ с ${\displaystyle \left|{\tfrac {\omega (p)}{p}}\right|\leq 10^{-14}}$.

p	${\displaystyle \omega (p)}$	${\displaystyle \left|{\tfrac {\omega (p)}{p}}\right|\times 10^{14}}$
1093	0	0
3511	0	0
2276306935816523	+6	0.264
3167939147662997	−17	0.537
3723113065138349	−36	0.967
5131427559624857	−36	0.702
5294488110626977	−31	0.586
6517506365514181	+58	0.890

Простым числом Вифериха по базе a называется простое p, удовлетворяющее сравнению

${\displaystyle a^{p-1}\equiv 1{\pmod {p^{2}}}}$.[4]

Такие простые не могут делить a, поскольку тогда они должны делить и 1.

Парой Вифериха называется пара простых ${\displaystyle p,q}$, удовлетворяющих

${\displaystyle p^{q-1}\equiv 1{\pmod {q^{2}}},\ q^{p-1}\equiv 1{\pmod {p^{2}}}}$

Таким образом, простое число Вифериха ${\displaystyle p\equiv 1{\pmod {4}}}$ образует пару ${\displaystyle (p,2)}$. Единственное известное число для этого случая – это ${\displaystyle p=1093}$. Известно 6 пар Вифериха.[57]

Числом Вифериха называется нечетное целое ${\displaystyle w\geqslant 3}$, удовлетворяющее сравнению ${\displaystyle 2^{\varphi (w)}\equiv 1{\pmod {w^{2}}}}$, где ${\displaystyle \varphi }$ означает функцию Эйлера. Если число Вифериха ${\displaystyle w}$ является простым, то оно также является простым числом Вифериха.

Несколько первых чисел Вифериха:

1093, 3279, 3511, 7651, 10 533, 14 209, 17 555, 22 953, 31 599, 42 627, 45 643, … последовательность A077816 в OEIS

Можно показать, что если имеется только конечное число простых чисел Вифериха, то и количество чисел Вифериха конечно. В частности, если простые числа Вифериха только 1093 и 3511, то существует точно 104 чисел Вифериха, и они соответствуют тем числам, которые известны на данный момент.[58]

Обобщая, целое ${\displaystyle w}$ является числом Вифериха по базе ${\displaystyle a}$, если ${\displaystyle a^{\varphi (w)}\equiv 1{\pmod {w^{2}}}}$.[59]^:31

По другому определению числом Вифериха называется положительное нечетное q, такое, что q и ${\displaystyle {\tfrac {2^{m}-1}{q}}}$ не взаимно просты, где m – показатель 2 по модулю q. Первые несколько этих чисел:[60]

21, 39, 55, 57, 105, 111, 147, 155, 165, 171, 183, … последовательность A182297 в OEIS

Как и выше, если число Вифериха q является простым, то оно является простым числом Вифериха.

Простым числом Люка-Вифериха, соответствующим паре целых ${\displaystyle (P,Q)}$ называется простое ${\displaystyle p}$, такое, что ${\displaystyle U_{p-\varepsilon }(P,Q)\equiv 0{\pmod {p^{2}}}}$, где ${\displaystyle U_{n}(P,Q)}$ означает последовательность Люка первого вида и ${\displaystyle \varepsilon }$ – это значение символа Лежандра ${\displaystyle P^{2}-4Q}$ по модулю ${\displaystyle p}$. Все простые числа Вифериха являются простыми числами Люка-Вифериха, соответствующими паре ${\displaystyle (3,2)}$.[61] ^:2088

Пусть ${\displaystyle K}$ – глобальное поле, т.е. числовое поле или поле функций одной переменной над конечным полем и пусть ${\displaystyle E}$ – эллиптическая кривая. Если ${\displaystyle v}$ – это неархимедова точка нормы ${\displaystyle q_{v}}$ ${\displaystyle K}$ и ${\displaystyle a\in K}$, где ${\displaystyle v(a)=0}$, то ${\displaystyle v(a^{q_{v}-1})\geqslant 1}$. ${\displaystyle v}$ называется точкой Вифериха по базе ${\displaystyle a}$, если ${\displaystyle v(a^{q_{v}-1})>1}$, эллиптической точкой Вифериха по базе ${\displaystyle P\in E}$, если ${\displaystyle N_{v}(P)\in E_{2}}$, и сильной эллиптической точкой Вифериха по базе ${\displaystyle P\in E}$, если ${\displaystyle n_{v}(P)\in E_{2}}$, где ${\displaystyle n_{v}}$ – порядок ${\displaystyle P}$ по модулю ${\displaystyle v}$ и ${\displaystyle N_{v}}$ дает количество рациональных точек (над полем вычетов ${\displaystyle v}$) редукции ${\displaystyle E}$ на ${\displaystyle v}$.[62]^:206