Русская Википедия:Частное Ферма

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

<math>q_p(a) = \frac{a^{p-1}-1}{p}.</math>

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

Свойства

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

<math>q_p(1) \equiv 0 \pmod{p}</math>

<math>q_p(-a) \equiv q_p(a) \pmod{p}</math>

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

<math>q_p(ab)\equiv q_p(a)+q_p(b) \pmod{p}</math>;

<math>q_p(a^r)\equiv rq_p(a) \pmod{p}</math>;

<math>q_p(a+p)\equiv q_p(a)-\frac{1}{a} \pmod{p}</math>;

<math>q_p(p-1)\equiv 1 \pmod{p} </math>;

<math>q_p(p+1)\equiv -1 \pmod{p}</math>.

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

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

<math>q_p(1/a) \equiv -q_p(a) \pmod{p}</math>;

<math>q_p(a/b) \equiv q_p(a) - q_p(b) \pmod{p}</math>.

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

<math>q_p(a+np)\equiv q_p(a)-n\cdot\frac{1}{a} \pmod{p}.</math>

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

<math>q_p(a+np^2)\equiv q_p(a) \pmod{p}.</math>

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

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

<math>-2q_p(2) \equiv \sum_{k=1}^{\frac{p-1}{2}} \frac{1}{k} \equiv H_{\frac{p-1}2} \pmod{p}.</math>

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

<math>-3q_p(2) \equiv \sum_{k=1}^{\lfloor\frac{p}{4}\rfloor} \frac{1}{k} \pmod{p}.</math>

<math>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}.</math>

<math>2q_p(2) \equiv \sum_{k=\lfloor\frac{p}{6}\rfloor+1}^{\lfloor\frac{p}{3}\rfloor} \frac{1}{k} \pmod{p}.</math>

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

<math>-3q_p(3) \equiv 2\sum_{k=1}^{\lfloor\frac{p}{3}\rfloor} \frac{1}{k} \pmod{p}.</math>

<math>-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}.</math>

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

Если 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).