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

6

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

В статье «Сравнения и классы вычетов»*) было рассмотрено множество $F_m$ классов вычетов по модулю $m$ и были определены три операции — сложения, вычитания и умножения классов. Там было доказано, что в случае, когда модель сравнения — простое число, можно определить и деление на любой ненулевой класс. Благодаря этому сравнению по простому модулю обладают рядом интересных и тонких свойства, которые сравнения по произвольному модулю не обладают. Мы познакомимся здесь с некоторыми таким свойствами. В дальнейшем мы будем все время считать, что модель — простое число; чтобы не забывать об этом, мы будем обозначать его через $p$.

Существование первогообразного корня

Назовем порядком класса вычетов $\bar{a} \in F_p$ наименьшее натуральное число $k$, для которого $\bar{a}^k = 1$. В конце статьи «Сравнения и классы вычетов» было сказано, что в множество $F_p$ существует класс, порядок которого равен $p-1$. Класс с таким свойством называется первообразным корнем. Теорема о существовании такого класса была впервые доказана Лежандром (1752—1833). Приведем доказательство теоремы Лежандра, близкое к доказательству самого Лежандра.

*) См. «Квант» № 10.

Докажем сначала, что если порядки $l$ и $m$ двух классов $\bar{a}$ и $\bar{b}$ взаимно просты, то порядок произведения $\bar{a}\bar{b}$ равен $lm$. Действительно, $(\bar{a}\bar{b})^{lm} = \bar{a}^{lm} \cdot \bar{b}^{lm} = (\bar{a}^l)^{m} \cdot (\bar{b}^m)^{l} = 1$ (так как $\bar{a}^l = 1$ и $\bar{b}^m = 1$). Порядок класса $\bar{a}\bar{b}$ должен быть поэтому делитель числа $lm$. Обозначим его через $l'm'$, где $l'$ — делитель $l$, а $m'$ — делитель $m$ (l и m взаимно просты!)*. Итак,

$$\bar{a}^{l'm'} \cdot \bar{b}^{l'm'} = (\bar{a}\bar{b})^{l'm'} = 1.$$

Возведем обе части этого равенства в такую степень $l''$, что $l'l'' = l$. Популярным тогда $(\bar{a}^l)^{m'} \cdot \bar{b}^{lm'} = 1$, а так как $l$ — порядок $\bar{a}$, то $(\bar{a}^l)^{m'} = 1$ и потому $\bar{b}^{lm'} = 1$. Значит, $lm'$ делится на $m$ (порядок $\bar{b}$), но $l$ взаимно просто с $m$, а $m'$ — делитель $m$, поэтому $m' = m$, аналогично $l' = l$; наше утверждение доказано.

Перейдем теперь непосредственно к теореме.

Рассмотрим класс $\bar{a}$ с наиболее возможным порядком $N$. Мы хотим доказать, что это и есть первообразный корень. Для этого достаточно убедиться, что любой другой класс $\bar{b}$ является степенью $\bar{a}$. Предположим, что порядок $\bar{b}$ равен $n$. Возможны два случая на $n$. Расмотрим $n$ классов $\bar{a}^k \cdot N/n$ при $0 \leq k < n$. Все они являются различными корнями степени $n$ из единиц, т. е. решениями уравнения $\bar{x}^n - 1 = 0$ (проверьте). Класс $\bar{b}$ также является корнем степени $n$ из единиц по определению порядка. В приложении к этой статье мы доказем, что у любого многочлена степени $n$ с коэффициентами из $F_p$ и, в частности, у многочлена $\bar{x}^n - 1$ не может быть больше, чем $n$ корней. Поэтому $\bar{b}$ есть один из элементов $\bar{a}^k N/n$, то есть является степенью $\bar{a}$.

2. $N$ не делится на $n$. Пусть $r$ — наиболее возможный общий делитель $N$ и $n$.

*) Возможность такого представления произвольного числа $lm$ следует из Основной теоремы арифметики, доказанной в приложении к этой статье.

7

Порядок класса $\bar{b}^r$ равен $n/r$ (проверьте). Числа $N$ и $n/r$ взаимно просты. Поэтому порядок класса $\bar{ab}^r$ равен $N \cdot n/r > N$. Это противоречит максимальнымости $N$. Второй случай невозможен.

Теорема о существовании первого корня доказана.

Гипотеза Артина

Приведенное доказательство не конструктивно: мы не можем указыть явно, какой именно из вычетов $\bar{1}$, …, $\bar{p-1}$ является первообразным корнем по модulo $p$.

Американский математик Э. Артин (1898—1962) высказал такую гипотезу: если целое число $n$ не является полным квадратом, то существует бесконечного много простых чисел $p$, для которых класс вычетов по mod $p$, содержащий $n$, является первообразным корнем по mod $p$. Эта гипотеза до сих пор не доказана. Если мы могли явно указыть первообразные корни по mod $p$ для всех $p$, было бы легко выяснить, верна ли эта гипотеза. (Проверьте, что если $n=m^2$ для какого-нибудь $m$, то простых чисел $>2$, о которых говорится в гипотезе, вовсе не существует, вовсе не существует.)

Извлечение корней

Теорема Лежандра позволяет выяснить, когда в множестве $F_p$ можно извлечь корни.

Корнем степени $n$ из класса вычетов $\bar{b}$ естественно называть такой класс $\bar{x}$, что $\bar{x}^n = \bar{b}$.

Пусть $\bar{a}$ — какой-нибудь первообразный корень в $F_p$. Существует такое натуральное число $k$, что $\bar{b} = \bar{a}^k$. Если в соответствии $\bar{x}^n = \bar{b}$ заменить $\bar{x}$ на $\bar{a}^y$, то его можно перепись в виде $\bar{a}^{yn} = \bar{a}^k$ или $\bar{a}^{yn-k} = \bar{1}$.

Из последнего соответствия видно, что $yn-k$ делится на $p-1$.

Эта делимость равносильна следующему равенству в множестве $F_{p-1} : \bar{yn} = k$.

Обратно, если $\bar{m}$ в множестве $F_{p-1}$ является решением уравнения $\bar{yn} = \bar{k}$, то $\bar{a}^m$ является корнем степени $n$ из $\bar{b}$ (в $F_p$).

Таким образом, задачу об извлечении корней в множестве $F_p$ мы свели к задаче о делении в множестве $F_{p-1}$.

В статье «Сравнения и классы вычетов» было указано, что если $d$ — наиболееший общий делитель чисел $n$ и $p-1$ и $k$ делится на $d$, то уравнения $\bar{yn} = \bar{k}$ имеетсяровно $d$ решений; если же — не делится, то уравнения $\bar{yn} = \bar{k}$ вовсе нет решений.

Тепер вопрос о корнях степени $n$ из класса вычетов $\bar{b}$ выясен полностью:

Теорема. Если индекс*) $k$ класса $\bar{b} \in F_p$ делится на наиболееший общий делитель $d$ чисел $n$ и $p-1$, то существует динамический стелени $n$ из класса $\bar{b}$, в проминном случае из класса $\bar{b}$ нельзя извлечь корня стелени $n$.

Пример: $p = 11$.

Выпишем все стелени класса $\bar{2}$ в множестве $F_{11}$. В таблице 1 в первой строкке выписан показатель стелени, в котором нужно возвести $a$, чтобы получить $\bar{b}$. В формулировке теоремы не существует, какой первообразный корень выбран.

*) Напомним (см. «Квант» № 10, с. 8), что индексом класса $\bar{b}$ по основанию $\bar{a}$ (далее первообразный корень) называется показатель стелени, в котором нужно возвести $a$, чтобы получить $\bar{b}$. В формулировке теоремы не существует, какой первообразный корень выбран.

**) Проще всего вычислять стелени двойки (или другого элемента) последовательно: $\bar{2}^k = \bar{2}.\bar{2}^{k-1}$; сначала же возводить 2 в стелени $k$, а потом приводить по mod 11 — дело более трудоемкое.

8

мет, например, класс 3. Его индекс равен 8. Нам нужно решить уравнение $3y=8$ в множестве $F_{10}$. Будем умножать все классы в $F_{10}$ на 3 (табл. 2). Из таблицы видно, что от

$$\begin{array}{c|cccccccc} k \in F_{10} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 0 \\ \hline 3k \in F_{10} & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 \end{array}$$

вет — 6, значит, в множестве $F_{11}$ $2^6=9$ — кубический корень из 3. Действительно, $9^3=3$.

Пусть теперь $n=5$, тогда $d=5$ и из всех классов, кроме классов 1 и 10 (с индексами 10 и 5), корень степени 5 не извлекается. Найдем сначала корни степени 5 из 1. Легко сообщить, что это все классы с четыыми индексами. (Действительно, класс с четыым индексом 2r равен $2^2r$; $(2^2r)^5=(2^r)^{10}=1$ в силу малой теоремы Ферма для $p=11$.) Таких классовровно положина, пятый штук — это 1, 3, 4, 5 и 9. По теореме в множестве $F_{11}$ и должно быть пятый корней степени 5 из 1.

Займется теперь корнями степени 5 из 10. Один такой корень виден из таблицы — это 2, действительно, $2^5=10$. Чтобы получить все корни, нужно умножить 2 на все корни степени 5 из 1, которые мы уже нашли. Действительно, если $x^5=1$, то $(2x)^5=2^5\cdot x^5=10\cdot 1=10$. Ответ: классы 2, 6, 7, 8, 10, то есть все классы с четыыми индексами. To, что 10 — корень степени 5 из самого себя, не удивительно — ведь $10=-1$.

Квадратные вычеты и невечеты

Рассмотрим теперь частный случай — извлекание квадратных корней. Прежде всего нужно рассмотреть наиболее общий делитель $d$ чисел 2 и $p-1$. Если $p=2$, то $d=1$; если $p>2$, то $p$ нечетно, значит, $p-1$ четно и $d=2$. Рассмотрим случай нечетного $p$ (случай $p=2$ вы легко исследуете сами). Мы выяснили, что из класса с четыым индексом можно извлекать квадратный корень (причем их будет два для каждой класса), а из класса с четыым индексом нельзя извлекать квадратного корня. Классы с четыыми индексами называются квадратными вычетами, а с нечетными индексами — квадратными невычетами. Так как среди всевозможных значений индекса от 1 до $p-1$ имеется $\frac{p-1}{2}$ четных чисел и $\frac{p-1}{2}$ нечетных чисел, то среди $p-1$ нечувлевых классов квадратных вычетов и квадратных невычетов поровну. Интересно еще, что произведение вычета на вычет или невычета на вычет дает квадратный вычет, а произведение квадратного вычета на вычет дает невычет. Это следует из того, что при переменении классов их индексы складываются. Аналогичные утверждения справедливны и для частного. Например, частное от деления невычета на невычет — обязательно квадратный вычет.

Обратимся снова к $p=11$. Квадратные вычеты — это элементы с четыыми индексами, то есть все классы с четыыми индексами, то есть все корни степени 5 из 1. Такая скрытая симметрия имеет место для всех $p$, а не только для $11^*$).

Рациональные и irrationalные классы вычетов

Итак, не из всех классов можно извлекать корень. Например, квадратный корень, как мы убедились, можно извлекать только из положины нечувлевых классов.

Такое явление имеет место и для общих чисел. Вам хорошо известно, что в области рациональных чисел из числа 2, например, нельзя извлекавать квадратного корня. Вы знаe-

*) О квадратных вычетах и невычетах можно прочесть в «Кванте» № 1 за 1973 год (с. 2-9).

9

те также, что если расширить множество рациональных чисел и рассмотреть множество $R$ всех вещественных чисел, то в этом большем множество из числа 2 можно извлечь квадратный корень, и $\sqrt{2}$ является числом из множества $R$, только — irrationalным.

Давайте поступим аналогичным образом и с классами вычетов. Для наглядности рассмотрим опять $p=11$. Мы видели, что класс $\overline{2}$ — квадратный невычет, из него не извлекается квадратный корень. Построим большие множество $G \supset F_{11}$, в котором будет существовать квадратный корень из класса $\overline{2}$, то есть такой элемент $\alpha$, что $\alpha^2=\overline{2}$.

Так же, как и при геометрических построениях, проведем анализ. Прежде всего уточним постановку задачи. Чтобы равенство $\alpha^2=\overline{2}$ имело смысл, естественно считать, что для любой пары элементов множества $G$ определяено их произведение. Потребем также, чтобы была определена и сумма любых двух элементов в множестве $G$. В таком случае в $G$ должны содержаться всевозможные двух элементы $\overline{a}+\overline{b}\alpha$, где $\overline{a}, \overline{b} \in F_{11}$. Оказывается, этого уже вполне достаточно. Мы можем обчным образом определить сумму двухленов: $(\overline{a}+\overline{b}\alpha) + (\overline{c}+\overline{d}\alpha) = (\overline{a}+\overline{c}) + (\overline{b}+\overline{d})\alpha$. Например, $(\overline{5}+\overline{2}\alpha) + \overline{9}\alpha=5$.

При умножении возникают члены с $\alpha^2$. Мы будем заменять $\alpha^2$ на $\overline{2}$. Например, $(\overline{3}+\overline{7}\alpha)(\overline{5}+\overline{2}\alpha) = \overline{3}\cdot\overline{5} + (\overline{7}\cdot\overline{5}+\overline{2}\cdot\overline{3})\alpha + \overline{2}\cdot\overline{7}\alpha^2 = 10+\overline{8}\alpha$.

В множестве $G$ столко элементов $\overline{a}+\overline{b}\alpha$, сколько существует пар $\overline{a}, \overline{b} \in F_{11}$, то есть $11^2=(121)$. Поэтому для него принято обозначение $F_{11^2}$. Не нужно путь этого множество с множеством $F_{121}$ классов вычетов по модулю 121, в котором тоже 121 элемент. В отличие от $F_{121}$, в $F_{11^2}$ существует частное от деления $\overline{a}+\overline{b}\alpha$ на $\overline{c}+\overline{d}\alpha$, если только $\overline{c}$ и $\overline{d}$ не равны одновременно нулю. Это утверждение доказывается в два этапа. Сначала рассмотрим случай, когда $\overline{d}=0$. Легко проверить, что $(\overline{a}+\overline{b}\alpha) : c = \overline{a}/\overline{c} + (\overline{b}/\overline{c})\alpha$. Общий случай сво-

дится к этому, если умножить делимое и делитель на $\overline{c}-\overline{d}\alpha$. Тогда придется делить на $\overline{c}^2-2\overline{d}^2$. Этот элемент множества $F_{11}$ отличает от нуля, иначе бы мы имели $\overline{c}^2=2\overline{d}^2$, $\overline{2}=\left(\frac{\overline{c}}{\overline{d}}\right)^2$, и $2$ оказалось бы квадратным вычетом в $F_{11}$. Поэтому деление возможно.

В множестве $F_{11^2}$ известна квадратные корни не только из $\overline{2}$, но и из всех классов $\overline{r} \in F_{11}$. Действительно, если $\overline{r}$ — квадратный вычет, квадратный корень извлекается уже в $F_{11}$. Если же $\overline{r}$ — невычет, то, как мы видели ранее, частное от деления $\overline{r}$ на $\overline{2}$ является квадратным вычетом и поэтому существует такой класс $\overline{s}$, что $\overline{r}=2\overline{s}^2$. В таком случае $\sqrt{\overline{r}}=\sqrt{2}\cdot\overline{s}^2=\overline{s}\alpha$.

Аналогичным образом можно построить $F_{p^2}$ для произвольного $p$. В связи с известением корней более высоких степени возникают множества $F_{p^3}, F_{p^4}$ и т.д. В множестве $F_{p^2}$ есть первообразный корень, то есть элемент максимального возможного порядка $p^2-1$. Интересно, что это утверждение мы фактически уже доказали: при доказательстве теоремы Лежандра мы используем только существование четырех действий и конечность изучаемого множества.

Задание и

1. Найти все первообразные корни в множестве $F_{13}$.
2. Уравнение $\overline{x}^2+\overline{y}^2=0$ имеет решение в множестве $F_p$ ($p>2$), отличное от $\overline{x}=\overline{y}=0$, в том и только в том случае, когда остаток от деления $\overline{p}$ на 4 равен 1.
3. Сколько решений у уравнения $\overline{x}^2-\overline{5x}+7=0$ в множестве $F_5$? а в $F_7$?
4. Сколько элементов являются кубами в $F_{13}, F_5, F_{11}$, в $F_p$? к-min степени?
5. Сколько первообразных корней в множестве $F_p$?
6. Сколько элементов в множестве $F_{11^2}$ являются квадратами?

Приложение

Основная теорема арифметики

Любое натуральное число $n>2$ может быть представлено в виде произведения простых множестелей; с моносвью до порядка множестелей может представление единственного.

А. Сначала метод математической индукции доказем существование