Рассмотрим вопрос о распределении в классах по модулю последовательности
(1)
где - некоторое число, взаимно простое с модулем. По теореме Эйлера имеем , и поэтому , при любом целом положительном . Следовательно, среди степеней (1) числа найдется бесконечное количество чисел, сравнимых с 1 по модулю .
Определение 1. Наименьшее натуральное число , для которого справедливо сравнение
(2)
называется показателем числа по модулю или показателем, которому принадлежит число по модулю и обозначается символом .
Очевидно, что. Требование является существенным.
Определение 2. Если , то называют первообразным корнем (примитивным) по модулю .
1°. Если , то числа и принадлежат по этому модулю одному и тому же показателю, то есть .
Доказательство. Пусть , . Так как , то
.
Следствие 1. Все числа одного и того же класса имеют один и тот же показатель.
2°. Если , то .
Доказательство. Необходимость. Пусть . По теореме о делении с остатком имеем , причем . Поскольку , то . Следовательно, . А это означает, что .
Достаточность. Пусть . Тогда . Поскольку , то , то есть .
Следствие 2. Если и , то .
Следствие 3. Показатель , которому принадлежит число по модулю , является делителем числа , то есть .
3°. Если , то .
Следствие 4. Показатель, которому принадлежит по модулю произведение чисел , равен произведению показателей, которым принадлежат по модулю числа , если показатели попарно взаимно простые.
4°. Если , то .
2. Первообразные корни.
Теорема 1. Если - первообразный корень, то система - ПрСВ.
Действительно, в данной системе имеется - вычетов, они не сравнимы и взаимно просты с модулем .
Теорема 2. По любому простому модулю существует хотя бы один первообразный корень.
Доказательство. Действительно, пусть
(3)
- все различные показатели, которым по модулю принадлежат числа
. (4)
Пусть - наименьшее общее кратное этих показателей и - его каноническое разложение. Каждый множитель этого разложения делит по меньшей мере одно число ряда (3), которое, следовательно, может быть представлено в виде: . Пусть - одно из чисел ряда (4), принадлежащих показателю . Согласно свойству 4° число принадлежит показателю , согласно свойству 3° произведение принадлежит показателю . Поэтому, согласно следствия 2 свойства 2° показателей, - делитель . Но поскольку числа (3) делят , все числа (4) являются решениями сравнения ; поэтому будем иметь . Следовательно, и - первообразный корень.
Теорема 3. Если существует хотя бы одно число, принадлежащее по модулю показателю , то всего классов таких чисел будет .
Следствие 5. Первообразных корней по простому модулю существует .
