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

Действительно:

· так как

верно, то

· обратно, если

, то , следовательно,

Чтобы решить сравнение

, можно

1) взять любую полную систему вычетов по mod m:

2) вычислить

3) взять те числа

, при которых сравнение является верным, то есть Соответствующие классы , дадут все решения сравнения.

Удобнее брать полную систему наименьших по абсолютной величине вычетов по mod

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

Примеры.

1)

(mod 11).

классы вычетов по mod 11.

2)

Сравнение не имеет решения.

3)

Ответ:

Задача нахождения решения сравнения

проще, чем рассматриваемая в курсе алгебры задача нахождения решения уравнения . Так как решая уравнение в некотором бесконечном множестве (R, С) нельзя перебрать все числа . А решая сравнение , ищем решение в конечном кольце Z_m классов вычетов по mod m. Следовательно, с помощью конечного числа операций можно найти все решения. Но надо заметить, что при больших m будут громоздкие вычисления, поэтому надо изучить способы, позволяющие определить число решений, а иногда и способы нахождения решения с помощью возможно меньшего числа операций.

3.2 Сравнения вида

Рассмотрим сравнение с одной переменной вида

(3.3)

где

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

Определение 1. Решением сравнения (3.3) называется класс вычетов по mod m, состоящий из чисел, удовлетворяющих этому сравнению.

Теорема 1. Пусть

и многочлены с целыми коэффициентами и целое число удовлетворяет сравнению (3.3). Тогда весь класс вычетов (mod m) состоит из чисел, удовлетворяющих этому сравнению.

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

1) Так как число

удовлетворяет сравнению (3.3), то оно удовлетворяет сравнению , где .

2)

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

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

(3.4)

и

(3.5)

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

Если

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

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

Пример.

Решение первого сравнения:

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

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

Теорема 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).