10037

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

Доклад

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

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

Русский

2013-03-20

44.5 KB

50 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

74949. Заміна одних одиниць вимірювання величин іншими. Розв’язування задач на дві дії та складання обернених задач 129.5 KB
  Заміна одних одиниць вимірювання величин іншими. Формувати вміння використовувати набуті знання для заміни одних одиниць вимірювання величин іншими. Познайомити учнів зі старовинними одиницями вимірювання довжини і маси.
74950. Розв’язування задач на знаходження швидкості, часу та відстані 92 KB
  Мета: Ознайомити учнів зі способами визначення відстані, швидкості та часу; за допомогою пилки» формувати вміння розв’язувати задачі на основі творчих видів роботи; розвивати обчислюванні навички.
74951. Повторення вивченого «Нумерація чисел від 21 до 100» 45 KB
  Кожен герой мультика приготував для вас своє завдання. Увага відгадайте герої якого мультфільму пропонують вам перше завдання звучить пісня Ю. Щоб нікого не образити ми виконаємо і те і те завдання. Фрагмент пісні з Бременських музикантів готові малюнки кожної тварини яка буде пропонувати завдання.
74952. Розв’язування задач на зведення до одиниці. Вправи на засвоєння таблиці множення числа 8. Розпізнання многокутників 32.5 KB
  Удосконалювати вміння учнів розвязувати задачі на зведення до одиниці; домогтися засвоєння таблиці множення числа 8 напамять; закріплювати знання правил порядку дій; розвивати обчислювальні навички та вміння розвязувати рівняння...
74953. Письменное вычитание трёхзначных чисел. Сложные задачи – цена, количество, стоимость. Геометрический материал 188.5 KB
  Цель: Учить детей письменному вычитанию трехзначных чисел столбиком; закрепить умение делать правильный мотивированный выбор действия в задаче; выбирать арифметическое действие для решения задачи; составлять равенства на умножение деление; классифицировать и обобщать.
74954. Усвоение таблицы умножения и деления. Составление задачи по выражению 56 KB
  Цель. Совершенствовать умение решать выражения на основе знаний таблицы умножения и деления; развивать умение решать уравнения на нахождение неизвестного делителя; закреплять умение составлять и решать задачи по выражению, задачи на приведение к единице...
74955. Повторение табличного деления и умножения чисел 58.5 KB
  Цели и задачи: Образовательные: усвоение полученных знаний, умений и навыков при табличном делении и умножении; Развивающие: развивать наблюдательность и умение рассуждать; развивать математические способности, логическое мышление, внимание и интерес к предмету через игру...
74956. Додавання й віднімання виду 430 + 500, 430 + 50, 760 – 400, 760 – 40. Розширена задача на спосіб зведення до одиниці. Складена задача, яка включає суму двох або трьох доданків 54 KB
  Мета. Закріплювати вміння учнів додавати круглі трицифрові числа різними способами. Працювати над розв’язуванням задач. Розкриватимемо таємниці єгипетських пірамід. Розвивати обчислювальні навички, логічне мислення, пам’ять.