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

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

TemplateDifinitionIcon.svg Определение «Определение»

TemplateTheoremIcon.svg Теорема Утверждение 1
имеет решение НОД. Если это выполняется, то имеется решений, гдеНОД. Все решения имеют вид:
Доказательство

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

Пусть существует решение :

делит каждое из слагаемых

Достаточночть


Нашли некоторое решение, сложность нахождения не выше сложности алгоритма Евклида.

Способы нахождения решений сравнений

Решение с помощью алгоритма Евклида

Пусть решения.

Тогда получаем все эквивалентные решения.

Важно в

НОД

Решение с помощью теоремы Эйлера

- решение

Решение с помощью цепных дробей

Одна из атак на равенство Шамира-Адельмана использует цепные дроби. Цепные дроби используются используются для описания линейных рекурсивных последовательностей.

,

где целое, - натуральные.

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


TemplateExampleIcon.svg Пример Пример


Решение с помощью подходящих дробей

Понятие подходящих дробей

TemplateDifinitionIcon.svg Определение «Определение - Подходящие дроби»
. Дроби вида называются подходящими дробями.

Свойства подходящих дробей

1. Рекуррента второго порядка

2. из

3.

4.

Решение уравнения . Рассмотрим

TemplateExampleIcon.svg Пример Пример

НОД

Итого: