Сравнения с неизвестной величиной. Решение алгебраических сравнений

1. Лекция 7 СРАВНЕНИЯ С НЕИЗВЕСТНОЙ ВЕЛИЧИНОЙ

2. Решение алгебраических сравнений

• Пусть многочлены f x , g x Z x
• Будем рассматривать сравнения вида
f x g x mod m
• Такие сравнения называют алгебраическими
• Если в такое сравнение вместо х подставлять
различные целые числа, то некоторые из них
могут удовлетворять сравнению, то есть при
их подстановке вместо х получается верное
числовое сравнение

3. Теорема 1 Если число с удовлетворяет сравнению то и весь класс по модулю т состоит из чисел, удовлетворяющих этому сравнению

Теорема 1
Если число с удовлетворяет сравнению
1
f x g x mod m ,
то и весь класс c по модулю т состоит из чисел,
удовлетворяющих этому сравнению
Доказательство
• Пусть b c mod m
• Тогда b k c k mod m , k = 0, 1, 2, …
• ak b k ak c k mod m
• Складывая такие сравнения, получим, что
f b f c mod m
g b g c mod m
• А так как по условию f с g c mod m , то по
транзитивностиf b g b mod m и b удовлетворяет (1)
• Таким образом вместе с с любое число b класса c тоже
удовлетворяет сравнению (1)

4. Определение Решением сравнения называется класс чисел по модулю т, удовлетворяющих этому сравнению

Определение
Решением сравнения
f x g x mod m ,
1
называется класс чисел по модулю т,
удовлетворяющих этому сравнению
• Числом решений сравнения называют число классов
чисел, удовлетворяющих сравнению
• Так как классов по модулю т конечное число, то для
решения сравнения (1) достаточно взять полную
систему вычетов по модулю т и отобрать те
классы, представители которых удовлетворяют (1)

5. Примеры

1. x 3 2 x 6 0 mod 11
Непосредственная проверка показывает, что в полной
системе наименьших по абсолютной величине вычетов
–5, –4, –3, –2, –1, 0, 1, 2, 3, 4, 5 сравнению
удовлетворяет только одно число 5
Решение записываем в виде x 5 mod 11
4
2
x
2
x
6 0 mod 8
2.
В полной системе вычетов –3, –2, –1, 0, 1, 2, 3, 4 ни
одно число не удовлетворяет сравнению и,
следовательно, сравнение не имеет решений
3. x 3 x 0 mod 3
Этому сравнению удовлетворяет любое число (по
теореме Ферма). Сравнение имеет 3 решения – классы
0,1, 2

6. Равносильные сравнения

Определение
Пусть f x , g x , f1 x , g1 x Z x
Сравнения f x g x mod m и f1 x g1 mod m1
называются равносильными (эквивалентными),
если множества чисел, удовлетворяющих
этим сравнениям, совпадают

7. Теорема 2

1) Если к обеим частям сравнения f x g x mod m
прибавим любой многочлен u x Z x , то получим
сравнение, равносильное первоначальному
2) Если обе части сравнения f x g x mod m умножим на
одно и то же число, взаимно простое с модулем, то
получим сравнение, равносильное первоначальному
3) Если обе части сравнения и модуль умножим на одно и
то же натуральное число, то получим сравнение,
равносильное первоначальному.
Из теоремы 2 (пункт 1) следует, что сравнение
f x g x mod m
можно заменить равносильным сравнением
f x g x 0 mod m
Поэтому в дальнейшем достаточно рассматривать сравнение
F x 0 mod m
F x f x g x

8. Теорема 3

Пусть f x a0 a1x ... an x n и g x b0 b1x ... bn x n –
многочлены с целыми коэффициентами.
Если a0 b0 mod m , a1 b1 mod m , …, an bn mod m , то
сравнения f x 0 mod m и g x 0 mod m равносильны.
Из теоремы следует, что сравнение заменится
равносильным, если отбросить или добавить
слагаемые с коэффициентами, кратными модулю
Пример
Сравнения 17 x15 20 x10 12 x 5 6 x 4 1 0 mod 3 и
2 x15 x10 1 0 mod 3 равносильны, так как
17 2, 20 1, 12 0, 6 0 по модулю 3

9.

Определение
Степенью сравнения f x 0 mod m называют
степень многочлена f x , если старший
коэффициент f x не делится на т
Пример
Степень сравнения 14 x12 35 x 7 10 x 2 3 0 mod 7 равна
двум, так как 14 7, 35 7 , а само сравнение равносильно
3 x 2 3 0 mod 7

10. Лекция 8 СРАВНЕНИЯ ПЕРВОЙ СТЕПЕНИ

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

Сравнение 1-ой степени может быть приведено к виду
ax b(mod m )
(2)
Теорема 4
Если (a, m) 1, то сравнение (2) имеет
единственное решение
Теорема 5
Если (a, m) 1 , то решением сравнения (2) является
класс
x0 a ( m) 1 b(mod m)

12. Методы решений сравнения

ax b(mod m )
(2)
1. Метод подбора
2. Использование теоремы Эйлера
3. Метод преобразования коэффициентов

13.

Теорема 6
Если (a, m) d и b не делится на d, то сравнение
(2) не имеет решений
Теорема 7
Если (a, m) d , d 1 и b d , то сравнение (2)
имеет d решений, которые составляют один
m
класс вычетов по модулю d и находятся по
формулам
m
x0 c mod m , x1 c
d
mod m ,
m
m
x 2 c 2 mod m , ..., xd 1 c d 1 mod m ,
d
d
где с удовлетворяет вспомогательному сравнению
a
b
m
x mod .
d
d
d

14.

Алгоритм решения сравнения
ax b(mod m )
(2)
1) Убедившись, что (a, m) d , d 1 и b d , делим
обе части и модуль сравнения (2) на d и
получаем вспомогательное сравнение
a
b
m
a1x b1 mod m1 , где a1 , b1 , m1
d
d
d
Сравнение имеет единственное решение.
Пусть c это решение
2) Записываем ответ
x0 c mod m , x1 c m1 mod m ,
x2 c 2m1 mod m , ..., xd 1 c d 1 m1 mod m .

15. Неопределённые уравнения Диофантово уравнение первой степени с двумя неизвестными , где Требуется решить это уравнение в целых

Неопределённые уравнения
Диофантово уравнение первой степени с двумя
неизвестными ax by c , где a, b, c Z
Требуется решить это уравнение в целых числах
• Если (a, b) d и с не делится на d, то очевидно, что
сравнение не имеет решений в целых числах
• Если же с делится на d, то поделим обе части
уравнения на d
• Поэтому достаточно рассмотреть случай, когда (a, b) 1
• Так как ax отличается от с на число, кратное b, то
ax c(mod b)
(без ограничения общности можно считать, что b 0 )
• Решая это сравнение, получим x x1 mod b или
x x1 bt где t Z

16. Неопределённые уравнения Диофантово уравнение первой степени с двумя неизвестными , где Требуется решить это уравнение в целых

продолжение
Неопределённые уравнения
Диофантово уравнение первой степени с двумя
неизвестными ax by c , где a, b, c Z
Требуется решить это уравнение в целых числах
• Для определения соответствующих значений y
c ax1
имеем уравнение a x1 bt by c , откуда y
at
b
c ax1
• Причём y1
– целое число, оно является
b
частным значением неизвестного y,
соответствующим x1(получается, как и x1, при t 0 )
• А общее решение уравнения примет вид
x x1 bt ,
где t – любое целое число
y y1 at