Сравнения первой степени с одним неизвестным
Рассмотрим сравнение (1) 
Т1. Если ( a , m )=1, то сравнение (1) имеет решение и притом единственное.
Т2. Если ( a , m )=d и 
, то сравнение (1) не имеет решений.
Т3. Если (a , m )=1 и 
то сравнение (1) имеет 
решений.
Примеры.
1. Сравнение 
имеет единственное решение, т.к. НОД (3, 7)=1.
2. Сравнение 
не имеет решений, т.к. НОД (5, 15)=5 и 7 не делится на 5.
3. Сравнение 
имеет два решения, т.к. НОД (8, 10)=2 и 6 делится на 2.
Методы решений сравнений первой степени с одним неизвестным
Рассмотрим сравнение (1) 
.
1. Метод испытания полной системы вычетов по модулю 
.
Пример.
Решить сравнение 
. НОД(4, 7)=1 
.
Запишем полную систему вычетов по модулю 7 {0, 1, 2, 3, 4, 5, 6} и выясним, какое число удовлетворяет сравнению
, 
.
2. Метод Эйлера.
.
Пример. Решить сравнение 
. НОД(3, 10)=1 .
=4 
. 
.
3. Метод непрерывных дробей.
Разложим отношение коэффициента при х и модуля в конечную цепную дробь и воспользуемся свойствами подходящих дробей:
.
.
Пример.
Решить сравнение 
. НОД(17, 63)=1 .
.
| k | 0 | 1 | 2 | 3 | 4 | 5 |
| 0 | 3 | 1 | 2 | 2 | 2 |
| 0 | 1 | 1 | 3 | 7 | 17 |
| 1 | 3 | 4 | 11 | 26 | 63 |
. 
.
4. Искусственные приемы.
1) 
. Подберем t так, чтобы
.
Пример.
Решить сравнение 
. НОД(2, 9)=1 .
.
2) 
. Умножим обе части сравнения на такое целое число с, что 
Получим 
Учитывая, что
, получим 
|
|
|
Пример.
Решить сравнение 3 
. НОД(3, 5)=1 .
3 
Окончательно получаем 
. 
Обратите внимание, что все методы решения сравнений применяются только в том случае, когда сравнение имеет единственное решение.
Пример. Решить сравнение любым методом 
НОД(10, 45)=5, 
сравнение имеет 5 решений.
Разделим обе части сравнения и модуль на 5, получим равносильное сравнение 
НОД(2, 9)=1, значит сравнение имеет единственное решение. Так как 
сравнение принимает вид 
, и т.к. НОД(2, 9)=1 разделим обе части сравнения на 2. Получим 
. Возвращаемся к модулю 45 и находим 5 решений данного сравнения по формуле 
, где t= 
. В результате получаем:
, 
и 
.
Показатель числа a по модулю m
Пусть 
.
Определение. Показателем числа а по модулю m называется наименьший положительный показатель степени числа а, сравнимой с 1 по модулю m .
Обозначается: 
.
.
Пример. Найти 
.
.
Свойства 
1) 
2) 
3) 
Из свойства 2 следует, что 
является положительным делителем 
.
Пример. Найти 
.
2, 4, 7, 14, 28.
Находим числа, сравнимые со степенями числа 3 с показателями, равными делителям 
, пока в правой части сравнения не получим 1.
.
|
|
|
Первообразные корни по модулю m
Определение. Число а, взаимно простое с m , называется первообразным корнем по модулю m, если 
Примеры.
1) Число 
2) По модулю 
первообразных корней нет, т.к. 
и
,
,
.
Теорема. Если число а, взаимно простое с m , является первообразным корнем по модулю m, то числа 
образуют приведенную систему вычетов по модулю m.
Теорема Гаусса. По простому нечетному модулю p первообразные корни существуют и число их равно 
.
Первообразные корни по простому модулю p>2 можно находить:
1) По определению, т.е. найти показатель числа по модулю p, если он равен p-1, то число является первообразным корнем по модулю р, если он меньше (р-1), то число первообразным корнем не является
2) По теореме: если 
и 
то а- первообразный корень по модулю р.
Пример.
Следовательно, 7 – первообразный корень по модулю 11.
Дата добавления: 2021-05-18; просмотров: 473; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!