Сравнения с одним неизвестным

Будем рассматривать сравнения вида a0xn + a1xn-1 + … + an≡ 0 (mod m) (*).

Если a0 не делится на m, то n называется степенью сравнения.

Решить сравнение – значит найти все x, ему удовлетворяющие. Два сравнения, которые удовлетворяют одни и те же значения x, называются равносильными.

Если сравнению (*) удовлетворяет какое-то x=x1, то ему же будут удовлетворять все числа, сравнимые с x1 по модулю m: x ≡ x1(mod m). Весь класс чисел, сравнимых с x1 по модулю m считается за одно решение. Таким образом, (*) будет иметь столько решений, сколько вычетов из полной системы ему удовлетворяет.

Пример:

x5+x+1=0 (mod 7) удовлетворяют x ≡ 2 (mod 7) и x ≡ 4 (mod 7) – 2 решения.

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

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

Нахождение решения: Так как (a, m) = 1, то по теореме обратимости Сравнения с одним неизвестным - student2.ru 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 Сравнения с одним неизвестным - student2.ru сравнение имеет 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 Сравнения с одним неизвестным - student2.ru НОД(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 Сравнения с одним неизвестным - student2.ru НОД(18, 24)=6.

Правая и левая части сравнения, а также модуль, делятся на 6. Разделим исходное сравнение на 6 и получим равносильное сравнение:

3x ≡ 1 (mod 4) *.

Вычислим НОД(3, 4), пользуясь алгоритмом Евклида:

4 = 1∙3 + 1;

3 = 3∙1 + 0 Сравнения с одним неизвестным - student2.ru НОД(3, 4)=1.

Вычислим обратный элемент к 3 по модулю 4, пользуясь расширенным алгоритмом Евклида:

1=4–3 Сравнения с одним неизвестным - student2.ru 3-1 = –1(mod 4).

Домножим правую и левую части сравнения (*) на –1:

3-1∙3x=–1∙1 (mod 4) Сравнения с одним неизвестным - student2.ru 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).

Система сравнений первой степени. Китайская теорема об остатках.

Рассмотрим систему сравнений

Сравнения с одним неизвестным - student2.ru *

От системы сравнений вида aix ≡ bi (mod mi) можно перейти к данной способом, указанным в п.1.

Наши рекомендации