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

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

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

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

Свойства

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

$q_p(1)\equiv 0(\mathrm{mod}p)$

$q_p(-a)\equiv q_p(a)(\mathrm{mod}p)$

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

$q_p(ab)\equiv q_p(a)+q_p(b)(\mathrm{mod}p)$;

$q_p(a^r)\equiv r{q}_p(a)(\mathrm{mod}p)$;

$q_p(a+p)\equiv q_p(a)-\frac{1}{a}(\mathrm{mod}p)$;

$q_p(p-1)\equiv 1(\mathrm{mod}p)$;

$q_p(p+1)\equiv -1(\mathrm{mod}p)$.

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

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

$q_p(1/a)\equiv -q_p(a)(\mathrm{mod}p)$;

$q_p(a/b)\equiv q_p(a)-q_p(b)(\mathrm{mod}p)$.

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

$q_p(a+np)\equiv q_p(a)-n\cdot \frac{1}{a}(\mathrm{mod}p).$

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

$q_p(a+n{p}^2)\equiv q_p(a)(\mathrm{mod}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}}(\mathrm{mod}p).$

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

$-3q_p(2)\equiv \sum _{k=1}^{\lfloor \frac{p}{4}\rfloor }\frac{1}{k}(\mathrm{mod}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}(\mathrm{mod}p).$

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

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

$-3q_p(3)\equiv 2\sum _{k=1}^{\lfloor \frac{p}{3}\rfloor }\frac{1}{k}(\mathrm{mod}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}(\mathrm{mod}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	Шаблон:OEIS2C
3	11, 1006003	Шаблон:OEIS2C
5	2, 20771, 40487, 53471161, 1645333507, 6692367337, 188748146801	Шаблон:OEIS2C
7	5, 491531	Шаблон:OEIS2C
11	71
13	2, 863, 1747591	Шаблон:OEIS2C
17	2, 3, 46021, 48947, 478225523351	Шаблон:OEIS2C
19	3, 7, 13, 43, 137, 63061489	Шаблон:OEIS2C
23	13, 2481757, 13703077, 15546404183, 2549536629329	Шаблон:OEIS2C

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

1093, 11, 2, 5, 71, 2, 2, 3, 13, 2, 7, 2, 2, 5, … Шаблон: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).