Сравнения первой степени.
Любое сравнение первой степени можно привести к виду ax ≡ b (mod m). Рассмотрим случай, когда (a, m)=1. Согласно утверждению 2 пункта 3 §3, когда x пробегает полную систему вычетов по модулю m, ax тоже пробегает полную систему вычетов по по модулю m. Следовательно, при одном и только одном значении x из полной системы вычетов, ax будет сравнимо с b, т.е. при (a, m)=1 сравнение имеет ровно 1 решение.
Нахождение решения: Так как (a, m) = 1, то по теореме обратимости a-1 , и тогда исходному сравнению равносильно x ≡ a-1∙b (mod m).
Пусть теперь (a,m)=d>1. Для того, чтобы сравнение имело решение, необходимо, чтобы d\b, иначе сравнение невозможно (свойство сравнений №14).
Если же a=a1d, b=b1d, m=m1d , то исходному сравнению равносильно a1x≡b1(mod m1), причем (a1,m1)=1 сравнение имеет 1 решение по mod m1: x≡x1(mod m1), или d решений по модулю m:
x≡ x1 (mod m),
x≡ x1+m1(mod m),
x≡x1+2m1(mod m),
…
x≡x1+(d–1)m1(mod m).
Пример 1.
Решить сравнение 6x = 5 (mod 35).
Вычислим НОД(6, 35), пользуясь алгоритмом Евклида:
35 = 6∙5+5,
6 = 1∙5 +1
5 = 5∙1+0 НОД(6, 35)=1.
Вычислим обратный элемент к 6 по модулю 35, пользуясь расширенным алгоритмом Евклида:
1 = 6–5=6–(35–6∙5)=6–35+6∙5= 6∙6–35
6-1 = 6 (mod 35).
Домножим правую и левую части исходного сравнения на 6:
6-1∙6x≡6-1∙5(mod 35)
1∙x≡6∙5(mod 35)
Ответ: x ≡ 30 (mod 35)
Пример 2.
Решить сравнение 18x = 6 (mod 24).
Вычислим НОД(18, 24), пользуясь алгоритмом Евклида:
24 = 18 + 6;
18 = 2∙6+0 НОД(18, 24)=6.
Правая и левая части сравнения, а также модуль, делятся на 6. Разделим исходное сравнение на 6 и получим равносильное сравнение:
3x ≡ 1 (mod 4) *.
Вычислим НОД(3, 4), пользуясь алгоритмом Евклида:
4 = 1∙3 + 1;
3 = 3∙1 + 0 НОД(3, 4)=1.
Вычислим обратный элемент к 3 по модулю 4, пользуясь расширенным алгоритмом Евклида:
1=4–3 3-1 = –1(mod 4).
Домножим правую и левую части сравнения (*) на –1:
3-1∙3x=–1∙1 (mod 4) x≡ –1 (mod 4).
Или, переводя решение в систему наименьших неотрицательных вычетов, x≡ 3 (mod 4).
Ответ: получили 6 решений по модулю 24:
x≡ 3 (mod 24);
x≡ 7 (mod 24);
x≡ 11 (mod 24);
x≡ 15 (mod 24);
x≡ 19 (mod 24);
x≡ 23 (mod 24).
Дата добавления: 2018-11-26; просмотров: 761;