Теория сравнений

Таким образом, сравнения (3.6) и (3.11), где , будут эквивалентными.

3) Пусть класс вычетов по модулю решение сравнения (3.6), тогда для >верно сравнение , а, значит, верно и сравнение

4)

для любого натурального числа , поэтому класс вычетов по модулю решение сравнения

Обратно, если класс вычетов по модулю решение сравнения (3.13), то для верно сравнение (3.12), но тогда по свойству сравнений верно сравнение: , поэтому класс вычетов по модулю решение сравнения (3.6). Следовательно, сравнения (3.6) и (3.13) эквивалентны. Теорема доказана.

В дальнейшем сравнение (3.6) можно заменить эквивалентным сравнением:

где Теорема 1 доказана.

Теорема 2. Пусть даны сравнения Тогда сравнения эквивалентны.

Доказательство. Умножим почленно верные сравнения на некоторое целое число:

Сложим почленно полученные сравнения, тогда получим сравнение:

отсюда получим, что . Но тогда и . Следовательно, сравнения и эквивалентны. Теорема 2 доказана.

Заметим, из доказанной теоремы, в частности, следует, что сравнение заменится эквивалентным, если отбросить (или добавить) слагаемое с коэффициентами, делящимися на модуль.

3.4 Сравнения по простому модулю с одним неизвестным

Переходя от сравнений 1-й степени к сравнениям более высоких степеней, целесообразно сначала рассмотреть тот случай, когда модуль – простое число. В этом случае имеется ряд весьма важных теорем, которые, вообще говоря, неверны для составных модулей. Вместе с тем теория сравнений по простому модулю является основой, на которой строится изучение сравнений по составному модулю.

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

Теорема 1.Если , то сравнение

может быть заменено эквивалентным сравнением с коэффициентом при старшем члене, равном единице.

Доказательство. Рассмотрим сравнение 1-й степени ; поскольку то и сравнение имеет решение. Найдем число , удовлетворяющее этому сравнению, т.е. такое, что .

Тогда сравнение эквивалентно сравнению

,

а следовательно, сравнению

,

где .

Пример 1. Заменить сравнение

эквивалентным сравнением с коэффициентом при старшем члене, равным 1.

Решаем сравнение и находим . Данное нам сравнение эквивалентно сравнению

т.е. сравнению .

Теорема 2. Если и многочлены с целыми коэффициентами, то сравнения по простому модулю

эквивалентны.

Доказательство. Пусть удовлетворяет сравнению (3,15), т.е. . Поскольку при любом согласно теореме Ферма , то

 Скачать реферат