Теория сравнений (стр. 8 из 12)

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

3) Пусть класс вычетов

по – решение сравнения (3.6), тогда для , получим верное сравнение . Возьмем целое число , взаимно простое с модулем: . Умножим последнее сравнение почленно на , получим верное сравнение:

(3.10)

отсюда получим, что класс вычетов

по модулю решение сравнения

(3.11)

Обратно, если класс вычетов

по модулю решение сравнения (3.11), то для верно сравнение (3.10), следовательно, будет верно и сравнение:

(заметим, что

, так как , в противном случае было бы: ). Поэтому класс вычетов по модулю решение сравнения (3.6).

Таким образом, сравнения (3.6) и (3.11), где

, будут эквивалентными.

3) Пусть класс вычетов

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

4)

(3.12)

для любого натурального числа

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

(3.13)

Обратно, если класс вычетов

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

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

(3.14)

где

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

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

Тогда сравнения эквивалентны.

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

некоторое целое число:

…

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

отсюда получим, что

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

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

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

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

Во всей этой главе буквой

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

Теорема 1. Если

, то сравнение

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

Доказательство. Рассмотрим сравнение 1-й степени

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

Тогда сравнение

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

,

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

,

где

.

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

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

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

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

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

.

Теорема 2. Если

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

	(3.15)
	(3.16)

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

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

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