10037

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

Доклад

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

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

Русский

2013-03-20

44.5 KB

50 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

12015. Формирования депозитной политики коммерческого банка на примере Сибирского отделения Сбербанка ОАО 1.17 MB
  Содержание Введение 1. Теоретические основы формирования депозитной политики коммерческого банка Содержание принципы и функции депозитной политики коммерческого банка Классификация депозитных операций коммерческих банков Методы и инструменты
12016. Определение перспектив кассовых операций коммерческих банков 679.87 KB
  ОГЛАВЛЕНИЕ ВВЕДЕНИЕ 1 Содержание и структура кассовых операций банкоВ 2 Правила приема выдачи и пересчета наличных денег использование электронных кассиров 2.1 Правила приема выдачи и пересчета наличных денег 2.2 Использование электронных кассиров 3 Эффе
12017. Изучение основ формирования банковской системы США 80.35 KB
  Содержание ВВЕДЕНИЕ 1. История развития банковской системы США 2. Современная структура банковской системы США 2.1 Банковские учреждения США 2.2 Органы регулирования и надзора за деятельностью банков и других финансовых институтов в США 2.3 Совершенствование ...
12018. ІНВЕСТИЦІЙНА ДІЯЛЬНІСТЬ КОМЕРЦІЙНОГО БАНКУ ТА ЇЇ ВПЛИВ НА ЙОГО ФІНАНСОВИЙ СТАН 505.38 KB
  ДИПЛОМНА РОБОТА за освітньокваліфікаційним рівнем Бакалавр ІНВЕСТИЦІЙНА ДІЯЛЬНІСТЬ КОМЕРЦІЙНОГО БАНКУ ТА ЇЇ ВПЛИВ НА ЙОГО ФІНАНСОВИЙ СТАН Зміст ВСТУП РОЗДІЛ 1. ІНВЕСТИЦІЙНА ДІЯЛЬНІСТЬ КОМЕРЦІЙНИХ БАНКІВ ЯК ДЖЕРЕЛО ЙОГО ФІНАНСОВОЇ СТІЙКОСТІ І ПРИБУТКО...
12020. Финансовое состояние кредитной организации - ОАО КБ «Спутник» 560 KB
  Содержание Введение 1. Теоретические основы оценки финансового состояния кредитной организации 1.1 Сущность оценки финансового состояния кредитной организации 1.2 Методы оценки финансового состояния кредитной организации 1.3 Экономическая эффективность деятел...
12021. Финансовые аспекты деятельности Фонда социального страхования РФ (на примере Воронежского регионального отделения Фонда) 116.87 KB
  2 ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА НА ТЕМУ: Финансовые аспекты деятельности Фонда социального страхования РФ на примере Воронежского регионального отделения Фонда СОДЕРЖАНИЕ Введение 1 Теоретические основы финансов Фонда социального стр
12022. Основы банковского дела 786.5 KB
  Т.М. Иванова Основы банковского дела Учебно-методический комплекс Челябинск Содержание Методические указания 3 Тема 1. История возникновения и развития банков