Частное Ферма

В теории чисел частным Ферма для целого a ≥ 2 по простой базе p называется дробь^[1][2][3][4]

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

Если a взаимно просто с p, то малая теорема Ферма утверждает, что q_p(a) будет целым. Частное названо в честь Пьера Ферма.

Свойства

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

${\displaystyle q_{p}(1)\equiv 0{\pmod {p}}}$

${\displaystyle q_{p}(-a)\equiv q_{p}(a){\pmod {p}}}$

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

${\displaystyle q_{p}(ab)\equiv q_{p}(a)+q_{p}(b){\pmod {p}}}$;

${\displaystyle q_{p}(a^{r})\equiv rq_{p}(a){\pmod {p}}}$;

${\displaystyle q_{p}(a+p)\equiv q_{p}(a)-{\frac {1}{a}}{\pmod {p}}}$;

${\displaystyle q_{p}(p-1)\equiv 1{\pmod {p}}}$;

${\displaystyle q_{p}(p+1)\equiv -1{\pmod {p}}}$.

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

Из этих свойств вытекает

${\displaystyle q_{p}(1/a)\equiv -q_{p}(a){\pmod {p}}}$;

${\displaystyle q_{p}(a/b)\equiv q_{p}(a)-q_{p}(b){\pmod {p}}}$.

В 1895 году Дмитрий Мириманов (Dmitry Mirimanoff) указал на то, что последовательное применение правил Айзенштейна ведет к^[6]

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

Отсюда следует, что^[7]

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

Специальные случаи

Айзенштейн обнаружил, что частное Ферма по основанию 2 сравнимо по модулю p с суммой обратных величин к числам от 1 до ${\displaystyle {\frac {p-1}{2}}}$, то есть гармоническому числу ${\displaystyle H_{\frac {p-1}{2}}}$:

${\displaystyle -2q_{p}(2)\equiv \sum _{k=1}^{\frac {p-1}{2}}{\frac {1}{k}}\equiv H_{\frac {p-1}{2}}{\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}}.}$^[8]

${\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}}.}$^[9]

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

Сложность сравнений Айзенштейна увеличивается с ростом основания частных Ферма, несколько первых примеров:

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

${\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}}.}$^[13]

Обобщенные простые Вифериха

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

a	p	последовательность OEIS
2	1093, 3511	A001220
3	11, 1006003	A014127
5	2, 20771, 40487, 53471161, 1645333507, 6692367337, 188748146801	A123692
7	5, 491531	A123693
11	71
13	2, 863, 1747591	A128667
17	2, 3, 46021, 48947, 478225523351	A128668
19	3, 7, 13, 43, 137, 63061489	A090968
23	13, 2481757, 13703077, 15546404183, 2549536629329	A128669

Наименьшее решение q_p(a) ≡ 0 (mod p) с a = n-м простое

1093, 11, 2, 5, 71, 2, 2, 3, 13, 2, 7, 2, 2, 5, … последовательность A174422 в OEIS.

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