10037

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

Доклад

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

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

Русский

2013-03-20

44.5 KB

50 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

77789. Учет денежных средств в ОАО «Горецкая райагропромтехника» 192.53 KB
  Всевозможные расчеты возникающие между организациями осуществляются при помощи денежных средств в силу чего завершается превращение денежной формы выделенных средств в производственные запасы получение денежной выручки и заключенного в ней чистого дохода.
77790. ПРАВОВОЕ РЕГУЛИРОВАНИЕ ПОСТАВКИ ТОВАРОВ ДЛЯ ГОСУДАРСТВЕННЫХ НУЖД 158.95 KB
  Цели работы заключается в следующем: Определение и изучение процесса формирования заказов на поставку товаров для государственных нужд, Рассмотрение способов проведения процедуры размещения заказа на поставку государственных нужд...
77791. Деловая этика секретаря и руководителя 100.44 KB
  Этике деловых отношений уделяется в последнее время всё большее внимание. При отсутствии секретаря в рабочее время в дверь стучать не принято. В нерабочее время следует в дверь постучать; открыть ее можно только после того как услышали приглашение.
77792. РУЧНАЯ И МЕХАНИЗИРОВАННАЯ ДУГОВАЯ СВАРКА И НАПЛАВКА 9.11 MB
  В справочнике систематизированы материалы отражающие технологии дуговой сварки и наплавки металлов покрытым электродом в среде защитных газов плавящимся и неплавящимся электродом а также приведены основные сведения применительно к оборудованию...
77794. СОЗДАНИЕ БАЗЫ ДАННЫХ В MICROSOFT ACCESS 945.5 KB
  Реляционная база данных – база данных, которая позволяет определять отношения между различными категориями информации, например между данными о клиентах и данными о заказах. В результате имеется возможность совместного пользования данными.
77796. Изучение и составление математической модели идеального смесителя вещества и автоматического управления емкостью 1.92 MB
  Целью данной курсовой работы является изучение и составление математической модели идеального смесителя вещества и автоматического управления емкостью. В данном курсовом проекте представлена математическая модель идеального смесителя вещества и автоматического управления емкостью.