Коэффициент Ферма

В теории чисел , то частное ферма из целого числа а по отношению к нечетному простому р определяются следующим образом: ^{[1] [2] [3] [4]}

${\ displaystyle q_ {p} (a) = {\ frac {a ^ {p-1} -1} {p}}.}$

или же

${\ displaystyle \ delta _ {p} (a) = {\ frac {aa ^ {p}} {p}}}$.

Эта статья о первом. Относительно последнего см. Р- вывод . Частное названо в честь Пьера де Ферма .

Если база является взаимно просто с показателем р , то малая теорема Ферма утверждает , что д _р ( ) будет целым. Если базовый также генератор из мультипликативной группы целых чисел по модулю р , то д _р ( ) будет циклическое число , а р будет полным reptend простым .

Свойства [ править ]

Из определения очевидно, что

${\ displaystyle {\ begin {align} q_ {p} (1) & \ Equiv 0 && {\ pmod {p}} \\ q_ {p} (- a) & \ Equiv q_ {p} (a) && {\ pmod {p}} \ quad ({\ text {поскольку}} 2 \ mid p-1) \ end {выравнивается}}}$

В 1850 году Готтхольд Эйзенштейн доказал, что если a и b взаимно просты с p , то: ^[5]

${\displaystyle {\begin{aligned}q_{p}(ab)&\equiv q_{p}(a)+q_{p}(b)&&{\pmod {p}}\\q_{p}(a^{r})&\equiv rq_{p}(a)&&{\pmod {p}}\\q_{p}(p\mp a)&\equiv q_{p}(a)\pm {\tfrac {1}{a}}&&{\pmod {p}}\\q_{p}(p\mp 1)&\equiv \pm 1&&{\pmod {p}}\end{aligned}}}$

Эйзенштейн сравнил первые два из этих сравнений со свойствами логарифмов . Эти свойства подразумевают

${\displaystyle {\begin{aligned}q_{p}\left({\tfrac {1}{a}}\right)&\equiv -q_{p}(a)&&{\pmod {p}}\\q_{p}\left({\tfrac {a}{b}}\right)&\equiv q_{p}(a)-q_{p}(b)&&{\pmod {p}}\end{aligned}}}$

В 1895 году Дмитрий Мириманов указал, что повторение правил Эйзенштейна дает следствие: ^[6]

${\displaystyle q_{p}(a+np)\equiv q_{p}(a)-n\cdot {\tfrac {1}{a}}{\pmod {p}}.}$

Из этого следует, что: ^[7]

${\displaystyle q_{p}\left(a+np^{2}\right)\equiv q_{p}(a){\pmod {p}}.}$

Формула Лерха [ править ]

М. Лерх доказал в 1905 г., что ^{[8] [9] [10]}

${\displaystyle \sum _{j=1}^{p-1}q_{p}(j)\equiv W_{p}{\pmod {p}}.}$

Здесь есть фактор Wilson .${\displaystyle W_{p}}$

Особые значения [ править ]

Эйзенштейн обнаружил, что частное Ферма с основанием 2 может быть выражено через сумму обратных по модулю p чисел, лежащих в первой половине диапазона {1, ..., p  - 1}:

${\displaystyle -2q_{p}(2)\equiv \sum _{k=1}^{\frac {p-1}{2}}{\frac {1}{k}}{\pmod {p}}.}$

Более поздние авторы показали, что количество терминов, необходимых для такого представления, можно уменьшить с 1/2 до 1/4, 1/5 или даже 1/6:

${\displaystyle -3q_{p}(2)\equiv \sum _{k=1}^{\lfloor {\frac {p}{4}}\rfloor }{\frac {1}{k}}{\pmod {p}}.}$^[11]

${\displaystyle 4q_{p}(2)\equiv \sum _{k=\lfloor {\frac {p}{10}}\rfloor +1}^{\lfloor {\frac {2p}{10}}\rfloor }{\frac {1}{k}}+\sum _{k=\lfloor {\frac {3p}{10}}\rfloor +1}^{\lfloor {\frac {4p}{10}}\rfloor }{\frac {1}{k}}{\pmod {p}}.}$^[12]

${\displaystyle 2q_{p}(2)\equiv \sum _{k=\lfloor {\frac {p}{6}}\rfloor +1}^{\lfloor {\frac {p}{3}}\rfloor }{\frac {1}{k}}{\pmod {p}}.}$^{[13] [14]}

Ряд Эйзенштейна также имеет все более сложную связь с факторами Ферма с другими основаниями, первые несколько примеров:

${\displaystyle -3q_{p}(3)\equiv 2\sum _{k=1}^{\lfloor {\frac {p}{3}}\rfloor }{\frac {1}{k}}{\pmod {p}}.}$^[15]

${\displaystyle -5q_{p}(5)\equiv 4\sum _{k=1}^{\lfloor {\frac {p}{5}}\rfloor }{\frac {1}{k}}+2\sum _{k=\lfloor {\frac {p}{5}}\rfloor +1}^{\lfloor {\frac {2p}{5}}\rfloor }{\frac {1}{k}}{\pmod {p}}.}$^[16]

Обобщенные простые числа Вифериха [ править ]

Если q _p ( a ) ≡ 0 (mod p ), то a ^{p -1} ≡ 1 (mod p ² ). Простые числа, для которых это верно при a = 2, называются простыми числами Вифериха . Обычно они называются простыми числами Вифериха с основанием a. Известные решения q _p ( a ) ≡ 0 (mod p ) для малых значений a : ^[2]

а	p (проверено до 5 × 10 13 )	Последовательность OEIS
1	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... (все простые числа)	A000040
2	1093, 3511	A001220
3	11, 1006003	A014127
4	1093, 3511
5	2, 20771, 40487, 53471161, 1645333507, 6692367337, 188748146801	A123692
6	66161, 534851, 3152573	A212583
7	5, 491531	A123693
8	3, 1093, 3511
9	2, 11, 1006003
10	3, 487, 56598313	A045616
11	71
12	2693, 123653	A111027
13	2, 863, 1747591	A128667
14	29, 353, 7596952219	A234810
15	29131, 119327070011	A242741
16	1093, 3511
17	2, 3, 46021, 48947, 478225523351	A128668
18	5, 7, 37, 331, 33923, 1284043	A244260
19	3, 7, 13, 43, 137, 63061489	A090968
20	281, 46457, 9377747, 122959073	A242982
21 год	2
22	13, 673, 1595813, 492366587, 9809862296159	A298951
23	13, 2481757, 13703077, 15546404183, 2549536629329	A128669
24	5, 25633
25	2, 20771, 40487, 53471161, 1645333507, 6692367337, 188748146801
26 год	3, 5, 71, 486999673, 6695256707
27	11, 1006003
28 год	3, 19, 23
29	2
30	7, 160541, 94727075783

Для получения дополнительной информации см. ^{[17] [18] [19]} и. ^[20]

Наименьшие решения q _p ( a ) ≡ 0 (mod p ) с a = n :

2, 1093, 11, 1093, 2, 66161, 5, 3, 2, 3, 71, 2693, 2, 29, 29131, 1093, 2, 5, 3, 281, 2, 13, 13, 5, 2, 3, 11, 3, 2, 7, 7, 5, 2, 46145917691, 3, 66161, 2, 17, 8039, 11, 2, 23, 5, 3, 2, 3, ... (последовательность A039951 в OEIS )

Пара ( p ,  r ) простых чисел такая, что q _p ( r ) ≡ 0 (mod p ) и q _r ( p ) ≡ 0 (mod r ), называется парой Вифериха .

Ссылки [ править ]

Внешние ссылки [ править ]

• Готфрид Хелмс. Факторы Ферма / Эйлера ( a p -1 - 1) / p k с произвольным k .
• Ричард Фишер. Факторы Ферма B ^ (P-1) == 1 (mod P ^ 2) .