10037

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

Доклад

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

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

Русский

2013-03-20

44.5 KB

50 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

27795. Патронаж 36.5 KB
  Цель патронажа семей социальнопедагогическая адаптация и реабилитация детейинвалидов. Социальнопедагогический патронаж проводится по нескольким направлениям. Социальнопедагогическая адаптация детей с ограниченными возможностями здоровья.
27798. Характеристика семей «группы риска» 16.74 KB
  В зависимости от состава семьи от отношений в семье к членам семьи и вообще к окружающим людям человек смотрит на мир положительно или отрицательно формирует свои взгляды строит свои отношения с окружающими. Отношения в семье влияют на то как человек в дальнейшем будет строить свою карьеру по какому пути он пойдет. Именно в семье индивид получает первый жизненный опыт поэтому очень важно в какой семье воспитывается ребенок в благополучной или неблагополучной [26 с. Пристальный интерес к семье объясняется и рядом других обстоятельств:...
27799. КТД 133.94 KB
  Предполагает следующие этапы: принятие идеи выделение совета дела творческое коллективное выполнение коллективный анализ и оценка принятие идеи нового дела. Структура коллективнотворческого дела определяется шестью стадиями коллективного творчества. На этой стадии руководитель и сотрудники коллектива определяют конкретные задачи данного КТД намечают свои исходные направляющие действия необходимые для выполнения этих задач и приступают к таким действиям проводя нацеливающие воспитательные занятия с детьми беседы экскурсии готовят...
27800. Технологии профилактики наркомании и алкоголизма 20.21 KB
  Привлекают внимание информационные технологии профилактики наркомании и алкоголизма разработанные в г.Первый постулат профилактики наркомании заполнение информационного вакуума. Необходимо создать постоянно действующий и стабильно финансируемый конвейер публикаций и рекламы в СМИ по профилактике наркомании.
27801. СИСТЕМА РАБОТЫ С ОДАРЁННЫМИ ДЕТЬМИ В МОУ СОШ № 3 с. КИТАЕВСКОГО ВО ВНЕУРОЧНОЕ ВРЕМЯ 40.19 KB
  Вовлечение учащихся в систему дополнительного образования. Деятельность научного общества учащихся Олимп в которое входят предметные секции. Материальная поддержка талантливых и одарённых детей поездка в Москву на Всероссийский конкурс творческих работ учащихся посвящённый 75летию Д. Это позволяет увидеть оригинально мыслящих учащихся уделять внимание развитию их способностей.
27802. Работа учителей иностранного языка с одаренными детьми 181.5 KB
  Алексин Тульской области август 2010 года Слайд 2 В настоящее время одним из приоритетных направлений государственной политики в области образования является работа с одаренными детьми. Слайд 3 Наличие способных учащихся в школе реализация целевой программы Наша новая школа подчёркивают актуальность и необходимость программы развития одарённых детей. Слайд 4 Работа учителей иностранного языка с одаренными детьми В каждом классе есть учащиеся обладающие особыми способностями в изучении иностранных языков. Летний профильный лагерь...