10037

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

Доклад

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

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

Русский

2013-03-20

44.5 KB

50 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

79714. ипы государства. Формационный подход к типологии государства. Исторические типы государства 77 KB
  Государство – это особая организация власти, располагающая специальным аппаратом управления и принуждения и способная придавать своим велениям обязательную силу для населения всей страны.
79715. Современный подход к определению факторов происхождения государства 58 KB
  Современный подход к определению факторов происхождения государства. ТЕОРИИ ПРОИСХОЖДЕНИЯ ГОСУДАРСТВА По вопросу о происхождении возникновения государства существуют самые разные теории. Наиболее распространенными являются теории происхождения государства приведенные в таблице ниже.
79716. Функции государства: понятие, классификация функций 96.5 KB
  Научное познание государства любого исторического типа обязательно предполагает рассмотрение его функций представляющих собой важнейшие качественные характеристики и ориентиры не только собственно государства как особой организации публичной власти но и общества в целом.
79717. Форма государства. Понятие формы государства. Элементы формы государства 155 KB
  При изучении темы «Формы государства» нужно проводить анализ и раскрыть формы, в которых функционирует государство и его политическая система, рассматривать происхождение структурно-территориальной организации общества любого государства.
79718. Механизм государства: понятие и структура. Орган государства: понятие, признаки, классификаци 140 KB
  Обобщая политический опыт развития эксплуататорских государств, можно определить государство как организацию для поддержания одних политических сил, стоящих у власти, над другими. Без механизма государства нет и самого государства
79719. Гражданское общество: основные этапы становления и сфера деятельности 62 KB
  Идея гражданского общества появилась в Новое время, в противовес всевластию государства. Концепцию гражданского общества в наиболее полном виде разработал Г. Гегель, немецкий философ.
79720. Понятие демократии. Предпосылки демократии. Институты прямой демократии 80.5 KB
  Критериями демократического общества в эту эпоху были: Возможность принятия главных решений всему свободными гражданами полиса большинством голосов; Занятие должностей по жребию; Периодические отчеты должностных лиц. Этому способствуют: открытые для прессы заседания коллегиальных государственных органов публикация их стенографических отчетов представление чиновниками деклараций о своих доходах существование свободных от цензуры и независимых от власти неправительственных СМИ; Выборность основных органов власти на основе всеобщего...
79721. Зарождение и развитие идеи правового государства 52 KB
  Признаки правового государства. К концу XX века человечество приблизилось к реальному воплощению выработанной веками идеи правового государства. У ее истоков стояли древние философы Платон и Аристотель но наиболее полное отражение концепция правового государства получили в работах Ш.
79722. Понятие гражданства и подданства. Категории физических лиц по их отношению к гражданству, их правовой статус 79 KB
  Гражданство - устойчивая правовая связь человека с государством, выражающаяся в совокупности их взаимных прав, обязанностей и ответственности, основанная на признании и уважении достоинства, основных прав и свобод человека.