Решение сравнений и систем сравнений.

Изучим методы решения сравнений: ,

где .  

Если  удовлетворяет сравнению, то оно называется его решением.

Лемма. Если  и , то , то есть всякое число, сравнимое с  по модулю , тоже является решением сравнения.

Доказательство.    означает, что . 

, так как разность  состоит из слагаемых вида , каждое из которых обязательно делится на , которое в свою очередь, делится на .

 

Не всякое сравнение разрешимо. Так, при малых  можно проверить непосредственно: . Переформулируем иначе: Существует ли такое целое , что  ? 

Согласно лемме (см. выше), достаточно рассмотреть только 3 числа   (в общем случае ).  

, 

,

. 

 

Рассмотрим сравнения вида .

 

Теорема 1.

1) Если , то сравнение  имеет решение, причём единственное.

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

3) Если , и , то сравнение  имеет  решений.

Доказательство.

1) Пусть  полная система наименьших неотрицательных вычетов по модулю , среди них есть одно число, сравнимое с : . Но  тоже полная система вычетов (теорема 1 см. в прошлом §). Тогда среди них есть ровно одно число, сравнимое с  из множества , и тогда .  

 

2) Пусть . Тогда . Пусть сравнение разрешимо, тогда , т.е. , противоречие с тем, что  не делится на . 

Пример.   НОД (a,m)= 5.

, неразрешимо: 5x (напр, 5,10,15,20,…) не дают остаток 8 при делении на 10.

 

3) , и при этом , т.е. . 

, сократим на .  

Здесь уже вынесли НОД, т.е. как в п.1.  , значит, это сравнение имеет единственное решение, . Оно же является решением и для сравнения , так как  

. 

Перейдём к сравнениям по модулю . Есть  чисел вида , меньших , они попарно несравнимы по модулю   (все меньше чем ) и тоже являются решениями для . 

, добавляется величина, содержащая . 

 

Что этот п.3 в теореме означает, простыми словами на примере:

Пример. , НОД чисел  равен 2, и среди чисел  есть 2 числа, таких что  делится на 6 с остатком 4. 

Это 2 и 5. Результаты 4 и 10. Пара чисел, т.к. d=2.

 

 

ЛЕКЦИЯ 12. 20.3.2021.

 

Пусть , рассмотрим сравнение .

Если  то b можно перенести влево и вычесть из .

Теорема 2.  Если  - решение сравнения , то это сравнение равносильно , где  - неполное частное от деления  на . 

Доказательство.

 , где остаток  степени, меньшей чем 1, ведь делили на многочлен  степени 1. При этом заметим, что

, то есть остаток . По условию,  - это решение сравнения , то есть .  

 означает  , где остаток делится на , значит, и , что и означает . 

Следствие. Если  - решения сравнения , то оно равносильно сравнению , где  - некоторый многочлен степени  с тем же старшим коэффициентом, который был у . 

 

Теорема 3. Теорема Вильсона.

Число  является простым . 

Доказательство.

Необходимость. Пусть  простое. Тогда по малой теореме Ферма, , то есть , то есть . Так как есть   таких чисел , взаимно простых с , то сравнение  имеет  решений:  . 

Значит, . 

Кроме того, было .

Рассмотрим разность: .

Если раскрыть скобки, получим многочлен степени меньшей, чем , и оно имеет  решений. Это может быть, только если все коэффициенты делятся на , в частности свободный член уравнения, равный  = . Однако среди простых чисел, больших 2, нет чётных, так что  нечётное, а  чётное, поэтому  = . 

Отдельно рассмотрим при , в том случае вид такой:

, что очевидно и так 0. Впрочем, .

Достаточность.

Пусть для числа  верно ,и пусть оно не простое, , где . Тогда , т.е. . 

Но в таком случае , значит, число  присутствует в факториале:

, факториал  делится на , но тогда должно быть и , что приводит к противоречию, так как 1 не делится на . Значит, такого числа  не существует, и  простое.

Примеры.

 не делится на 4. 

 

 не делится на 6. 

,

здесь вспомним признак делимости: .   

и так далее.

Теорема 4.

Всякое сравнение  степени  равносильно некоторому сравнению степени не выше . 

Доказательство.

По малой теореме Ферма, , тогда .

Поделим многочлен на  с остатком: .

 делится на  по условию, первое слагаемое по малой теореме Ферма, значит, остаток  делится на . Таким образом, можно перейти к сравнению , где степень многочлена . 

Определение. Число  называется квадратичным вычетом по модулю , если разрешимо сравнение: .  

Теорема 5. Критерий Эйлера.

Число  является квадратичным вычетом по простому нечётному модулю , и не является квадратичным вычетом .

Доказательство.

Лемма 1. Если  - простое нечётное число, то возможны две ситуации: либо , либо . 

Доказательство. Так как нечётное, то  чётное, поэтому  целое. Поделим  на , и остаток обозначим через . Так как в этом случае , то , но по малой теореме Ферма , так что . Это значит, , то есть , таким образом,  может быть сравнимым только с 1 или . Напомним, что это был остаток от деления  на , так что  сравнимо только с 1 или  по модулю .

Лемма 2. Существует ровно  квадратичных вычетов по простому нечётному модулю .

Доказательство. Рассмотрим все числа, взаимно простые с  и меньшие чем , это . Возведём их в квадраты.

. Докажем, что .

, так как все слагаемые, кроме , делятся на . В таком случае, среди  квадратов вторая половина даёт те же самые остатки, что и первая (симметрично, см. пример ниже), и существует не более чем  квадратичных вычетов по модулю .

Допустим, что их меньше, то есть какие-то из этих вычетов  совпадающие, . Но тогда , при этом как сумма, так и разность меньше  и делиться на  не может. Сумма, так как оба числа меньше половины , разность тем более. Противоречие, в итоге вывод, что совпадающих среди этих  вычетов нет.

Пример.  , рассмотрим  чисел 1,2,3,4,5,6.

 ; 

. 

Вывод: только 1,2,4 могут быть квадратами чего-либо в поле вычетов . Это 3 числа, что как раз и равно .

 эти 3 сравнения неразрешимы.

Итак,

 ; . 

Рассмотрим теперь все   и установим, какие из них сравнимы с 1, а какие с . 

                   ()

         ()

       ().

Кубы именно тех чисел, которые являются квадратами чего-либо, сравнимы с 1, другие с .  

 

Доказательство.   Теперь докажем критерий Эйлера, с учётом информации из двух лемм.  Пусть  является квадратичным вычетом по модулю , то есть существует , такое что . В этом случае , тогда, возводя в степень , получим: , а по малой теореме Ферма . Следовательно, из-за транзитивности .

Итак, любой квадратичный вычет является корнем уравнения   степени . При этом ранее доказано, что существует  разных квадратичных вычетов. Так как  поле, то количество корней не может быть больше cтепени многочлена, и как раз эти  квадратичных вычетов и являются корнями. Оставшиеся  чисел и являются квадратичными невычетами, для них .