Степени и сравнение по модулю

[B@R5uk]

Решил изучить как ведут себя остатки от деления квадратов и кубов в зависимости от модуля сравнения. Например, при сравнении по модулю 13 можно получить такую табличку:

    x   x^2   x^3
    0     0     0
    1     1     1
    2     4     8
    3     9     1
    4     3    12
    5    12     8
    6    10     8
    7    10     5
    8    12     5
    9     3     1
   10     9    12
   11     4     5
   12     1    12

Сразу видно, что у функции квадрат всегда есть повторяющиеся остатки, и, как следствие, отсутствующие остатки. Это, в принципе, очевидно: можно для каждого остатка рассмотреть дополнительный отрицательный остаток, после возведения в квадрат остатки с одинаковым модулем дадут один результат (кроме нуля и половины модуля, в случае, если он чётный).

С кубической функцией же результат немного интереснее. Иногда бывает так, что остатки куба пробегают все возможные значения остатков, и каждый остаток встречается только один раз без повторов и без пропусков. Например, табличка для остатков по модулю 10:

    x   x^2   x^3
    0     0     0
    1     1     1
    2     4     8
    3     9     7
    4     6     4
    5     5     5
    6     6     6
    7     9     3
    8     4     2
    9     1     9

Сразу же хочется узнать, а что же это за числа, по модулю которых кубы дают все возможные остатки. Перебор в лоб дал такую вот последовательность до сотни:

2, 3, 5, 6, 10, 11, 15, 17, 22, 23, 29, 30, 33, 34, 41, 46, 47, 51, 53, 55, 58, 59, 66, 69, 71, 82, 83, 85, 87, 89, 94.

То, что в этой последовательности отсутствуют квадраты и вообще числа, в разложении которых на простые есть повторяющиеся множители, думаю, очевидно. Если модуль $M$ можно представить в виде $M=a^2b$, где $a>1$, то число $N=ab<M$ при возведении в квадрат даст $N^2=a^2b^2$, которое делится на $M$ и, поэтому, даёт по модулю $M$ ноль. Ноль при умножении на $N$ снова даёт ноль, поэтому по крайней мере нулевой остаток у кубической функции повторяется.

С остальными отсутствующими в последовательности числами (среди которых есть и простые) не всё так просто. Так же анализируя разложение на простые множители, я обнаружил, что если модуль делится на простое число, которое даёт при делении на 3 остаток 1, то такой модуль в последовательность не входит. В результате, получается правило: последовательность состоит из чисел, в разложении которых на простые отсутствуют повторяющиеся множители И простые множители, сравнимые с 1 по модулю 3 (да, масло масленое: разложение модуля надо проверять по модулю). Проверка в лоб до $10^5$, показало, что это правило выполняется.

Собственно вот мой вопрос: почему это так?

[Munin]

Я занимался собственными "открытиями" на эту тему, а потом открыл для себя замечательную книжку
Дынкин, Успенский. Математические беседы.
(это тот самый Дынкин, ну и тот самый Успенский).

Очень советую! Кстати, половина текста книги находится в "Решениях" - сразу предупреждаю о таком стиле.

В частности, ответ на ваш вопрос там располагается в § 1.1.4, и в "решениях" к нему.

[B@R5uk]

Munin, спасибо. Книжка есть вместе с полной коллекцией книжек математического кружка.

(Оффтоп)

Скачал сто лет назад, но так и не добрался почитать.

[Munin]

Вот она ровно про это (по крайней мере, её середина). О чём по названию нифига не догадаешься.

[B@R5uk]

Munin в сообщении #1435232 писал(а):

половина текста книги находится в "Решениях" - сразу предупреждаю о таком стиле.

Плохо, что ответы находятся в конце книги, а не сразу после задачи. Так же было бы более-менее сносным компромиссом, если решения были бы в конце параграфа.

[Andrey A]

B@R5uk в сообщении #1435227 писал(а):

2, 3, 5, 6, 10, 11, 15, 17, 22, 23, 29, 30, 33, 34, 41, 46, 47, 51, 53, 55, 58, 59, 66, 69, 71, 82, 83, 85, 87, 89, 94.

Тут выписаны модули, по которым $a^3 \equiv b^3$ возможно только если $a \equiv b$.
По $\mod 19$, к примеру, $3^3 \equiv 2^3.$ Значит эти кубы дадут одинаковые остатки при делении на $19$, а опытов всего $19$, и где-то образуются пробелы, то есть невычеты. Поэтому числа $19$ в списке нет.

[B@R5uk]

Andrey A, лучше говорить как в этой энциклопедии последовательностей: последовательность образуют такие числа $M$, что уравнение $x^3\equiv a \mod M$ разрешимо относительно $x$ для любых значений $a$. То есть для любого натурального существует кубический корень по модулю.

[Andrey A]

Ну, это как удобно. Важно, что в левых скобках разложения $a^3-b^3=(a-b)(a^2+ab+b^2)$ может оказаться любое число, а в правых — кратного пяти, к примеру, быть не может. И любому простому вида $6k-1$.

[B@R5uk]

Munin, вроде чуть-чуть вникнул в доказательство теоремы в книжке.

Там используется (доказанный ранее) факт, что $a^{p-1}\equiv 1\mod p$ (1), где $a\ne 0$ и p — простое. Далее, используя свойство деления в p-арифметике (видимо, тоже доказанное ранее), что деление 1 на x единственным образом сопоставляет x новое целое число y такое, что $xy\equiv 1\mod p$, показывают, что решение уравнения $b^3\equiv 1\mod p$ единственно и даёт $b=1$, если $p=3k+2$. Для этого в (1) подставляется последнее равенство, получая: $b=b^{3k+2-1} / (b^3)^k\equiv 1\mod p$. Мне понятно, откуда в сравнении для числа p берётся 3, — это результат того, что функция кубическая. Так же понятно, почему остаток от p должен быть 2, — это потому что $2=1+1$, где одна единица, потому что b должно быть в степени 1, когда записывают решение $b=1$, а другая — из степени в малой теореме Ферма.

Однако, это всё описывает только частный случай. А именно: кубический корень по модулю M извлекается всегда, если $M=p=3k+2$, где p — простое. Это доказательство совершенно ничего не говорит, почему корень извлекается не всегда, если M делится на $p=3k+1$, но в то же время извлекается всегда, если M — составное из последовательности выше. Понятно, что общий случай как-то связан с частным, но как?

-- 15.01.2020, 03:42 --

Andrey A в сообщении #1435262 писал(а):

Важно, что в левых скобках разложения $a^3-b^3=(a-b)(a^2+ab+b^2)$ может оказаться любое число, а в правых — кратного пяти, к примеру, быть не может.

Выделенное совершенно не понял. Можете пояснить развёрнутей, пожалуйста?

[Andrey A]

Поясню. $a^2+ab+b^2=\dfrac{(a-b)^2+3(a-b)^2}{4}.$ При взаимно простых $a,b$ такое число нечетно и может содержать в каноническом разложении тройку и простые вида $6k+1$. По аналогии с числами вида $p^2+q^2$ (там двойка и простые вида $4k+1$). Я намеренно избегаю терминологии, смотрите любой учебник по теории чисел.

[Sonic86]

B@R5uk, ну детский сад, честное слово.
Если $p$ - простое число, то мультипликативная группа поля $\mathbb{Z}_p^{\times}$ - циклическая (она порождается одним элементом) порядка $p-1$.
Если $G$ - циклическая группа порядка $n$, то в ней уравнение $x^d=e$ имеет $\gcd(d,n)$ корней (для любого $d,n$).
Отсюда все следует в 2 счета.
Почитайте литературу, список тем с литературой в этом же разделе.

[Munin]

B@R5uk в сообщении #1435267 писал(а):

Это доказательство совершенно ничего не говорит, почему корень извлекается не всегда, если M делится на $p=3k+1$,

Рассмотрите сначала, если $M=p=3k+1.$

Sonic86

Sonic86 в сообщении #1435282 писал(а):

Если $p$ - простое число, то мультипликативная группа поля $\mathbb{Z}_p^{\times}$

А где описан случай колец $\mathbb{Z}_n,$ где $n\notin\mathbb{P}$? Понятно, что там делители нуля, и вообще это плохой случай, но должен же он быть разобран. Я так подозреваю, там всё связано с набором простых множителей $n,$ и со взаимной простотой $a,n.$

[Sonic86]

Munin в сообщении #1435297 писал(а):

А где описан случай колец $\mathbb{Z}_n,$ где $n\notin\mathbb{P}$? Понятно, что там делители нуля, и вообще это плохой случай, но должен же он быть разобран. Я так подозреваю, там всё связано с набором простых множителей $n,$ и со взаимной простотой $a,n.$

Если брать множество взаимно простых с $n$ элементов из $\mathbb{Z}_n$ по умножению $\mathbb{Z}_n$, то они образуют мультипликативную группу $\mathbb{Z}_n^{\times}$, не всегда циклическую. Сравнение $x^m\equiv 1\pmod n$ при $n=p_1^{a_1}...p_s^{a_s}$ по китайской теореме об остатках равносильно системе сравнений вида $x^m\equiv 1\pmod {p_i^{a_i}}$, причем $\mathbb{Z}_{p^n}$ циклична при $p\neq 2$, а $\mathbb{Z}_{2^n}=\langle -1,5\rangle \cong \mathbb{Z}_{2} \times \mathbb{Z}_{2^{n-2}}$. Отсюда можно извлекать нужную информацию.
Я знаю в книге Айерленда Роузена Классическое введение в современную теорию чисел главу 4 "Структура группы $U(\mathbb{Z}/n\mathbb{Z})$" - там про это написано.
Если же в сравнении $x^m\equiv a\pmod n$ $x$ не взаимно просто с $n$, то там еще сложнее: $\langle x\rangle$ будет полугруппой, ее граф будет типа ориентированного кольца с "хвостом, впадающим в кольцо". Численно для решения можно перебирать первые $m$ до тех пор, пока степени $x$ не попадут в "кольцо", после чего можно сократить общий множитель и вернуться к случаю группы $\mathbb{Z}_n^{\times}$. Китайская теорема об остатках тут тоже работает: конкретные сравнения вида $x^m\equiv c\pmod {p^a}$ решаются легко и при $p|c$. Тут я литературы не знаю кроме книги Ляпина Полугруппы.

[Munin]

Sonic86 в сообщении #1435383 писал(а):

причем $\mathbb{Z}_{p^n}$ циклична при $p\neq 2$

Может, вы имели в виду, что $\mathbb{Z}_{p^n}^{\times}$ циклическая?

В общем, спасибо за литературу! Надеюсь, B@R5uk тоже её возьмёт! (Вот ассоциируется у меня его никнейм с фамилией Борсук...)

[Sonic86]

Munin в сообщении #1435385 писал(а):

Может, вы имели в виду, что $\mathbb{Z}_{p^n}^{\times}$ циклическая?

Да, торопился.
Еще вспомнил, что полугруппы $\langle x \rangle$ обычно характеризуются соотношениями типа $x^a=x^b$, где $a$ - длина "хвоста", а $b-a$ - длина "цикла".