10037

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

Доклад

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

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

Русский

2013-03-20

44.5 KB

49 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

80041. Край, у якому ти живеш. Україна – наша Батьківщина 417.5 KB
  Мета: збагачувати знання учнів про Україну, а також активний словниковий запас учнів; пробудити інтерес до вивчання рідного краю; розширити знання народні, історичні та культурні символи українського народу; сприяти формування національної свідомості, осмисленню себе як частини...
80042. Н.В.Гоголь и Т.Г.Шевченко: две судьбы, две личности, два пути великих сыновей украинского народа 134.5 KB
  В своих исследованиях, представленных на конференции по заявленной теме, учащиеся проследили, как среда и время определили разницу в судьбах и литературных путях двух великих украинцев Н.Гоголя и Т.Шевченко. Прилагается электронная презентация темы в формате Pover Point.
80043. Декоративна таця 473 KB
  Необхідність таці люди зрозуміли дуже давно, саме тому її почали використовувати як столове приладдя вже в стародавні часи. Перші таці були зроблені не з каменя, як можна було припустити, а з обпаленої глини, оскільки їм не була потрібна міцність. Представляла вона собою напівкулю.
80044. ПІДПРИЄМЛИВІСТЬ – ОСНОВА КОНКУРЕНТНОСПРОМОЖНОСТІ ВИПУСКНИКА 211.5 KB
  З учнями: діагностика: Виявлення характерних рис дитини Виявлення нахилів і здібностей школярів Виявлення спрямованості учнів 811 класів; анкетування: Мої успіхи і невдачі Формування життєвої компетентності особистості Настрій і його зображення Розуміння почуттів іншої людини...
80045. Громадянське виховання як метод правової соціалізації учнів 74 KB
  Виховання адаптованої людини, тобто людини, здатної пристосуватися до вимог суспільства. Прищеплення дітям з раннього віку національних цінностей: патріотизм, людяність, працелюбство, соціальна справедливість, правосвідомість.
80046. Я И МИР ПРОФЕССИЙ 62.5 KB
  Формирование у школьников представлений о мире профессий и о факторах, обуславливающих рациональный выбор профессии; активизация учащихся в профессиональном самоопределении; познакомить учащихся с учебными заведениями города...
80048. Все работы хороши. Защита профессий 58 KB
  Подготовительная работа: Игре предшествуют беседы с родителями экскурсии к ним на работу выпуск газеты Наши родители на работе с фотографиями рисунками краткой информацией о том что они делают чем занимаются на работе какое значение имеет их работа для них самих и для других людей.