10037

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

Доклад

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

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

Русский

2013-03-20

44.5 KB

50 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

36939. Обмін даними з додатками 702 KB
  Щоб прочитати цей файл в Mthcd необхідно: В меню Insert Вставка виберіть команду Сomponent Компонент зявиться діалогове вікно Сomponent Wizrd рис. Рис. Зявиться діалогове вікно File Options рис. Рис.
36941. Ознайомитись з програмною моделлю 32 розрядних процесорів Intel та оволодіти навиками створення програм, використовуючи 32 розрядний асемблер 122.49 KB
  model flt stdcll option csemp: none ; оголошення службових процедур макросів змінних констант include msm32 include windows.inc include msm32 include kernel32.inc include msm32 include msm32.inc include msm32 include debug.
36942. Оволодіти навиками створення програм, частини яких написані різними мовами програмування. Засвоїти правила взаємодії різних модулів 169.07 KB
  Звичайно доступ наприклад до двох параметрів переданих через стек здійснюється в такий спосіб: PUSH EBP MOV EBPESP MOV EX[EBP8] MOV EDX[EBP12] . POP EBP RET Деякі версії мови C розрізняють великі і малі букви тому ім'я асемблерного модуля повинне бути представлено в тому ж символьному регістрі який використовують для посилання Cпрограми.code _clc proc push ebp mov ebpesp mov ex[ebp16] shr ex01 mov ebx[ebp8] shl ebx02 sub ebxex sub ebx[ebp12] sub ebx[ebp8] mov ex[ebp20] dd exebx pop ebp ret _clc endp END ...
36943. Робота з масивами в СКМ Mathcad 24.73 KB
  Дано дві матриці А та В.7150 Транспонувати матриці А В С.1600 Знайти найменший елемент 3го стовпчику матриці С.1600 Вивести стовбець матриці С який містить максимальний елемент у виді окремого вектору.
36944. Побудова вибіркової функції розподілу засобами комп’ютерних технологій 363.5 KB
  Лабораторна робота №2 Тема: побудова вибіркової функції розподілу засобами компютерних технологій. У MthCD існують дві функції що дозволяють зробити обробку вибірки для наступної побудови гістограм. Оскільки методика створення гістограм з використанням функції hist досить складна надамо її по пунктах: Для початку представимо експериментальні дані у вигляді вектора.
36945. Розрахувати найбільшу похибку відлікового пристрою і встановити раціональну точність виготовлення елементів багатооборотного індикатора 543.84 KB
  1 Функції перетворення синусного механізму: Для кулісного механізму Передаточне відношення від веденої ланкистрілки до кінцевої ланки кулісного механізму Вихідна функція з кулісного механізму враховуючи що вихід синусного є входом кулісного.
36946. Обладнання та драйвери. Використання Device Manager та System Information 316.54 KB
  Вивести властивості пристрою 1. Вивести список драйверів що забезпечують роботу даного пристрою відобразити у звіті рис. Імітуючи несправність пристрою неправильно підєднаний шлейф SCSIпристрою запустити програму Troubleshooter Діагностика 1. Також я знайшов IRQ ресурси певних пристроїв та визначив які драйвера потрібні для роботи дискового пристрою відображені на рис2.
36947. Використання вбудованих функцій MathCAD, MS Exсel для обчислення характеристик вибірки 61.5 KB
  Для обчислення числових характеристик вибірки що утримується в масиві Х розмірності m×n в MthCD призначені наступні функції: mxХ для пошуку найбільшого елемента в масиві даних; minХ пошук мінімального елемента в масиві даних; sortХ побудова варіаційного ряду тобто сортування вихідних даних по зростанню; menХ обчислення вибіркового середнього по масиву даних: vrХ для визначення вибіркової дисперсії; stdevХ для обчислення середньоквадратичного відхилення; medin для розрахунку значення медіани ...