10037

Алгоритм решения сравнения. Китайская теорема об остатках

Доклад

Информатика, кибернетика и программирование

Сравнения вида могут иметь несколько решений иметь единственное решение или не иметь решений вовсе. Если то решение единственно: Теорема. Решения сравнения существуют тогда и только тогда когда делит . При этом количество решений сравнения равно d. Алгорит...

Русский

2013-03-20

44.5 KB

50 чел.

Сравнения вида могут иметь несколько решений, иметь единственное решение или не иметь решений вовсе. Если , то решение единственно: .

Теорема. Решения сравнения  существуют тогда и только тогда, когда делит . При этом количество решений сравнения равно d.

Алгоритм решения сравнения .

1. Если   не делит , то решений нет, иначе – существует d решений.

2.Если решение существует, то от исходного сравнения переходим к сравнению вида с единственным решением (поскольку коэффициент при х взаимно прост с модулем).

3. Все решения исходного сравнения в диапазоне  являются числами вида , .

Китайская теорема об остатках.

Следующее утверждение называется китайской теоремой об остатках.

Пусть числа попарно взаимно просты и . Тогда существует единственное по модулю решение системы сравнений , .

При этом, , где , .

Действительно, в указанном выражении для одно слагаемое сравнимо с по модулю , а все прочие сравнимы с нулем.

Очевидно, что коэффициенты можно вычислить заранее и решать несколько систем, подставляя их правые части в выражение для х.

Китайская теорема об остатках показывает, что решение сравнения  можно найти, если знать решения этого сравнения по модулям, равным степеням простых, входящих в каноническое разложения числа на сомножители.


 

А также другие работы, которые могут Вас заинтересовать

6162. Осциллографические измерения 320.5 KB
  Осциллографические измерения 1. Электронно-лучевой осциллограф Электронно-лучевой осциллограф (от латинского слова осциллум - колебание и греческого графо - пишу) или осциллоскоп (греч. скопео - вижу) - прибор, предназначен...
6163. Робота з симулятором машини Ноймана. Дослідження виконання машинного коду в автоматичному режимі 170.61 KB
  Мета: опанувати роботу на симуляторі машини Ноймана, зрозуміти і дослідити принцип виконання програми машиною Ноймана. Завдання: запустити симулятор, увести до нього коди машинних інструкцій і коди чисел, навчитися утворювати і змінювати ці ко...
6164. Редактор логических схем алгоритмовАвтоматизация проектирования компьютерных систем 125.74 KB
  Автоматизация проектирования компьютерных систем Краткое описание программы Интерфейс пользователя: Пользователь может выполнить одно из следующих действий: Открыть существующий файл для просмотра и дальнейшего редактирования алгоритма. ...
6165. Маркетинговые исследования рынка шоколадных батончиков 224.41 KB
  Маркетинговые исследования рынка шоколадных батончиков Введение Рынок шоколадных батончиков достаточно привлекателен, является одним из самых значительных сегментов  национальной экономики, а также  принадлежит к высокодоходным отраслям. Следствием ...
6166. Естетично-екологічне виховання у дошкільних навчальних закладах 268.5 KB
  Екологічна криза, що виникла через непродумане господарювання людини, змушує змінити своє ставлення до довкілля. Цій меті покликана служити система екологічного виховання, яка є окремим напрямом педагогічної теорії та практики.
6167. Принципи конфігурування коммутатора Cisco Catalyst 2960 610.5 KB
  Мета роботи: Вивчити принципи конфігурування коммутатора CiscoCatalyst 2960. Порядок виконання роботи Виконання даної лабораторної роботи, складається з двох частин: Підготовки на емуляторі Packet Tracerv 4 Робота на ко...
6169. Бази даних XML 130 KB
  Бази даних XML Завдання Вивчити відповідні розділи документації СУБД. Навести власні приклади використання конструкцій мови доступу до СУБД. Підготувати звіт у вигляді файлу з прикладами та його друкованого варіанту. Створення ...
6170. НАГНЕТАТЕЛЬНАЯ ФУНКЦИЯ СЕРДЦА. ФАЗОВЫЙ АНАЛИЗ СЕРДЕЧНОГО ЦИКЛА. ЯВЛЕНИЯ, СОПРОВОЖДАЮЩИЕ РАБОТУ СЕРДЦА 164.23 KB
  Нагнетательная функция сердца. Роль клапанного аппарата в ее реализации. Закон Франка-Старлинга (закон «сердца»). Причины наполнения сердца кровью. Фазовый анализ сердечного цикла. Звуковые и механические явления, сопровождающие работу сердца (тоны сердца, верхушечный толчок), их диагностическое значение.