10037

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

Доклад

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

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

Русский

2013-03-20

44.5 KB

50 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

67478. ОСНОВЫ КВАЗИРЕЛЯТИВИСТСКОЙ КВАНТОВОЙ ТЕОРИИ. УРАВНЕНИЕ ДИРАКА 147.5 KB
  Первое слагаемое - вероятность найти частицу с положительной энергией, второе - с отрицательной энергией. Видим, что сохраняется только сумма этих вероятностей. Поэтому состояния с отрицательными энергиями нельзя просто выбросить - сразу нарушится вероятностная интерпретация.
67479. ВЗАИМОДЕЙСТВИЕ ЧАСТИЦ С ВНЕШНИМ ЭЛЕКТРОМАГНИТНЫМ ПОЛЕМ. УРАВНЕНИЕ ПАУЛИ 250 KB
  Вернемся к уравнению Клейна-Гордона - релятивистскому уравнению второго порядка, которому должна подчиняться любая волновая функция. Из него было ранее получено уравнение непрерывности
67480. ЭЛЕКТРОН В ЭЛЕКТРОСТАТИЧЕСКОМ ПОЛЕ 550.5 KB
  Имея полный гамильтониан, легко убедиться, что он коммутирует с При этом не входит в уравнение, а потому по проекции полного момента будет вырождение. Энергетические уровни будут характеризоваться собственными значениями трех первых операторов...
67481. НАУКА “РОБОТОТЕХНІКА”, ІСТОРІЯ РОЗВИТКУ ТА ОСТАННІ ДОСЯГНЕННЯ 236 KB
  Робототехніка і гнучкі виробничі системи є найважливішою технічною основою інтенсифікації виробництва. Це, з одного боку, дітище науково-технічного прогресу, а з іншою — його рушійна сила в розвитку сучасного промислового виробництва.
67482. Завдання, організація та актуальні питання медичної служби Збройних Сил України на воєнний час 148 KB
  Навчальна та виховна мета: розкрити найбільш складні та актуальні питання щодо ролі та місця у військовій медицині наукової дисципліни організації медичного забезпечення військ; ознайомити з організаційною структурою медичної служби ЗС України та її завданнями на воєнний час...
67483. ПОНЯТТЯ ТА СИСТЕМА ПРИРОДНОРЕСУРСОВОГО ПРАВА 145 KB
  Наукове значення природи полягає в безкінечній різноманітності об’єктів та процесів, які її складають і потребують вивчення. Іншими словами, природа є важливим джерелом наукових знань, основою для розвитку різноманітних галузей науки.
67484. РОБОТОТЕХНІЧНІ СИСТЕМИ (РТС), ЇХ СТРУКТУРА 337 KB
  Роботизований технологічний процес технологічний процес в якому в ролі основного технологічного устаткування використовуються промислові роботи і маніпулятори. З цією метою роботи доцільно сполучити з таким технологічним устаткуванням яке оснащене числовим програмним...
67485. Предприятие в условиях рыночной экономики 280 KB
  Цель моей работы рассмотреть и показать на примере, как предприятие функционирует в условиях рыночной экономики, какие виды и организационно-правовые формы предприятия существуют, какую роль играет ценообразование и какие методы планирования применяют предприятия.
67486. Экономика природопользования 353.5 KB
  Экономические механизмы природопользования Реализация экономических механизмов осуществляется через многие институты: кадастры своды экономических экологических организационных и технических показателей характеризующих количество и качество природного ресурса а также категории...