Теоремы об эквивалентных сравнениях

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

(3.6)

где .

Тогда имеют место следующие утверждения:

1) Если к обеим частям сравнения (3.6) прибавить любой многочлен  то получится сравнение, эквивалентное сравнению (3.6).

2) Если обе части сравнения (3.6) умножить на одно и то же целое число, взаимно простое с модулем, то получится сравнение, эквивалентное сравнению (3.6).

3) Если обе части сравнения и модуль умножить на одно и то же натуральное число , то получится сравнение, эквивалентное сравнению (3.6).

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

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

2)

(3.7)

является верным сравнением, следовательно, сравнение

,

(3.8)

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

(3.9)

Обратное также верно: если  решение сравнения (3.9), то для , будет верно сравнение (3.8), а, следовательно, верно сравнение (3.7), поэтому  является решением сравнения (3.6).

Таким образом, сравнения (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 доказана.

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