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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:09, 14 мая 2016.
TemplateTheoremIcon.svg Теорема Утверждение
Всякое сравнение вида по простому модулю равносильно сравнению степени не выше
Доказательство

Разделим многочлен

Кольцо многочленов - Евклидово кольцо, в нем выполняется теорема о делении с остатком. Знаем, что выполняется, по следствию из теоремы Ферма:

(т.е. переходим от высоких степеней к относительно невысоким, бит).


TemplateLemmaIcon.svg Лемма «Утверждение»
Если корень , то имеет место тождественное сравнение:


TemplateLemmaIcon.svg Лемма «Утверждение»
Разделим с остатком на :


TemplateExampleIcon.svg Пример Следствие 1

различные корни.


TemplateExampleIcon.svg Пример Следствие 2
Если имеет несравнимых между собой корней, то имеет место тождественное сравнение:


TemplateTheoremIcon.svg Теорема Утверждение
Сравнение степени может иметь не сравнимых между собой решений.
Доказательство

Пусть корней всего . Тогда подставим в сравнение :

НЕ корень. Это утверждение верно для


TemplateExampleIcon.svg Пример Пример
Если , решений может быть больше, чем степень


TemplateLemmaIcon.svg Лемма «Утверждение»
имеет n решений все коэффициенты остатка от деления на кратны .