10037

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

Доклад

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

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

Русский

2013-03-20

44.5 KB

49 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

59055. Нетрадиційний урок: Що? Де? коли? 33.5 KB
  Оцінка історичної постаті і діяльності гетьмана Б.Хмельницького Очікувані результати: Закріпити знання учнів з даної теми; Оцінити історичну постать і діяльність гетьмана Б.Хмельницького; Виховувати почуття гордості до славного минулого нашого народу...
59056. Новорічний гороскоп 44.5 KB
  Звучить музика П. Чайковського з балету «Лускунчик». На сцену вибігають Зірочки й танцюють свій танець. У цей час виходить Звіздар у довгому халаті, ковпаку, окулярах.
59057. Мультисервісна мережу стадіону для надання послуг трансляціі відео потоків, IP-телефоніі, доступу до внутрішніх web-сервісів і доступу в інтернет 795.5 KB
  Мультисервісна мережа зможе поєднувати велику кількість пристроїв користувачів на всій території стадіону. Їх число може вимірятися десятками тисяч, які зможуть не тільки використовувати надані послуги, а й мати доступ до мережі інтернет, яка стала невід’ємною частиною життя
59058. Образ віку в ліриці ХХ століття 50 KB
  Література не задовольняючись формами романтизму і реалізму намагалася знайти нові форми зображення змін що відбувалися передусім у людській свідомості і разом зі світовим мистецтвом вийти на новий рівень творення художніх цінностей.
59059. Око як оптична система. Комбінований урок із біології, фізики та основ здоровя 77.5 KB
  На основі знань одержаних вами у 8-му класі на уроках фізики про світло про закони заломлення світла на межі двох прозорих середовищ про геометричну оптику ми ознайомимося з тим як наше око сприймає світло та колір пояснимо причини порушення зору...
59060. Олена Пчілка - світоч національних ідей 56.5 KB
  У таких складних навіть небезпечних історичних умовах розвивалась українська мова працювали та продовжували видавати свої чудові твори видатні українські поети та письменники серед яких була Олена Пчілка.
59061. Оповідання Р. Бредбері. Усмішка 60 KB
  Мета: розкрити вплив мистецтва Леонардо да Вінчі на творчість Р. Обладнання: репродукції картин Леонардо да Вінчі книги що розповідають про нього: Всеобщая история искусств Т. да Вінчі та Р. да Вінчі та його картину Джоконда .
59062. Трудове навчання. Осінні фантазії 34 KB
  Виховувати любов до природи та бережливе ставлення до неї Наочність та обладнання: репродукція картини Левітана Золота осінь грамзапис П. Чайковського Пори року відеозапис телевізор відеомагнітофон програвач казковий герой Осінь.
59063. Особливі, одиничні та суттєві ознаки. Корекційне заняття 4-й клас 38 KB
  Запитання озвучуються інші команди дають відповіді. Запрошення до зоопарку Капітан команди Євразія знайомить усіх дітей із кішкою рись. Капітан команди Африка знайомить усіх дітей із кішкою сервал яка проживає на Африканському континенті.