Сравнение по модулю

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:06, 14 мая 2016.

Решение сравнений

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

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

Сравнения n-ой степени по простому модулю

Сравнения n-ой степени по составному модулю

Общие свойства

Общий вид сравнения:

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

, при этом

Свойства таких сравнений:

1) Сравнение вида , где -простое эквивалентно сравнению степени не выше

Доказательство: , следовательно все члены суммы (по малой теореме Ферма) у которых степень выше сводятся к членам степени не выше ч.т.д.

2) Сравнение вида имеет не более корней.

Доказательство: От обратного: пусть корней больше, чем и их как минимум . Составим произведение . Раскрывая скобки, получим выражение степени , что противоречит условию (степень сравнения ). Значит корней не больше чем , ч.т.д.

Линейное сравнение

Существует два случая:

1) , следовательно . Решение всегда существует и единственно.

2) . Сравнение можно представить в виде: . .

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

б) Если , то: , при этом новый коэффициент при с новым модулем взаимно просты, следовательно смотри пункт 1. Следовательно исходное сравнение имеет решений вида , где . Других решений нет.

Системы сравнений

Система вида I

Возьмем следующие числа:

Общее решение: (Китайская теорема об остатках)

Система вида II

Система эквивалентна сравнению .

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

: Пусть . Это значит, что делится на этот модуль нацело, т.е.

Если

Количество решений системы вида II

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

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

. Если решение существует, то -вычет степени по модулю . Если решения не существует, то -невычет степени по модулю .

Квадратичный вычет - вычет степени 2.

Рассмотрим сравнение . Если решение существует то -квадратичный вычет.

В приведенной системе вычетов: , для нечетного. Разобъем это множество на две части:

Квадраты этих чисел совпадают по модулю , следовательно квадратов штук. Столько же и вычетов и невычетов, иначе у сравнения было бы 2 решения, что противоречит доказанной ранее теормеме.


Символ Лежандра

Символ Якоби

Задачи

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

Найти все пары чисел, удовлетворяющих уравнению

Перечислить квадратичные вычеты

В вычетов.

Вычеты -