Решение сравнений методом подбора. Метод преобразования коэффициентов при решении линейных сравнений. 2 страница

35. Теорема о максимальном числе решений сравнения -й степени по простому модулю. Теорема Вильсона.
Теорема 5. Сравнение степени по простому модулю вида (1), где может иметь не более, чем решений.
Доказательство. Пусть сравнение (1) имеет решение , т.е. . Тогда по теореме Безу , где - многочлен с целыми коэффициентами степени с неизменным старшим коэффициентом , а . Тогда получаем сравнение . (6)
Таким образом, сравнение (1) эквивалентно сравнению .
Аналогично можно получить тождественное сравнение , если имеет решений и т.д., пока не получим неразрешимое сравнение

Возможны два случая.
В первом случае получаем тождественное сравнение ,(7)
которое показывает, что все найденные решения для , , …, являются также решениями сравнения Других решений (1) иметь не может, т.к. если и , то , т.к. остальные множители в (7) не делятся на , что противоречит принятому условию о неразрешимости сравнения .
Во втором случае получаем тождественное сравнение , которое аналогично не может иметь более решений. Теорема доказана.
Следствие. Если сравнение (1) при отказе от требования имеет более, чем решений, то все коэффициенты делятся на .
Теорема 6. Сравнение степени с коэффициентом 1 при старшем члене имеет решений тогда и только тогда, когда все коэффициенты остатка от деления на кратны .
Доказательство Пусть или , (8)
Причём имеют целые коэффициенты, , .
Пусть сравнение имеет решений, тогда имеет эти же решений, т.к. , но т.к. имеет степень , то по следствию все коэффициенты делятся на .
Обратно, пусть все коэффициенты делятся на , тогда из (8) следует тождественная справедливость сравнения , т.е. оно имеет решений. Но любое решение этого сравнения удовлетворяет по крайней мере одному из сравнений , имеет решений, а сравнение имеет решений. Тогда общее число решений этих сравнений . Т.к. , то .
С другой стороны , т.е. сравнение имеет ровно значений. Теорема доказана.
Теореме7 (Вильсона) Если - простое число, то . (9)
Доказательство. Сравнение имеет , т.е максимальное число решений. Эти решения . Следовательно, .
Подставим :

или .
Если - нечётное, то .
Если , то - верно.
Теорема доказана.
Замечание1. Для составного числа теорема Вильсона не верна.
Замечание2. Справедлива обратная теорема: Если для целого
положительного числа имеет место соотношение (9), то - простое число. Однако этот критерий не имеет непосредственного применение на практике, т.к. для небольших число очень большое.

36. Приведение сравнения n-й степени по составному модулю к системе сравнений. Приведение сравнения по составному
Теорема 8. Пусть (10) и , где для . Тогда сравнение (10) равносильно системе:

(11)
Доказательство.
1. Если сравнение имеет место по некоторому модулю , то оно имеет место по любому модулю, являющимся делителем , т.е. если удовлетворяет (10), то удовлетворяет каждому сравнению (11).
2. Если сравнение справедливо по модулям , то оно справедливо и по модулю равному , т.к. для .
Замечание Если сравнение (10) имеет решений, а отдельные сравнения системы (11) имеют , то .
Рассмотрим Сравнение (11)
Решать (11) методом подбора неудобно.
Сведём решение этого сравнения к сравнению по модулю р виде (1).. Действительно, всякое , удовлетворяющее (11) удовлетворяет и (1), т.к. если , то .
Поэтому решение сравнения (11) надо искать среди решений сравнения (1). Сделаем это постепенно переходя от сравнения (1) к сравнению по модулю . Пусть или . Где .

Выберем из (12) такие целые значения .
Для вычисления левой части удобно заменить многочлен его разложением по формуле Тейлора .

За исключением первых двух слагаемых, все остальные содержат в степени , следовательно . Т.к. , то илb . (12)
1 случай. Если , то из (13) или , где . Подставляя найденные в (11) получаем .(13)
При формула (13) даёт одно из решений сравнения . Обозначим его через , тогда , где Или Переходя к решению сравнения , (14) на накладываем требование .
Далее применяем формулу Тейлора и процесс повторяем пока не придём к решению сравнения . Итак, в случае каждое решения сравнения (1) приводит к одному решению сравнения (11).
2 случай. Если , а правая часть (12) на не делится, то сравнение (12), а значит и (11) не разрешимы.
3 случай. Если и правая часть (12) делится на , то сравнение (12) тождественное и ему удовлетворяют все целые числа , тогда сравнение будет иметь решений. Из этих решений будем далее общим приёмом выделять те числа, которые удовлетворяют сравнению по и т.д.

37 Сравнения второй степени, их связь с неопределёнными уравнениями второй степени с двумя неизвестными. Приведение Сравнений второй степени к двучленным сравнениям.
Определение. Сравнением второй степени называется сравнение вида (1).
Сравнение второй степени (1) равносильно неопределённому уравнению второй степени вида
Определение. Двучленным сравнением второй степени называется сравнение вида (3).
Сравнение второй степени (1) можно привести к двучленному сравнению (3).
Умножим обе части и модуль сравнения на : Дополним до полного квадрата: , .
Обозначим , тогда получаем двучленное сравнение , (4)

Каждое число, удовлетворяющее (1), будет также удовлетворять (4), поэтому из неразрешимости (4) следует неразрешимость (1). Однако, из разрешимости (4) относительно ещё не следует разрешимость (1) относительно .
Действительно, каждое решение (4) приводит к сравнению относительно или т.к. , то если , то сравнение (5),а следовательно и (1) не имеют решение. Если , то сокращая обе части сравнения и модуль на , а для сравнения (1) необходимо указать решение по модулю , количество классов решений может уменьшиться.

38 Приведение Сравнений второй степени к двучленным сравнениям.
Определение. Сравнением второй степени называется сравнение вида (1).
Сравнение второй степени (1) равносильно неопределённому уравнению второй степени вида
Определение. Двучленным сравнением второй степени называется сравнение вида (3).
Сравнение второй степени (1) можно привести к двучленному сравнению (3).Умножим обе части и модуль сравнения на : Дополним до полного квадрата: , .Обозначим , тогда получаем двучленное сравнение ,(4)
Каждое число, удовлетворяющее (1), будет также удовлетворять (4), поэтому из неразрешимости (4) следует неразрешимость (1). Однако, из разрешимости (4) относительно ещё не следует разрешимость (1) относительно .Действительно, каждое решение (4) приводит к сравнению относительно или (5)
т.к. , то если , то сравнение (5),а следовательно и (1) не имеют решение. Если , то сокращая обе части сравнения и модуль на , а для сравнения (1) необходимо указать решение по модулю , количество классов решений может уменьшиться.

39 Двучленные сравнения по простому модулю: квадратные вычеты и невычеты, критерий Эйлера.
Пусть дано двучленное сравнение (3): и .
Определение. Если сравнение (3) разрешимо, то называется квадратичным вычетом по модулю . Если сравнение (3) неразрешимо, то называется квадратичным невычетом по модулю .
Рассмотрим двучленное сравнение по нечётному простому модулю.

40 Символ Лежандра и его свойства. Закон взаимности квадратичных вычетов.
Определение Пусть - нечётное простое число и не делится на . Символ Лежандра называется символ вида Читается - «символ Лежандра по отношению к », - числитель, - знаменатель символа.
Свойства символа Лежандра:
1⁰. Если то .
2⁰. , т.е. 1 – квадратичный вычет для любого нечётного простого , т.к. сравнение всегда разрешимо.
3⁰.
Следствие.