§ 6. Первообразные корни, индексы, двучленные сравнения.

Пусть простой модуль и а — не делящееся на число. Уже из теоремы Ферма (§ 4) видно, что существуют положительные показатели (например для которых Если — наименьший показатель такого рода, то говорят, что а принадлежит к показателю 8 по модулю этот показатель должен быть делителем числа так как в противном случае из вытекало бы причем Число принадлежащее к показателю называется первообразным корнем. Для такого числа степени очевидно, несравнимы по модулю и образуют поэтому приведенную систему вычетов по модулю гак что для каждого найдется показатель а, для которого Понятие о первообразном корне введено Эйлером стр. 516); однако Эйлеру не удалось строго доказать

существование первообразного корня для всякого простого числа Это было сделано впервые Гауссом Доказательство Гаусса, воспроизводимое ниже, является одним из самых блестящих примеров арифметического рассуждения. Пусть есть количество несравнимых по модулю чисел, принадлежащих к заданному делителю 8 числа как к показателю. Предположим, что существует хоть одно из таких чисел, например а; тогда 8 чисел несравнимы по модулю Все эти числа удовлетворяют сравнению так что других решений это сравнение иметь не может (теорема 4). Поэтому остальные числа (кроме а), принадлежащие к показателю нужно искать среди степеней Рассматривая же степень находим, что показатель к которому она принадлежит, есть наименьшее число, для которого делится на 8. Таким образом тогда и только тогда, когда Итак, при непременно Разобьем числа на группы, отнеся в одну группу все числа, принадлежащие к одному и тому же показателю ; в группе, соответствующей , будет чисел, так что получаем соотношение где сумма берется по всем делителям 8 числа Сравнивая его с аналогичным соотношением для функции [формула (4)], находим для всякого что для и дает теорему Гаусса:

Теорема 5. Для всякого простого числа существует несравнимых по модулю первообразных корней.

Разыскание первообразных корней при большом требует значительных вычислений и совершается путем проб. Гаусс дал метод, позволяющий уменьшить количество этих проб (см. 20, D. A., art. 73). Лишь для некоторых специальных форм модуля П. Л. Чебышеву (см. 82, стр. 198) удалось указать первообразный корень. Простейшие из теорем Чебышева следующие: 1) для простого числа формы первообразным корнем является число 3, 2) если в простом числе число и также простое, то первообразным корнем будет 2.

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

(через обозначаем корень сравнения ). Если построены таблицы, дающие для каждого числа его индекс, и обратно, то эти таблицы приносят такую же пользу при решении сравнений, как и таблица логарифмов при обычных действиях; например, решение сравнений приводится к вычитанию и делению по модулю Таблицы индексов были вычислены Якоби 30 для всех простых чисел до

Индексы приносят пользу и в теоретических рассуждениях; желая, например, рассмотреть вопрос о разрешимости двучленного сравнения суть данные числа], перейдем в нем к индексам и применим известную нам (§ 4) теорему о сравнениях первой степени. Тогда получим: пусть для разрешимости сравнения необходимо условие при выполнении которого данное сравнение имеет несравнимых решений. Эта теорема принадлежит Эйлеру.

Если сравнение разрешимо, то число А называется вычетом степени, в противном случае — невычетом степени для простого числа По сказанному выше, для того чтобы А было вычетом степени, необходимо и достаточно условие Рассматривая в последнем сравнении А как неизвестную и прилагая к нему теорему о двучленных сравнениях, находим, что существует несравнимых между собою вычетов степени.

Остальные членов приведенной системы вычетов будут невычетами степени. Представляется целесообразным разбить все невычеты на групп, каждая из которых содержала бы членов, т. е. столько, сколько существует вычетов. Это делается следующим образом. Пусть одно из чисел, принадлежащих к показателю ; так как все решения сравнения заключаются в ряде то из теоремы Ферма вытекает, что всякое число удовлетворяет одному (и только одному) из сравнений

Объединим в группу все числа А, для которых показатель а в этом сравнении один и тот же. Тогда 1) каждая группа состоит из чисел, 2) 0-я группа состоит из вычетов степени, 3) отношение двух чисел одной группы есть вычет степени, 4) произведение числа группы на число группы принадлежит к [или ] группе. При замене числа другим числом, принадлежащим к показателю 8, меняется только нумерация групп (кроме нулевой). Указанные 8 групп можно характеризовать еще и так: индексы чисел одной и той же группы (по какому-нибудь фиксированному первообразному корню) имеют одинаковый вычет по модулю При вычеты называются квадратичными, кубическими, биквадратичными.

Обращаясь к составному модулю к, возьмем сначала случай где нечетное простое число. В этом случае также существуют первообразные корни, т. е. числа, принадлежащие к наивысшему

возможному показателю что легко выводится из теоремы Взяв один из них можем представить приведенную систему вычетов для модуля в виде Иначе обстоит дело в случзе ; приведенная система вычетов для этого модуля представляется в виде цикла только при или 2. При всякое число удовлетворяет сравнению и поэтому первообразного корня не существует; взяв одно из чисел принадлежащих к показателю можем написать приведенную систему вычетов модуля в виде где независимо от него, Наконец, для любого составного числа различные нечетные простые числа, пользуясь теоремой о линейных сравнениях по нескольким модулям (§ 4), находим следующий состав приведенной системы вычетов: где показатели пробегают независимо друг от друга полные системы вычетов по модулям Числа определяются условиями: отсутствует при при число отсутствует при при далее Числа выбраны для отдельных модулей принадлежащими к показателям Теорема эта с точки зрения теории групп основной базис абелевой группы классов чисел по модулю взаимно простых с к (§ 4).