Сравнения и их основные свойства.

⇐ ПредыдущаяСтр 3 из 14Следующая ⇒

Пусть m∊ N, - множество целых чисел. При делении каждого целого числа z∊ на m возможны остатки 0, 1, 2, …, m-1, т.к. по теореме о делении с остатком z=mq+r, 0≤ r< m. Таким образом, множество разбивается на классы. В каждый класс входит только те целые числа, которые при делении на m дают равные остатки. Обозначим классы следующим образом: , , …, . При таком разбиении множества число m называют модулем (обозначают mod m), а представитель каждого класса называют вычетом.

Пример. m=4. При делении на 4 возможны остатки 0, 1, 2, 3.

={-3, -4, 0, 4, 8, …}; ={-7, -3, 1, 5, 9, …};

={…, -6, -2, 2, 6, 10, …}; ={…, -1, 3, 7, …}.

Введя алгоритм операции над классами следующим образом:

= = можно показать, что они обладают свойствами ассоциированности, коммутативности и дистрибутивности относительно . Приняв, кроме того, класс за нейтральный элемент, а класс =( за противоположный, можно показать, что множество классов вычетов с выделенными операциями является кольцом.

Определение 1.2. Два числа a и b называются сравнимыми по модулю m, если они являются вычетами одного и того же класса по модулю m.

Обозначают: .

Определение 1.3. Два числа a и b называют сравнимыми по модулю m, если при делении на m они дают равные остатки.

Теорема 1.4. Для того, чтобы числа a и b были сравнимы по mod m необходимо и достаточно, чтобы их разность .

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

Необходимость.

⇒ ⇒ .

Достаточность. Пусть , , то , или + . Получаем равные остатки.

Свойства сравнений.

1 . Отношение является отношением эквивалентности на множестве , т.е. оно обладает свойством рефлексивности, симметричности и транзитивности.

2 . Сравнения по одному и тому же модулю можно почленно складывать, т.е. если и , то

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

По критерию имеем и . Тогда по свойствуотношения делимости , что и означает, что

Следствие1. К обеим частям сравнения можно прибавить одно и тоже число.

Следствие2. К одной части сравнения в другую можно переносить можно переносить число с противоположным знаком.

3 . Сравнения по одному и тому же модулю можно почленно перемножить, т.е. если и , то

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

Рассмотрим

Т.к. и , то по свойству отношения делимости , т.е. .

Следствие 1. Обе части сравнения можно умножить на одно и тоже целое число.

Следствие 2. Обе части сравнения можно возводить в одну и ту же натуральную степень.

4 . Обе части сравнения можно разделить на одно и то же число, взаимно простое с модулем, т.е. если и , то

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

По критерию имеем: , Т.к. , то по свойству взаимно простых чисел т. е. .

5 Обе части сравнения и модуль можно разделить на одно и то же число, т.е. если , то .

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

По критерию имеем: , . Следовательно, , или .

6 . Если два числа сравнимы по некоторому составному модулю, то они сравнимы по любому его делителю, т.е. если и , то .

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

По критерию имеем: и . Следовательно, по свойству отношения делимости .

7 . Обе части сравнения и модуль можно умножить на одно и тоже натуральное число: если и , то .

Полная и приведенная система вычетов.

Определение 1.4. Если из каждого класса вычетов взять по одному представителю, то полученная система чисел называется полной системой вычетов.

Существуют наиболее употребительные полные системы вычетов: полная система наименьших неотрицательных, наименьших по абсолютной величине вычетов и наименьших положительных вычетов.

Пример.

: {0, 1, 2, 3}- наименьшие неотрицательные; {-1, 0, 1, 2}- наименьшие по абсолютной величине; {1, 2, 3, 4}- наименьшие положительные.

Лемма 1.1. Совокупность чисел тогда и только тогда образует полную систему вычетов по модулю m, когда

1) числа попарно не сравнимы по модулю m;

2) количество чисел в системе равно m.

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

Необходимость непосредственно следует из определения.

Достаточность: Из 2) следует, что каждое из чисел принадлежит некоторому классу вычетов по модулю m и любые два числа принадлежат разным классам вычетов. Кроме того, всего в совокупности m чисел, т.е. столько и должно быть в полной системе вычетов.

Определение 1.5. Если из полной системы вычетов выбрать числа, взаимно простые с модулем m, то получим систему, которая называется приведенной системой вычетов.

Пример. и т.д.

По аналогии с леммой 1.1 легко проверить следующее утверждение.

Лемма 1.2. Совокупность чисел образует приведенную систему вычетов по модулю m тогда и только тогда, когда:

1) числа попарно не сравнимы по модулю m;

2) взаимно простые с модулем m;

3) количество чисел равно , где - функция Эйлера.

Определение 1.6. Количество натуральных чисел, не превосходящих и взаимно простых с называется функцией Эйлера и обозначается .

Пример. =10. Взаимно простые с 10 числа 1, 3, 7, 9. Значит =4.

Замечание. Поскольку (1, 1)=1, полагают =1.

Рассмотрим задачу о вычислении значений функции Эйлера.

Теорема 1.5. Если - простое число, - натуральное число, то .

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

Рассмотрим сначала случай . Ясно, что числа 1, 2, …, все взаимно простые с . Следовательно, = .

Пусть В ряду чисел 1, 2, …, , , …, не взаимно простыми с являются лишь числа, простые с , т.е. каждое Всего таких чисел будет = . Таким образом, .

Для того чтобы получить общую формулу для формулы Эйлера, докажем следующее ее важное свойство.

Теорема 1.6. Формула Эйлера мультипликативна, т.е. если , то .

Теперь мы можем сформулировать общую теорему о вычислении значений Эйлера.

Теорема 1.7. Пусть - каноническое разложение числа . Тогда .

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

Применяя теорему 1.5 и 1.6, получаем: .

Пример. 288= . Это значит, что .

Свойства полной и приведенной системы вычетов.

1 . Пусть . Если и принимает все значения полной системы вычетов по модулю , , …, , то и принимает все значения полной системы вычетов по модулю , , …, .

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

Воспользуемся леммой 1.1:

1) Покажем, что при .

Предположим противное, что . Тогда . По свойству 4 сравнений тогда .Получаем противоречие условию что принимает все значения полной системы вычетов. Следовательно, при .

2) Т.к. принимает значений, то тоже принимает значений.

По аналогии с предыдущим свойством для полной систему вычетов можно получить следующее утверждение.

2 . Пусть . Если и принимает все значения приведенной системы вычетов по модулю , , …, , то и принимает все значения полной системы вычетов по модулю , , …, .

Теорема 1.8 Эйлера. Если , то .

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

Пусть и принимает все значения приведенной системы вычетов , , …, по модулю . Тогда по свойству 2 также принимает все значения приведенной системы вычетов , , …, по тому же модулю . Поэтому и обязательно будут сравнимы между собой по модулю , т.е. , , …, .

По свойству 3 сравнений имеем , , …, , , …, . Т.к. , то по свойству взаимно простых чисел , , …, . Следовательно, по свойству 4 уравнений, тогда имеем .

Следствие (Теорема Ферма): Если p- просто число и , то или .

Решение сравнений.

Пусть дан многочлен , где .

Определение 1.7. Выражение вида (1.8) называется сравнение с одним неизвестным.

Решить сравнение - значит найти все такие целые числа , при которых сравнение справедливо. В качестве решения сравнения мы будем рассматривать весь класс вычетов по модулю , каждый представить которого удовлетворяет сравнению. Такие классы вычетов мы будем называть корнями сравнения.

Как и в случае алгебраических уравнений, скажем, что два сравнения равносильны, если множества их корней одинаковы.

Теорема 1.9. Если в сравнении (1.8) коэффициенты , заменить числами, сравнимыми с ними по , то полученное сравнение будет равносильно исходному.

Следствие. Если коэффициенты , делится на, то соответствующий член сравнения можно удалить и получить равносильное сравнение.

Данные свойства могут быть использованы для упрощения сравнений.

Пример. Сравнение равносильно сравнению .

Сравнения первой степени.

Сравнения первой степени мы будем записывать в виде

(*), где .

Исследуем вопрос о разрешимости сравнения (1.8) и нахождении его корней. Справедливо следующее утверждение.

Теорема 1.10. Если , то сравнение (1.8) имеет единственное решение.

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

Рассмотрим полную систему вычетов по модулю . Число принадлежит одному и только одному из классов вычетов по модулю и, следовательно для него найдется одно и только одно число

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

Теорема 1.11. Если и , то сравнение (1.8) решений не имеет.

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

В самом деле, сравнение (1.8) может быть переписано в виде

, , или , откуда, видно, что должно делиться на любой общий делитель и .

Теорема 1.12. Если и , то уравнение (1.8) имеет решений, которые могут быть найдены по формуле:

где и - единственное решение сравнения

, (**)

где , .

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

Из свойств 5 и 8 сравнений следует, что сравнения (*) и (**) равносильны.

В сравнении (**) имеем и поэтому, в силу теоремы 1.10, сравнение (**) имеет единственное решение - некоторый класс вычетов по модулю . Это означает, что числа вида

, , , …, (1.9)

удовлетворяют сравнениям (*), (**). Продолжать далее этот ряд не имеет смысла, так как следующее число = и, значит, это число попадает в класс и т.д.

Все числа вида (1.9), вообще говоря, принадлежат разным классам вычетов по модулю . Действительно, по теореме 1.4 необходимо, чтобы разность делилась на модуль . Рассмотрим разность кратных членов: . Очевидно, она не делится на .

Способы решения сравнений.

1) Способ испытаний.

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

Пример:

Так как , по теореме 1.10 сравнение имеет единственное решение {0, 1, 2, 3, 4, 5, 6, 7, 8}- полная система наименьших неотрицательных вычетов. , , …, не делится на 9, .

Ответ: .

2) Способ преобразования правой части.

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

Пример: ; . При t=2: 5 ; .

Ответ: .

3) Одним из самых эффективных является способ Эйлера.

По следствию 1 из свойства 3° сравнений имеем . Откуда по теореме 2.8 Эйлера .

Пример: ; .

, .

Ответ: .

4) Для того, чтобы применить способ цепных дробей разложим дробь в цепную: ]. Найдем все подходящие дроби. По свойству 2° подходящих дробей тогда имеем или .Отсюда . Согласно следствию 1 из свойства 3° сравнений тогда имеем . Таким образом, - решение сравнения.

Пример: ; .

Ответ: .

Применение сравнений первой степени к решению неопределенных уравнений.

В начале пункта 1.2 мы выяснили, что решение неопределенного уравнения (1.5) сводится в нахождению какого-нибудь частного решения при предположении, что .

Без ограничения общности будем считать Справедливо следующее утверждение.

Теорема 1.13. Если -решение уравнения (1.5), то - решение уравнения . Обратно, если - решение уравнения (! ), то найдется -решение уравнения (1.5).

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

Необходимость. Пусть -решение уравнения (1.5), т.е. . Тогда , т.е. и следовательно, . С другой стороны, т.е. , и следовательно .

Достаточность. Пусть , тогда , что можно записать как , т.е. .

Пример:

Ответ:

⇐ Предыдущая 1 234 5 6 7 8 9 10 Следующая ⇒