Сравнения n-ой степени по составному модулю

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:17, 14 мая 2016.

Основные определения и утверждения

, где - многочлен, не произвольная функция.

TemplateTheoremIcon.svg Теорема Утверждение
Если - попарно взаимно простые числа, , тогда

1

2 Количество решений:
Доказательство

Рассмотрим

1 Пусть решение (1) . Из свойств сравнений известно, что НОК, а так как все взаимно просты .

2 Если больше решений нет. Посчитаем иначе - как одно из решений (2). Тогда:


Согласно КТО эта система имеет решение выпишем его: , где зависит от также решение сравнения (1).

Посчитаем, сколько таких решений:

Допустим

Следовательно, наборы взяты из одного класса, а значит


Это утверждение позволяет свести к решению в случае . Далее этот случай сведем к .

TemplateExampleIcon.svg Пример Пример
Возьмем



Сведение решения сравнения по примарному модулю к простому

Научимся решать систему по примарному модулю

Можно свести к решению

Пусть решение это означает, что:

решение

Пусть найдено решение сравнения :

- решение , из определения сравнимости

Какие нужно взять , чтобы удовлетворять сравнению?

TemplateLemmaIcon.svg Лемма «Утверждение»
- разложение в ряд Тейлора


Определим

Если собрать коэффициенты при (после применения формулы бинома Ньютона к :

то получим то же значение, что и в случае производной в матанализе.

Перепишем функцию по-другому:

Очевидно, пришли к виду:

, и оно имеет решение, тогда

Возможны следующие варианты:

- проверим, будет ли это решение удовлетворять .

так как

Тогда

где . Получим, что



удовлетворяет (т.е. все удовлетворяют )