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

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

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

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

Свойства

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Отсюда следует, что

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

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

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

$-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:

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

$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}}.$

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

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

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

$-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}}.$

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

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

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) называется парой Вифериха.

Ссылки

• Gottfried Helms. Fermat-/Euler-quotients (a^p-1 – 1)/p^k with arbitrary k.
• Richard Fischer. Fermat quotients B^(P-1) == 1 (mod P^2).