10037

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

Доклад

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

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

Русский

2013-03-20

44.5 KB

50 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

26099. Философские и научные основания постижения культуры 13.42 KB
  Имеет смысл лишь в границах определенной культуры философские идеи свойством культурной уникальности и самобытности философ же пытается постичь его в прямой и непосредственной связи с человеческой субъективностью всегда культурно обусловленной Смотреть философскими глазами на мир значит смотреть на него как на мир культуры своей культуры видеть в нем отражение собственной исторически и общественно сформированной индивидуальности. Восприятие через призму культуры философия как знание о мире не выходит за культурный горизонт своей...
26100. Культура как система 20.17 KB
  Однако такое восприятие культуры утвердилось далеко не сразу. Начало системному рассмотрению культуры было положено Эдуардом Бернеттом Тайлором в работе Первобытная культура. На основе изучения большого этнографического материала автор описывает и анализирует конкретные элементы первобытной культуры на фоне культуры мировой и формулирует целостное видение культуры первобытности в контексте теории анимизма специфической веры первобытного человека в одушевленность всей природы которая связывала в единую целостность весь его практический...
26101. Методология, методы и методика исследования культуры 13.43 KB
  Методология система базовых мировоззренческих принципов исследования включающая методы методики способы и средства реализации поставленных целей и задач. Методология исследования культуры: Феноменологические Функционализм Структурализм Постструктурализм Системный Синергетический Постмодернизм Диалектический Семиотический Органицизм Диффузионизм Цивилизационный Аксиологический и др. Методология: Универсалистская Индивидуалистическая Конструктивистская Метод последовательность шагов действий которые необходимо...
26102. Основные подходы в изучении культуры 17.67 KB
  Ценности нормы и значения Предметные и организационные формы Главная функция Креативная творение бытия человеком или для человека Адаптация и воспроизводство жизненною уклада людей Латентность поддержание образца и социализация Воспроизводство и обновление самой деятельности Приоритетный метод исследования Диалектический Эволюционный Структурнофункциональный Системнодеятельностный Философский подход дает самую широкую панораму видения культуры предполагая изучение фундаментальных оснований человеческого бытия глубин самосознания...
26103. Проблема типологии культуры: основные принципы построения 17.54 KB
  Этническая культура совокупность черт культуры касающихся преимущественно обыденной жизни бытовой культуры. Этническая культура включает орудия труда нравы обычаи нормы обычного права ценности постройки одежду пищу средства передвижений жилище знания верования виды народного искусства. Национальная культура имеет соционормативную структуру которая обеспечивает координацию поведения и деятельности людей объединенных в рамках данной общности; предохраняет от распада и способствует адаптации членов общества к внешним и...
26104. Культура как способ самореализации человека 14.83 KB
  Человек выступает одновременно и как субъект культуры ее творец и как объект ее воздействия. Воспитание определенного типа личности главная цель в функционировании духовной культуры. В основе функционирования всей духовной культуры лежит деятельность по производству и воспроизводству духовных ценностей а также деятельность по овладению этими ценностями.
26105. Понятие затрат, издержек и расходов. Классификация затрат для принятия управленческих решений 48 KB
  Например: швейной фабрикой был закуплен материал на 100 тыс руб. Однако находится предприятие которое согласно купить изделия из этого материала за 300 тыс руб. при этом дополнительные затраты на изготовление этой продукции составят 260 тыс руб. целесообразно ли принимать заказ Затраты в сумме 100 тыс руб произведены и не будут изменяться в зависимости от выбранного варианта решения.
26106. Классификация затрат для исчисления себестоимости 29.5 KB
  1Прямые это те затраты которые экономически обосновано напрямую включаются в себестоимость отдельного вида продукции работ услуг. Материалы могут основными и вспомогательными прямые трудовые зарплата основных производственных рабочих 2Косвенные общепроизводственные расходы их нельзя напрямую отнести на готовою продукцию они распределяются между отдельными изделиями согласно выбранной на предприятии методики пропорционально базе распределения косвенных расходов Себестоимость продукции это выраженные в денежной форме...
26107. Понятие и объекты калькулирования 32.5 KB
  Задача калькулирования определить размер затрат приходящихся на единицу продукции. фактическая отчетная калькуляция отражает совокупность всех затрат на производство и реализацию продукции. Для рациональной организации учета издержек необходимо правильно выбрать метод учета затрат и калькулирования себестоимости продукции работ услуг. Под методом учета затрат и калькулирования себестоимость понимают совокупность документирования и отражения производственных затрат обеспечивающих определение фактической себестоимости продукции а т.