10037

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

Доклад

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

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

Русский

2013-03-20

44.5 KB

50 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

47673. Методические указания. Финансовый менеджмент 90.5 KB
  Целью изучения дисциплины является подготовка студентов к применению полученных знаний для рационального управления финансами предприятия. Задачами дисциплины являются: ознакомление с состоянием отечественного и мирового опыта организации управления финансами;...
47676. Оформление учебных текстовых документов. Методические указания 366 KB
  Единая система конструкторской документации. Общие требования к текстовым документам введен Построение документа Пояснения к записи ПРИЛОЖЕНИЕ А Пример оформления содержания ПРИЛОЖЕНИЕ Б Пример оформления текстовой части документа ПРИЛОЖЕНИЕ В Пример оформления таблиц ПРИЛОЖЕНИЕ Г Пример оформления рисунка ПРИЛОЖЕНИЕ Д Пример оформления формул ПРИЛОЖЕНИЕ Е Примеры оформления использованных источников 1 ОБЩИЕ СВЕДЕНИЯ 1.