10037

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

Доклад

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

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

Русский

2013-03-20

44.5 KB

50 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

17844. ИНСТРУМЕНТЫ ОРГАНИЗАЦИИ МЕЖБЮДЖЕТНЫХ ВЗАИМООТНОШЕНИЙ 66.5 KB
  Тема 10. ИНСТРУМЕНТЫ ОРГАНИЗАЦИИ МЕЖБЮДЖЕТНЫХ ВЗАИМООТНОШЕНИЙ План 1. Инструменты межбюджетных отношений 2. Межбюджетные отношения в зарубежных странах 3. Проблемы совершенствования межбюджетных отношений в Украине 1. Инструменты межбюджетных отношений М
17845. БЮДЖЕТНЫЕ ТРАНСФЕРТЫ 69.5 KB
  Тема 11. БЮДЖЕТНЫЕ ТРАНСФЕРТЫ План 1. Понятие бюджетных трансфертов и их правовое регулирование 2. Зарубежный опыт использования бюджетных трансфертов 3. Проблемы совершенствования системы трансфертов в Украине 1. Понятие бюджетных трансфертов и их правовое
17846. ЦЕЛИ И ЗАДАЧИ ГОСУДАРСТВЕННОЙ РЕГИОНАЛЬНОЙ ФИНАНСОВОЙ ПОЛИТИКИ 59.5 KB
  Тема 12. ЦЕЛИ И ЗАДАЧИ ГОСУДАРСТВЕННОЙ РЕГИОНАЛЬНОЙ ФИНАНСОВОЙ ПОЛИТИКИ 1. Понятие государственная региональная финансовая политика 2. Цели государственной региональной финансовой политики 3. Задача государственной региональной финансовой политики 4. Регио
17847. КОМПЕТЕНЦИЯ МЕСТНЫХ ОРГАНОВ ВЛАСТИ В ОБЛАСТИ ФИНАНСОВ 86.5 KB
  Тема 13. КОМПЕТЕНЦИЯ МЕСТНЫХ ОРГАНОВ ВЛАСТИ В ОБЛАСТИ ФИНАНСОВ План 1. Составление утверждение и выполнение местного бюджета 2. Бюджетный процесс 3. Образование внебюджетных целевых резервных и валютных фондов 4. Установление местных налогов и сборов Под ко...
17848. МЕСТНЫЕ ФИНАНСОВЫЕ ОРГАНЫ И ИХ ФУНКЦИИ 39 KB
  Тема 14. МЕСТНЫЕ ФИНАНСОВЫЕ ОРГАНЫ И ИХ ФУНКЦИИ План 1. Виды местных финансовых органов 2. Местные финансовые органы в зарубежных странах 1. Виды местных финансовых органов Управление местными финансами осуществляется местными представительными и исполнительн...
17849. ОРГАНИЗАЦИЯ КАССОВОГО ИСПОЛНЕНИЯ МЕСТНЫХ БЮДЖЕТОВ, КОНТРОЛЯ И АУДИТА В МЕСТНЫХ ОРГАНАХ ВЛАСТИ 67 KB
  Тема 15. ОРГАНИЗАЦИЯ КАССОВОГО ИСПОЛНЕНИЯ МЕСТНЫХ БЮДЖЕТОВ КОНТРОЛЯ И АУДИТА В МЕСТНЫХ ОРГАНАХ ВЛАСТИ План 1. Понятие и системы кассового исполнения местных бюджетов 2. Оборотная кассовая наличность 3. Кассовое исполнение местных бюджетов в зарубежных странах ...
17850. Совершенная конкуренция 7.08 MB
  Задача 4 Тема Совершенная конкуренция Исходные данные: Год рождения студента ГР = 1980 Месяц рождения студента МР = 4 День рождения студента ДР = 21 На рынке совершенной конкуренции отраслевой спро
17851. Монополия. Задача 1.98 MB
  Задача 5 Тема: Монополия Исходные данные: Год рождения студента ГР = 1999 Месяц рождения студента МР = 5 День рождения студента ДР = 23 Рыночная функция спроса имеет следующий вид: QD = ГР/3 05×МР×P = 666 25Р Фу
17852. Потребительский выбор 1.1 MB
  Задача 1 Тема Потребительский выбор Исходные данные: Год рождения студента: ГР = 1985 Месяц рождения студента: МР = 1 День рождения студента: ДР = 3 Функция полезности потребителя: TU = ГР × А × В =1985АВ Доход потребителя: I = ГР = 1985 Цена блага А: PА = 5 × ДР = ...