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

2) mod m будет , следовательно, , поэтому число удовлетворяет сравнениюто

есть сравнению . Следовательно, число удовлетворяет сравнению (3.3). Таким образом, класс вычетов состоит из чисел, удовлетворяющих сравнению (3.3). Теорема 1 доказана.

Определение 2. Два сравнения

и

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

Если и сравнения (3.4) и (3.5) имеют одни и те же решения, то получим два эквивалентных сравнения по .

Эквивалентные сравнения могут иметь разную степень.

Пример.

Решение первого сравнения: , решением второго сравнения тоже будет класс вычетов . Следовательно, они эквивалентны. Но степени их различны (степень первого сравнения равна 1, степень второго – 3).

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

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

где .

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

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

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

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

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

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

2)

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

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

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

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

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

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

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

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

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