Сравнения первой степени.


 

Любое сравнение первой степени можно привести к виду axb (mod m). Рассмотрим случай, когда (a, m)=1. Согласно утверждению 2 пункта 3 §3, когда x пробегает полную систему вычетов по модулю m, ax тоже пробегает полную систему вычетов по по модулю m. Следовательно, при одном и только одном значении x из полной системы вычетов, ax будет сравнимо с b, т.е. при (a, m)=1 сравнение имеет ровно 1 решение.

Нахождение решения: Так как (a, m) = 1, то по теореме обратимости a-1 , и тогда исходному сравнению равносильно xa-1b (mod m).

Пусть теперь (a,m)=d>1. Для того, чтобы сравнение имело решение, необходимо, чтобы d\b, иначе сравнение невозможно (свойство сравнений №14).

Если же a=a1d, b=b1d, m=m1d , то исходному сравнению равносильно a1xb1(mod m1), причем (a1,m1)=1 сравнение имеет 1 решение по mod m1: x≡x1(mod m1), или d решений по модулю m:

xx1 (mod m),

xx1+m1(mod m),

xx1+2m1(mod m),

xx1+(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-13x=–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; просмотров: 662;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.007 сек.