Случаи составного модуля
Теорема 2.11. Пусть число р простое, p≠2, целое число a не делится на р и n N, n≥ 1. Для того чтобы сравнение было разрешимо, необходимо и достаточно, чтобы было разрешимо сравнение
Определение 2.8. Порядком числа a, 1 ≤ a <m, НОД(а, m)= 1, по модулю m называется наименьшее натуральное число d, для которого 1 (mod m).
Определение 2.9. Число a, 1 ≤ a <m, порядка φ(m) по модулю m называется первообразным корнем по модулю m.
Свойство 2.12. Для числа а, имеющего порядок d по модулю m, сравнение (mod m) выполняется тогда и только тогда, когда (mod d).
Свойство. Если число а имеет порядок по модулю т, то число имеет порядок по модулю m.
Свойство 2.14. Если числа , имеют по модулю m порядки , соответственно, причем НОД( , )=1, то число имеет по модулю m порядок .
Теорема 2.15. Для любого простого р≠ 2 существует первообразный корень по модулю р.
Теорема 2.16. Для любого простого р≠ 2 существует первообразный корень по модулю .
Теорема 2.17. Если сравнение разрешимо, то оно имеет ровно два решения.
Следствие. Число квадратичных вычетов по модулю где р— простое число, р ≠ 2, равно числу квадратичных невычетов по модулю .
Do'stlaringiz bilan baham: |