Первообразные корни и индексы

Пусть а, m – натуральные взаимно простые числа, причем тогда, согласно теореме Эйлера, . Наименьшее натуральное число n такое, что называется показателем, которому принадлежит число а по модулю m.

Приведем основные свойства показателей:

1) числа попарно не сравнимы по модулю m;

2) тогда и только тогда, когда

3) делится на n;

4) если bс – показатель, которому принадлежит число х по модулю m, то b – показатель, которому принадлежит число по модулю m;

5) пусть а – показатель, которому принадлежит число х по модулю m; b – показатель, которому принадлежит число y по модулю m, причем числа а и b взаимно простые, тогда ab – показатель, которому принадлежит число хy по модулю m.

Если – показатель, которому принадлежит число а по модулю m, то число а называется первообразным корнем по модулю m. Известно, что первообразный корень по модулю m существует тогда и только тогда, когда где р – нечетное простое число.

Для нахождения первообразных корней удобно использовать следующий факт. Пусть каноническое разложение числа , g – натуральное число, взаимно простое с числом m. Число g является первообразным корнем по модулю m тогда и только тогда, когда не сравнимо с 1 по модулю m для любого i.

Пусть или g – первообразный корень по модулю m, тогда числа образуют приведенную систему вычетов по модулю m. Пусть число а взаимно просто с числом m. Целое неотрицательное число d называется индексом числа а по модулю m при основании g, если Индекс d обозначают или Вообще говоря, индекс определен не однозначно, но если известен один из индексов d, то любой другой индекс можно найти по формуле

Свойства индексов:

1) ;

2) для любого натурального значения n.

Если для некоторого целого значения х, то число а называется вычетом степени n по модулю m. В противном случае, число а называется невычетом степени n по модулю m. В приведенной системе вычетов по модулю m число вычетов степени n по модулю m равно Число а является вычетом степени n по модулю m тогда и только тогда, когда где

Пусть Показатель, которому принадлежит число а по модулю m, равен В частности, число а является первообразным корнем по модулю m тогда и только тогда, когда В приведенной системе вычетов по модулю m количество чисел, принадлежащих показателю t, равно В частности, количество первообразных корней в приведенной системе вычетов по модулю m равно

Системой индексов нечетного числа а по модулю () называется пара чисел такая, что Зная одну пару индексов , можно найти все такие пары индексов по формулам где

Пусть каноническое разложение числа m, первообразный корень по модулю Упорядоченный набор называется системой индексов числа a по модулю m, если для любого Любая другая система индексов связана с исходной следующим образом: где

Пример 1. Найдите число первообразных корней в приведенной системе вычетов по модулю 31, и найдите эти первообразные корни.

Решение. Число первообразных корней в приведенной системе вычетов по модулю 31 равно Так как и , , , то число 3 является первообразным корнем по модулю 31. Число является первообразным корнем по модулю 31 тогда и только тогда, когда . Отсюда следует, что . Следовательно, . Первообразные корни по модулю 31: 3, 17, 13, 24, 22, 12, 11, 21.

Пример 2. Найдите число вычетов степени 6 в приведенной системе вычетов по модулю 31, а также найдите эти вычеты.

Решение. Искомое число вычетов равно . Число а является вычетом степени 6 по модулю 31 тогда и только тогда, когда Так как число 3 является первообразным корнем по модулю 31, то сравнение равносильно сравнению 5ind₃ a ≡0(mod 30). Отсюда , то есть . Следовательно, . Вычеты степени 6 в приведенной системе вычетов по модулю 31: 16, 8, 4, 2, 1.

Пример 3. Найдите, какому показателю принадлежит число 5 по модулю 29.

Решение. Так как , то показатель , которому принадлежит число 5 по модулю 29, делит число 28. Поскольку , , , , , то .

Пример 4. Постройте систему индексов числа 17 по модулю 8928.

Решение. Имеем . Используя таблицу индексов

по модулю 32, находим, что . Так как число 2 является первообразным корнем по модулю 9, число 3 является первообразным корнем по модулю 31, , , то набор является системой индексов числа 17 по модулю 8928.

4.1. Найдите число первообразных корней по модулю:

1) 59, 2) 143, 3) 2011, 4) 67, 5) 54.

4.2. Найдите все первообразные корни по модулю:

1) 41, 2) 29, 3) 50, 4) 54, 5) 23.

4.3. Найдите число вычетов четвертой степени в приведенной системе вычетов по модулю:

1) 41, 2) 29, 3) 50, 4) 54, 5) 23.

4.4. Найдите вычеты четвертой степени в приведенной системе вычетов по модулю:

1) 41, 2) 29, 3) 50, 4) 54, 5) 23.

4.5. Является ли число g первообразным корнем по модулю m, если

1) ; 2) ; 3) , ;

4) , , 5) , ?

4.6. Найдите показатель, которому принадлежит число 2 по модулю 31.

4.7. Пусть p, q – простые числа, Докажите, что

4.8. Докажите, что не существует натурального числа , большего 1, такого, что делится на .

4.9. Найдите все простые числа и целые числа , удовлетворяющие уравнению .

4.10. Докажите, что любой натуральный делитель числа Ферма имеет вид , . Используя этот факт, покажите, что наименьший простой делитель числа равен 641.

4.11. Найдите все нечетные натуральные , такие, что делится на .

4.12. Пусть натуральное число принадлежит показателю по модулю . Для любого натурального числа найдите показатель, которому принадлежит число по модулю .

4.13. Пусть натуральное число принадлежит показателю по модулю . Для любого натурального числа найдите натуральное число, которое принадлежит показателю по модулю .

4.14. В приведенной системе вычетов найдите все числа, принадлежащие показателю 6 по модулю 43.

4.15. Постройте систему индексов числа по модулю , если:

1) m =2624; 2) , ; 3) , ;

4) , ; 5) , .