10037

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

Доклад

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

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

Русский

2013-03-20

44.5 KB

49 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

21899. Аварии на гидротехнических сооружениях 540 KB
  Масштабы последствий гидродинамических аварий зависят от параметров и технического состояния гидроузла характера и степени разрушения плотины объемов запасов воды в водохранилище характеристик волны прорыва и катастрофического наводнения рельефа местности сезона и времени суток происшествия и многих других факторов. 160 227 СаяноШушенская 47 120 Красноярская 68 986 Основными поражающими факторами затопления при аварии на ГТС являются: волна прорыва высота волны скорость движения и длительность затопления. Начало волны называется...
21900. Современные техногенные опасности мирного и военного времени 324.5 KB
  Определение степени и масштабов разрушений при производственных авариях и авариях на транспорте связанных с взрывами взрывчатых веществ. Именно в ХХ столетии происходило: интенсивное развитие малоотходной ядерной энергетики; бурное развитие химической промышленности; стремительное освоение космического пространства; появление новых видов современного оружия: ОМП ядерное термоядерное нейтронное химическое биологическое геофизическое оружие; современные средства поражения ССП зажигательные кассетные боеприпасы боеприпасы объемного...
21901. ЖИЗНЕОБЕСПЕЧЕНИЕ НАСЕЛЕНИЯ В ЧРЕЗВЫЧАЙНЫХ СИТУАЦИЯХ 40 KB
  ЖОН в ЧС совокупность согласованных и взаимосвязанных по цели задачам месту и времени действий территориальных и ведомственных органов управления сил средств и соответствующих служб направленных на создание условий необходимых для сохранения жизни и поддержания здоровья людей в зоне ЧС на маршрутах эвакуации и в местах отселения пострадавшего населения. Первоочередные виды ЖОН в ЧС жизненно важные материальные средства и услуги сгруппированные по функциональному предназначению и сходным свойствам используемые...
21902. ХАРАКТЕРИСТИКА ЧС ПРИРОДНОГО ХАРАКТЕРА 676.5 KB
  Землетрясения Землетрясения это подземные толчки и колебания земной поверхности возникающие в основном в результате внезапных смещений и разрывов в земной коре или верхней мантии и передающиеся на большие расстояния. Колебания земной поверхности при землетрясениях носят волновой характер. Сейсмическая опасность при землетрясениях определяется не только колебаниями грунта но и возможными вторичными факторами к которым следует отнести лавины оползни обвалы опускание просадку и перекосы земной поверхности разрушение грунта...
21903. Номенклатура и разграфка топографических карт 164.5 KB
  Общегеографические карты делятся на три вида: обзорные масштаб 1:I 000000 и мельче; обзорнотопографические масштаб 1:100000 1:1000000; топографические масштаб 1:100000 и крупнее. Обзорнотопографические карты составляются по картам более крупных масштабов. Топографические карты составляются по результатам съемок территорий и отличаются детальностью изображения местности. Это многолистные карты т.
21904. Атрибутивное описание. Векторная модель. Топологическая модель 121 KB
  Атрибутивное описание Одних координатных данных недостаточно для описания картографической или сложной графической информации. Атрибуты соответствующие тематической форме данных и определяющие различные признаки объектов также хранятся в таблицах. Применение атрибутов позволяет осуществлять анализ объектов базы данных с использованием стандартных форм запросов и разного рода фильтров а также выражений математической логики. Кроме того с помощью атрибутов можно типизировать данные и упорядочивать описание для широкого набора некоординатных...
21905. Растровая модель. Оверлейные структуры. Трехмерные модели 158 KB
  Трехмерные модели. При этом каждой ячейке растровой модели соответствует одинаковый по размерам но разный по характеристикам цвет плотность участок поверхности объекта. В ячейке модели содержится одно значение усредняющее характеристику участка поверхности объекта. В растровых моделях в качестве атомарной модели используют двухмерный элемент пространства пиксель ячейка.
21906. Введение в дистанционное зондирование. Восстановление (коррекция) видеоинформации. Предварительная обработка изображений. Классификация. Преобразование изображений 145.5 KB
  К настоящему времени накоплен огромный фонд более 100 миллионов аэрокосмических снимков полностью покрывающих всю поверхность Земли а для значительной части районов с многократным перекрытием. Геометрическая коррекция или трансформирование снимков предназначено для устранения искажений вызванных кривизной и вращением Земли а также углом наклона орбиты спутника к плоскости экватора. Часто для представления и совместной обработки материалов разных видов типов съемок а также разновременных снимков одной и той же территории используется...
21907. Отраслевые геоинформационные проекты 139.5 KB
  Создание карт распределения геологической продукции и информации: а по административным районам; б по геологическим структурам. Создание двумерных и трехмерных моделей подсчета запасов полезных ископаемых и карт в изолиниях. Персональные компьютеры в руках геолога представляют собой надежный инструмент который дает большие возможности как по созданию геологических отчетов геологических карт научных разработок так и по решению различных модельных задач по теории рудообразования геотектонике стратиграфии металлогении и т.