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

причем, .

Целое число удовлетворяет сравнению (3.1), если сравнение является верным сравнением.

Теорема 1. Пусть дано сравнение (3.1) и целое число удовлетворяет сравнению (3.1). Тогда весь класс по mod m состоит из чисел, удовлетворяющих сравнению (3.1).

Доказательство. Число удовлетворяет сравнению (3.1), следовательно, верное сравнение. Для любого всегда . Но тогда по свойству сравнений , поэтому по транзитивности получим, что , отсюда следует, что число удовлетворяет сравнению (3.1). А так как произвольное из , то, следовательно, весь класс вычетов по mod m состоит из чисел, удовлетворяющих сравнению (3.1). Теорема 1 доказана.

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

Если класс mod m является решением сравнения (3.1), то будем говорить, что класс удовлетворяет сравнению (3.1). Числом решений сравнения (3.1) называется число классов вычетов по mod m, удовлетворяющих сравнению (3.1).

Задача нахождения чисел, удовлетворяющих сравнению (3.1), сводится к нахождению классов, удовлетворяющих уравнению

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

· так как верно, то

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

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

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

2) вычислить

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

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

Примеры.

1) (mod 11).

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

2)

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

3)

Ответ:

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

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

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

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

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

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

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

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

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