Изложение теоретического материала иллюстрируется большим количеством примеров с подробными решениями
 Скачать 1.34 Mb.
|
3.2 Сравнения видаРассмотрим сравнение с одной переменной вида
где , , коэффициенты при старшем члене и не делятся на m. Определение 1. Решением сравнения (3.3) называется класс вычетов по modm, состоящий из чисел, удовлетворяющих этому сравнению. Теорема 1. Пусть и многочлены с целыми коэффициентами и целое число удовлетворяет сравнению (3.3). Тогда весь класс вычетов (modm) состоит из чисел, удовлетворяющих этому сравнению. Доказательство. 1) Так как число удовлетворяет сравнению (3.3), то оно удовлетворяет сравнению , где . 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). Доказательство. Пусть класс вычетов но модулю решение сравнения (3.6), то есть для сравнение
является верным сравнением, следовательно, сравнение
где , тоже верно. Поэтому класс вычетов по модулю является решением сравнения
Обратное также верно: если решение сравнения (3.9), то для , будет верно сравнение (3.8), а, следовательно, верно сравнение (3.7), поэтому является решением сравнения (3.6). Таким образом, сравнения (3.6) и (3.9) эквивалентны. Пусть класс вычетов по – решение сравнения (3.6), тогда для , получим верное сравнение . Возьмем целое число , взаимно простое с модулем: . Умножим последнее сравнение почленно на , получим верное сравнение:
отсюда получим, что класс вычетов по модулю решение сравнения
Обратно, если класс вычетов по модулю решение сравнения (3.11), то для верно сравнение (3.10), следовательно, будет верно и сравнение: (заметим, что , так как , в противном случае было бы: ). Поэтому класс вычетов по модулю решение сравнения (3.6). Таким образом, сравнения (3.6) и (3.11), где , будут эквивалентными. Пусть класс вычетов по модулю решение сравнения (3.6), тогда для верно сравнение , а, значит, верно и сравнение
для любого натурального числа , поэтому класс вычетов по модулю решение сравнения
Обратно, если класс вычетов по модулю решение сравнения (3.13), то для верно сравнение (3.12), но тогда по свойству сравнений верно сравнение: , поэтому класс вычетов по модулю решение сравнения (3.6). Следовательно, сравнения (3.6) и (3.13) эквивалентны. Теорема доказана. В дальнейшем сравнение (3.6) можно заменить эквивалентным сравнением:
где Теорема 1 доказана. Теорема 2. Пусть даны сравнения Тогда сравнения эквивалентны. Доказательство. Умножим почленно верные сравнения на некоторое целое число:
Сложим почленно полученные сравнения, тогда получим сравнение: отсюда получим, что . Но тогда и . Следовательно, сравнения и эквивалентны. Теорема 2 доказана. Заметим, из доказанной теоремы, в частности, следует, что сравнение заменится эквивалентным, если отбросить (или добавить) слагаемое с коэффициентами, делящимися на модуль. |