Теорема 3 Пусть и – многочлены с целыми коэффициентами

Теорема 3

Пусть и – многочлены с целыми коэффициентами.

Если , , …, , то сравнения и равносильны.

Из теоремы следует, что сравнение заменится равносильным, если отбросить или добавить слагаемые с коэффициентами, кратными модулю

Пример

Сравнения и

равносильны, так как

по модулю 3

Определение

Определение

Степенью сравнения называют степень многочлена , если старший коэффициент не делится на т

Пример

Степень сравнения равна двум, так как , а само сравнение равносильно

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

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

Сравнение 1-ой степени может быть приведено к виду

Теорема 4

Если , то сравнение (2) имеет единственное решение

Теорема 5

Если , то решением сравнения (2) является класс

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

• Метод подбора
• Использование теоремы Эйлера
• Метод преобразования коэффициентов

Теорема 6

Теорема 6

Если и b не делится на d, то сравнение (2) не имеет решений

Теорема 7

Если и , то сравнение (2) имеет d решений, которые составляют один класс вычетов по модулю и находятся по формулам

где с удовлетворяет вспомогательному сравнению

Алгоритм решения сравнения

Алгоритм решения сравнения

• Убедившись, что и , делим обе части и модуль сравнения (2) на d и получаем вспомогательное сравнение

, где

Сравнение имеет единственное решение.

Пусть это решение

2) Записываем ответ

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

• Если и с не делится на d, то очевидно, что сравнение не имеет решений в целых числах
• Если же с делится на d, то поделим обе части уравнения на d
• Поэтому достаточно рассмотреть случай, когда
• Так как ax отличается от с на число, кратное b, то

(без ограничения общности можно считать, что )

• Решая это сравнение, получим или

где

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

• Для определения соответствующих значений y имеем уравнение , откуда
• Причём – целое число, оно является

частным значением неизвестного y, соответствующим (получается, как и , при )

• А общее решение уравнения примет вид где t – любое целое число