10037

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

Доклад

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

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

Русский

2013-03-20

44.5 KB

49 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

5629. Система налогообложения для сельскохозяйственных товаропроизводителей (единый сельскохозяйственный налог - ЕСХН) 30 KB
  Система налогообложения для сельскохозяйственных товаропроизводителей (единый сельскохозяйственный налог - ЕСХН) Сельскохозяйственные товаропроизводители - это организации и индивидуальные предприниматели, производящие сельскохозяйственную...
5630. Ответственность за нарушение налогового законодательства. Административная и уголовная ответственность в налоговой сфере 78.5 KB
  Ответственность за нарушение налогового законодательства Понятие налоговой ответственности. Составы налоговых правонарушений. Ответственность в соответствии с НК РФ. Административная и уголовная ответственность в налоговой...
5631. Налоговый контроль. Камеральная и выездная налоговые проверки 76 KB
  Налоговый контроль Понятие и виды налогового контроля. Камеральная и выездная налоговые проверки. Порядок оформления результатов проверок. Административная и судебная защита прав налогоплательщиков. Налоговый контроль
5632. Федеральная налоговая служба. Государственные органы как участники отношений в налоговой сфере 76.5 KB
  Государственные органы как участники отношений в налоговой сфере Федеральная налоговая служба. Таможенные органы. Федеральная служба по борьбе с налоговыми и экономическими преступлениями. Другие участники отношений в налогов...
5633. Налоговое производство. Порядок исчисления и уплаты налога 75 KB
  Налоговое производство Понятие налогового производства. Бухгалтерский и налоговый учет при исчислении налога. Порядок исчисления налога. Порядок уплаты налога. Юридической обязанностью налогоплательщика является уплата нал...
5634. Система налогов. Направления развития системы налогообложения в РФ 76 KB
  Система налогов Направления развития системы налогообложения в РФ. Перечень налогов, взимаемых на территории РФ. Общие сведения о налогах. Реформирование налоговой системы - это ее преобразование, исходя из направлений...
5635. Основы российской налоговой системы. Принципы налогообложения 68 KB
  Основы российской налоговой системы Понятие налоговой системы и налоговой политики. Принципы налогообложения в РФ. Система налогового законодательства. Бюджетный процесс и налогообложение. Основные характеристики налого...
5636. Дискретная математика. Теория вероятностей и математическая статистика 1.01 MB
  Учебно-методическое пособие разработано по дисциплине Математика и содержит краткий теоретический материал и упражнения по двум разделам дисциплины: дискретная математика, теория вероятностей и математическая статистика. Для организации самостоятель...
5637. Изучение и расчет конструкции дробилок 2.65 MB
  Введение Увеличивающиеся из года в год объемы промышленного, гидротехнического, жилищного, дорожного и других видов строительства требуют огромного количества нерудных строительных материалов (щебня, гравия, песка), идущих на изготовление железобето...