Теоремы об эквивалентных сравнениях
Теорема 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). Таким образом, сравнения (3.6) и (3.11), где , будут эквивалентными. 3) Пусть класс вычетов по модулю решение сравнения (3.6), тогда для верно сравнение , а, значит, верно и сравнение 4)
для любого натурального числа , поэтому класс вычетов по модулю решение сравнения
Обратно, если класс вычетов по модулю решение сравнения (3.13), то для верно сравнение (3.12), но тогда по свойству сравнений верно сравнение: , поэтому класс вычетов по модулю решение сравнения (3.6). Следовательно, сравнения (3.6) и (3.13) эквивалентны. Теорема доказана. В дальнейшем сравнение (3.6) можно заменить эквивалентным сравнением:
где Теорема 1 доказана. Теорема 2. Пусть даны сравнения Тогда сравнения эквивалентны. Доказательство. Умножим почленно верные сравнения на некоторое целое число:
Сложим почленно полученные сравнения, тогда получим сравнение:
отсюда получим, что . Но тогда и . Следовательно, сравнения и эквивалентны. Теорема 2 доказана. Заметим, из доказанной теоремы, в частности, следует, что сравнение заменится эквивалентным, если отбросить (или добавить) слагаемое с коэффициентами, делящимися на модуль.
Популярное: Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... Почему стероиды повышают давление?: Основных причин три... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (255)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |