Китайская теорема об остатках - Википедия - Chinese remainder theorem

Оригинальная формулировка Сунь-цзы: Икс ≡ 2 (мод 3) ≡ 3 (мод 5) ≡ 2 (мод 7) с решением Икс = 23 + 105k, куда k ∈ ℤ

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

Самое раннее известное утверждение теоремы было сделано китайским математиком Сунь-цзы в Сунь-цзы Суань-цзин в 3 веке нашей эры.

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

Китайская теорема об остатках (выраженная в терминах совпадения ) верно для всех главная идеальная область. Он был обобщен на любой коммутативное кольцо, с формулировкой, включающей идеалы.

История

Самое раннее известное утверждение теоремы как проблема с конкретными числами появляется в книге 3-го века. Сунь-цзы Суань-цзин китайским математиком Сунь-цзы:^[1]

Есть вещи, количество которых неизвестно. Если мы посчитаем их по три, у нас останется два; к пятеркам у нас остается три; а к семеркам осталось два. Сколько там всего?^[2]

Работа Сунь-цзы не содержит ни доказательства, ни полного алгоритма.^[3] Что представляет собой алгоритм решения этой проблемы был описан Арьябхата (6 век).^[4] Частные случаи китайской теоремы об остатках были также известны Брахмагупта (7 век), и появляются в Фибоначчи с Liber Abaci (1202).^[5] Позже результат был обобщен в виде полного решения, названного Та-янь-шу (大衍術) в Цинь Чиу-шао 1247 год Математический трактат в девяти разделах (數書九章, Шу-шу Чиу-чанг)^[6] который был переведен на английский язык в начале 19 века британским миссионером Александр Вайли.^[7]

Китайская теорема об остатках появляется в Гаусс книга 1801 года Disquisitiones Arithmeticae.^[8]

Понятие конгруэнции было впервые введено и использовалось Гаусс в его Disquisitiones Arithmeticae 1801 г.^[9] Гаусс иллюстрирует китайскую теорему об остатках в задаче, связанной с календарями, а именно: «найти годы, которые имеют определенный номер периода по отношению к солнечному и лунному циклам и по римскому указанию».^[10] Гаусс вводит процедуру решения проблемы, которая уже использовалась Эйлер но на самом деле это был древний метод, который появлялся несколько раз.^[11]

Заявление

Позволять п₁, ..., п_k быть целыми числами больше 1, которые часто называют модули или же делители. Обозначим через N продукт п_я.

Китайская теорема об остатках утверждает, что если п_я находятся попарно взаимно просты, и если а₁, ..., а_k - целые числа такие, что 0 ≤ а_я < п_я для каждого я, то есть одно и только одно целое число Икс, такое что 0 ≤ Икс < N а остальная часть Евклидово деление из Икс к п_я является а_я для каждого я.

Это можно переформулировать следующим образом: совпадения: Если п_я попарно взаимно просты, а если а₁, ..., а_k любые целые числа, то существуют целые числа Икс такой, что

{ Displaystyle { begin {выровненный} х & экви а_ {1} { pmod {n_ {1}}} & , , , vdots х & экви а_ {к} { pmod { п_ {к}}}, конец {выровнено}}}

и любые два решения, скажем Икс₁ и Икс₂, конгруэнтны по модулю N, то есть, $Икс 1 \equiv Икс 2 (мод N)$ .^[12]

В абстрактная алгебра, теорема часто переформулируется так: если бы п_я попарно взаимно просты, отображение

{ Displaystyle х { bmod {N}} ; mapsto ; (x { bmod {n}} _ {1}, , ldots, , x { bmod {n}} _ {k} )}

определяет изоморфизм колец^[13]

{ Displaystyle mathbb {Z} / N mathbb {Z} cong mathbb {Z} / n_ {1} mathbb {Z} times cdots times mathbb {Z} / n_ {k} mathbb {Z}}

между звенеть из целые числа по модулю N и прямой продукт колец целых чисел по модулю п_я. Это означает, что для выполнения последовательности арифметических операций в ${ Displaystyle mathbb {Z} / N mathbb {Z},}$ одно и то же вычисление можно производить независимо в каждом ${ Displaystyle mathbb {Z} / n_ {i} mathbb {Z}}$ а затем получить результат, применив изоморфизм (справа налево). Это может быть намного быстрее, чем прямое вычисление, если N и количество операций большое. Это широко используется под названием многомодульные вычисления, за линейная алгебра над целыми числами или рациональное число.

Теорема также может быть переформулирована на языке комбинаторика как факт, что бесконечное арифметические прогрессии целых чисел образуют Семья Хелли.^[14]

Доказательство

Существование и единственность решения можно доказать независимо. Однако первое доказательство существования, данное ниже, использует эту уникальность.

Уникальность

Предположим, что $Икс$ и $у$ оба решения всех сравнений. В качестве $Икс$ и $у$ дают тот же остаток при делении на $п я$ , их отличие $Икс - у$ кратно каждому $п я$ . Поскольку $п я$ попарно взаимно просты, их произведение $N$ разделяет также $Икс - у$ , и поэтому $Икс$ и $у$ конгруэнтны по модулю $N$ . Если $Икс$ и $у$ должны быть неотрицательными и меньше $N$ (как в первом утверждении теоремы), то их разность может быть кратной $N$ только если $Икс = у$ .

Существование (первое доказательство)

Карта

{ Displaystyle х { bmod {N}} mapsto (х { bmod {n}} _ {1}, ldots, x { bmod {n}} _ {k})}

отображает классы сравнения по модулю $N$ последовательностям классов конгруэнтности по модулю $п я$ . Доказательство единственности показывает, что это отображение инъективный. Поскольку домен и codomain этой карты имеют одинаковое количество элементов, карта также сюръективный, что доказывает существование решения.

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

Существование (конструктивное доказательство)

Существование может быть установлено явным построением $Икс$ .^[15] Эту конструкцию можно разбить на два этапа: во-первых, решая задачу в случае двух модулей, а во-вторых, распространяя это решение на общий случай с помощью индукция от количества модулей.

Случай двух модулей

Мы хотим решить систему:

{ Displaystyle { begin {выровнено} x & Equiv a_ {1} { pmod {n_ {1}}} x & Equiv a_ {2} { pmod {n_ {2}}}, end {выровнено }}}

куда ${ displaystyle n_ {1}}$ и ${ displaystyle n_ {2}}$ взаимно просты.

Личность Безу утверждает существование двух целых чисел ${ displaystyle m_ {1}}$ и ${ displaystyle m_ {2}}$ такой, что

{ displaystyle m_ {1} n_ {1} + m_ {2} n_ {2} = 1.}

Целые числа ${ displaystyle m_ {1}}$ и ${ displaystyle m_ {2}}$ может быть вычислен расширенный алгоритм Евклида.

Решение дается

{ displaystyle x = a_ {1} m_ {2} n_ {2} + a_ {2} m_ {1} n_ {1}.}

В самом деле,

{ displaystyle { begin {align} x & = a_ {1} m_ {2} n_ {2} + a_ {2} m_ {1} n_ {1} & = a_ {1} (1-m_ {1 } n_ {1}) + a_ {2} m_ {1} n_ {1} & = a_ {1} + (a_ {2} -a_ {1}) m_ {1} n_ {1}, end {выровнено}}}

подразумевая, что ${ displaystyle x Equiv a_ {1} { pmod {n_ {1}}}.}$ Второе сравнение доказывается аналогично, заменой индексов 1 и 2.

Общий случай

Рассмотрим последовательность уравнений сравнения:

{ Displaystyle { begin {выровненный} х & экви а_ {1} { pmod {n_ {1}}} & vdots х & экви а_ {k} { pmod {n_ {k}}} , конец {выровнено}}}

где ${ displaystyle n_ {i}}$ попарно взаимно просты. Два первых уравнения имеют решение ${ displaystyle a_ {1,2}}$ предоставляется методом из предыдущего раздела. Набор решений этих двух первых уравнений - это совокупность всех решений уравнения

{ Displaystyle x Equiv a_ {1,2} { pmod {n_ {1} n_ {2}}}.}

Как и другие ${ displaystyle n_ {i}}$ взаимно просты с ${ displaystyle n_ {1} n_ {2},}$ это уменьшает решение исходной проблемы $k$ уравнения к аналогичной задаче с ${ displaystyle k-1}$ уравнения. Итерируя этот процесс, в конечном итоге можно получить решение исходной проблемы.

Существование (прямое построение)

Для построения решения нет необходимости проводить индукцию по количеству модулей. Однако такое прямое построение требует большего количества вычислений с большими числами, что делает его менее эффективным и менее используемым. Тем не менее, Интерполяция Лагранжа является частным случаем этой конструкции, применяемой к многочленам вместо целых чисел.

Позволять ${ displaystyle N_ {i} = N / n_ {i}}$ быть произведением всех модулей, кроме одного. Поскольку ${ displaystyle n_ {i}}$ попарно взаимно просты, ${ displaystyle N_ {i}}$ и ${ displaystyle n_ {i}}$ взаимно просты. Таким образом Личность Безу применяется, и существуют целые числа ${ displaystyle M_ {i}}$ и ${ displaystyle m_ {i}}$ такой, что

{ displaystyle M_ {i} N_ {i} + m_ {i} n_ {i} = 1.}

Решение системы сравнений есть

{ displaystyle x = sum _ {i = 1} ^ {k} a_ {i} M_ {i} N_ {i}.}

Фактически, как ${ displaystyle N_ {j}}$ кратно ${ displaystyle n_ {i}}$ за ${ Displaystyle я neq j,}$ у нас есть

{ Displaystyle х эквив а_ {я} М_ {я} N_ {я} эквив а_ {я} (1-м_ {я} п_ {я}) эквив а_ {я} { pmod {п_ {я} }},}

для каждого ${ displaystyle i.}$

Вычисление

Рассмотрим систему сравнений:

{ Displaystyle { begin {выровненный} х & экви а_ {1} { pmod {n_ {1}}} & vdots х & экви а_ {k} { pmod {n_ {k}}} , конец {выровнено}}}

где ${ displaystyle n_ {i}}$ попарно совмещать, и разреши ${ displaystyle N = n_ {1} n_ {2} cdots n_ {k}.}$ В этом разделе описаны несколько методов вычисления уникального решения для ${ displaystyle x}$ , так что ${ Displaystyle 0 Leq х$ и эти методы применяются на примере:

{ displaystyle { begin {align} x & Equiv 0 { pmod {3}} x & Equiv 3 { pmod {4}} x & Equiv 4 { pmod {5}}. end { выровнено}}}

Систематический поиск

Легко проверить, имеет ли значение $Икс$ является решением: достаточно вычислить остаток от Евклидово деление из $Икс$ каждым $п я$ . Таким образом, чтобы найти решение, достаточно последовательно проверить целые числа из $0$ к $N$ пока не найду решение.

Хотя этот метод очень простой, он очень неэффективен. Для простого примера, рассматриваемого здесь, $40$ целые числа (включая $0$ ) должны быть проверены для нахождения решения, которое $39$ . Это экспоненциальное время алгоритма, так как размер входных данных с точностью до постоянного множителя, количество цифр $N$ , а среднее количество операций порядка $N$ .

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

Поиск по просеиванию

Поиск решения может быть значительно ускорен за счет просеивания. Для этого метода мы без ограничения общности предполагаем, что ${ displaystyle 0 leq a_ {i}$ (если бы это было не так, достаточно было бы заменить каждый ${ displaystyle a_ {i}}$ на остаток от деления на ${ displaystyle n_ {i}}$ ). Это означает, что решение принадлежит арифметическая прогрессия

{ displaystyle a_ {1}, a_ {1} + n_ {1}, a_ {1} + 2n_ {1}, ldots}

Проверяя значения этих чисел по модулю ${ displaystyle n_ {2},}$ в конце концов можно найти решение ${ displaystyle x_ {2}}$ двух первых сравнений. Тогда решение принадлежит арифметической прогрессии

{ displaystyle x_ {2}, x_ {2} + n_ {1} n_ {2}, x_ {2} + 2n_ {1} n_ {2}, ldots}

Проверка значений этих чисел по модулю ${ displaystyle n_ {3},}$ , и продолжение до тех пор, пока каждый модуль не будет проверен, дает в конечном итоге решение.

Этот метод работает быстрее, если модули упорядочены по убыванию значения, то есть если ${ displaystyle n_ {1}> n_ {2}> cdots> n_ {k}.}$ Для примера это дает следующее вычисление. Сначала мы рассмотрим числа, которые сравнимы с 4 по модулю 5 (наибольший модуль), а именно 4, 9 = 4 + 5, 14 = 9 + 5, ... Для каждого из них вычислите остаток по 4 (второй по величине модуль), пока не получите число, конгруэнтное 3 по модулю 4. Затем можно продолжить, добавив 20 = 5×4 на каждом шаге и вычисляя только остатки по 3. Это дает

4 mod 4 → 0. Продолжить

4 + 5 = 9 по модулю 4 → 1. Продолжать

9 + 5 = 14 мод 4 → 2. Продолжить

14 + 5 = 19 по модулю 4 → 3. Хорошо, продолжаем, рассматривая остатки по модулю 3 и добавляя каждый раз 5 × 4 = 20.

19 мод 3 → 1. Продолжить

19 + 20 = 39 mod 3 → 0. Хорошо, вот результат.

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

Использование конструкции существования

В конструктивное доказательство существования показывает, что в случай двух модулей, решение может быть получено вычислением Коэффициенты Безу модулей, за которыми следуют несколько умножений, сложений и редукций по модулю ${ displaystyle n_ {1} n_ {2}}$ (для получения результата в интервале ${ displaystyle (0, n_ {1} n_ {2} -1)}$ ). Поскольку коэффициенты Безу могут быть вычислены с помощью расширенный алгоритм Евклида, все вычисление, самое большее, имеет квадратичный временная сложность из ${ displaystyle O ((s_ {1} + s_ {2}) ^ {2}),}$ куда ${ displaystyle s_ {i}}$ обозначает количество цифр ${ displaystyle n_ {i}.}$

Для более чем двух модулей метод для двух модулей позволяет заменять любые два сравнения на одно сравнение по модулю произведения модулей. Повторение этого процесса в конечном итоге приводит к решению, сложность которого квадратична по количеству цифр произведения всех модулей. Эта квадратичная временная сложность не зависит от порядка, в котором модули перегруппированы. Можно перегруппировать два первых модуля, затем перегруппировать полученный модуль со следующим и так далее. Эту стратегию проще всего реализовать, но она также требует большего количества вычислений с большими числами.

Другая стратегия состоит в разделении модулей на пары, чьи произведения имеют сравнимые размеры (насколько это возможно), параллельном применении метода двух модулей к каждой паре и повторении с количеством модулей, приблизительно разделенных на два. Этот метод позволяет легко распараллелить алгоритм. Также, если быстрые алгоритмы (то есть алгоритмы, работающие в квазилинейное время ) используются для основных операций, этот метод обеспечивает алгоритм для всего вычисления, работающий в квазилинейном времени.

В текущем примере (в котором всего три модуля) обе стратегии идентичны и работают следующим образом.

Личность Безу для 3 и 4 это

{ Displaystyle 1 раз 4 + (- 1) раз 3 = 1.}

Помещение этого в формулу для доказательства существования дает

{ Displaystyle 0 раз 1 раз 4 + 3 раз (-1) раз 3 = -9}

для решения двух первых сравнений, остальные решения получаются добавлением к −9 любого кратного 3×4 = 12. Можно продолжить любое из этих решений, но решение 3 = −9 +12 меньше (по абсолютной величине) и, вероятно, приводит к более легкому вычислению

Тождество Безу для 5 и 3 × 4 = 12 имеет вид

{ Displaystyle 5 раз 5 + (- 2) раз 12 = 1.}

Применяя еще раз ту же формулу, мы получаем решение проблемы:

{ displaystyle 25 times 3-24 times 4 = -21.}

Остальные решения получаются сложением любых кратных 3×4×5 = 60, а наименьшее положительное решение −21 + 60 = 39.

Как линейная диофантова система

Система сравнений, решаемая китайской теоремой об остатках, может быть переписана как система одновременных линейных диофантовых уравнений:

{ displaystyle { begin {align} x & = a_ {1} + x_ {1} n_ {1} & vdots x & = a_ {k} + x_ {k} n_ {k}, end { выровнен}}}

где неизвестные целые числа ${ displaystyle x}$ и ${ displaystyle x_ {i}.}$ Следовательно, любой общий метод решения таких систем может быть использован для нахождения решения китайской теоремы об остатках, например, приведение матрицы системы к Нормальная форма Смита или же Нормальная форма Эрмита. Однако, как обычно при использовании общего алгоритма для более конкретной проблемы, этот подход менее эффективен, чем метод предыдущего раздела, основанный на прямом использовании Личность Безу.

По основным идеальным областям

В § Формулировка теоремы китайская теорема об остатке была сформулирована тремя различными способами: в терминах остатков, сравнений и изоморфизма колец. Заявление об остатках не применяется, как правило, к области главных идеалов, так как остатки в таких кольцах не определены. Однако две другие версии имеют смысл для основной идеальной области. $р$ : достаточно заменить «целое число» на «элемент домена» и ${ Displaystyle mathbb {Z}}$ к $р$ . Эти две версии теоремы верны в данном контексте, потому что доказательства (за исключением первого доказательства существования) основаны на Лемма евклида и Личность Безу, которые верны для каждого основного домена.

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

Над кольцами одномерных многочленов и евклидовыми областями

Отчет об остатках, приведенный в § Формулировка теоремы не может быть обобщен на любую область основных идеалов, но его обобщение на Евклидовы области просто. В одномерные многочлены через поле является типичным примером евклидовой области, которая не является целыми числами. Поэтому сформулируем теорему для случая кольца одномерной области ${ Displaystyle R = К [X]}$ над полем ${ displaystyle K.}$ Чтобы получить теорему для общей евклидовой области, достаточно заменить степень на Евклидова функция евклидовой области.

Китайская теорема об остатках для многочленов такова: Пусть ${ displaystyle P_ {i} (X)}$ (модули) быть, при $я =1, ..., k$ , попарно взаимно просты многочлены от ${ Displaystyle R = К [X]}$ . Позволять ${ displaystyle d_ {i} = deg P_ {i}}$ быть степенью ${ displaystyle P_ {i} (X)}$ , и ${ displaystyle D}$ быть суммой ${ displaystyle d_ {i}.}$ Если ${ Displaystyle A_ {я} (X), ldots, A_ {k} (X)}$ - многочлены такие, что ${ displaystyle A_ {i} (X) = 0}$ или же ${ displaystyle deg A_ {i}$ для каждого $я$ , то существует один и только один многочлен ${ Displaystyle P (X)}$ , так что ${ Displaystyle deg P$ а остальная часть Евклидово деление из ${ Displaystyle P (X)}$ к ${ displaystyle P_ {i} (X)}$ является ${ displaystyle A_ {i} (X)}$ для каждого $я$ .

Построение решения может быть выполнено как в § Существование (конструктивное доказательство) или же § Существование (прямое доказательство). Однако последнюю конструкцию можно упростить, используя следующее: частичное разложение на фракции вместо расширенный алгоритм Евклида.

Таким образом, мы хотим найти многочлен ${ Displaystyle P (X)}$ , которая удовлетворяет сравнениям

{ Displaystyle P (X) Equiv A_ {i} (X) { pmod {P_ {i} (X)}},}

за ${ Displaystyle я = 1, ldots, к.}$

Рассмотрим многочлены

{ Displaystyle { begin {align} Q (X) & = prod _ {i = 1} ^ {k} P_ {i} (X) Q_ {i} (X) & = { frac {Q (X)} {P_ {i} (X)}}. End {выравнивается}}}

Разложение на частичную дробь ${ Displaystyle 1 / Q (X)}$ дает $k$ многочлены ${ Displaystyle S_ {я} (Х)}$ со степенями ${ displaystyle deg S_ {i} (X)$ такой, что

{ displaystyle { frac {1} {Q (X)}} = sum _ {i = 1} ^ {k} { frac {S_ {i} (X)} {P_ {i} (X)} },}

и поэтому

{ displaystyle 1 = sum _ {i = 1} ^ {k} S_ {i} (X) Q_ {i} (X).}

Тогда решение системы одновременных сравнений дается полиномом

{ displaystyle sum _ {i = 1} ^ {k} A_ {i} (X) S_ {i} (X) Q_ {i} (X).}

Фактически у нас есть

{ displaystyle sum _ {i = 1} ^ {k} A_ {i} (X) S_ {i} (X) Q_ {i} (X) = A_ {i} (X) + sum _ {j = 1} ^ {k} (A_ {j} (X) -A_ {i} (X)) S_ {j} (X) Q_ {j} (X) Equiv A_ {i} (X) { pmod {P_ {i} (X)}},}

за ${ Displaystyle 1 Leq я Leq к.}$

Это решение может иметь степень больше, чем ${ displaystyle D = sum _ {i = 1} ^ {k} d_ {i}.}$ Уникальное решение степени менее ${ displaystyle D}$ можно вывести, рассматривая остаток ${ displaystyle B_ {i} (X)}$ евклидова деления ${ Displaystyle А_ {я} (Х) S_ {я} (Х)}$ к ${ displaystyle P_ {i} (X).}$ Это решение

{ Displaystyle P (X) = sum _ {i = 1} ^ {k} B_ {i} (X) Q_ {i} (X).}

Интерполяция Лагранжа

Частным случаем китайской теоремы об остатках для многочленов является Интерполяция Лагранжа. Для этого рассмотрим $k$ монические полиномы первой степени:

{ displaystyle P_ {i} (X) = X-x_ {i}.}

Они попарно взаимно просты, если ${ displaystyle x_ {i}}$ все разные. Остаток от деления на ${ displaystyle P_ {i} (X)}$ полинома ${ Displaystyle P (X)}$ является ${ displaystyle P (x_ {i}).}$

Теперь позвольте ${ Displaystyle A_ {1}, ldots, A_ {k}}$ - константы (многочлены степени 0) в ${ displaystyle K.}$ И интерполяция Лагранжа, и китайская теорема об остатках утверждают существование единственного многочлена ${ Displaystyle P (X),}$ степени меньше чем ${ displaystyle k}$ такой, что

{ Displaystyle P (x_ {i}) = A_ {i},}

для каждого ${ displaystyle i.}$

Формула интерполяции Лагранжа в данном случае является результатом описанного выше построения решения. Точнее, пусть

{ Displaystyle { begin {align} Q (X) & = prod _ {i = 1} ^ {k} (X-x_ {i}) [6pt] Q_ {i} (X) & = { frac {Q (X)} {X-x_ {i}}}. end {align}}}

В частичное разложение на фракции из ${ displaystyle { frac {1} {Q (X)}}}$ является

{ displaystyle { frac {1} {Q (X)}} = sum _ {i = 1} ^ {k} { frac {1} {Q_ {i} (x_ {i}) (X-X_ {я})}}.}

Фактически, приведя правую часть к общему знаменателю, мы получим

{ displaystyle sum _ {i = 1} ^ {k} { frac {1} {Q_ {i} (x_ {i}) (X-X_ {i})}} = { frac {1} { Q (X)}} sum _ {i = 1} ^ {k} { frac {Q_ {i} (X)} {Q_ {i} (x_ {i})}},}

а числитель равен единице, как многочлен степени меньше ${ displaystyle k,}$ который принимает значение один для ${ displaystyle k}$ разные значения ${ displaystyle X.}$

Используя приведенную выше общую формулу, мы получаем формулу интерполяции Лагранжа:

{ displaystyle P (X) = sum _ {i = 1} ^ {k} A_ {i} { frac {Q_ {i} (X)} {Q_ {i} (x_ {i})}}. }

Эрмита интерполяция

Эрмита интерполяция является приложением китайской теоремы об остатках для одномерных многочленов, которое может включать модули произвольных степеней (интерполяция Лагранжа включает только модули первой степени).

Задача состоит в том, чтобы найти многочлен наименьшей возможной степени, такой, что многочлен и его первые производные принимают заданные значения в некоторых фиксированных точках.

Точнее, пусть ${ displaystyle x_ {1}, ldots, x_ {k}}$ быть ${ displaystyle k}$ элементы земли поле ${ displaystyle K,}$ и для ${ Displaystyle я = 1, ldots, k,}$ позволять ${ displaystyle a_ {i, 0}, a_ {i, 1}, ldots, a_ {i, r_ {i} -1}}$ быть значениями первого ${ displaystyle r_ {i}}$ производные искомого полинома при ${ displaystyle x_ {i}}$ (включая 0-ю производную, которая является значением самого полинома). Проблема состоит в том, чтобы найти многочлен ${ Displaystyle P (X)}$ так что его j-я производная принимает значение ${ displaystyle a_ {i, j}}$ в ${ displaystyle x_ {i},}$ за ${ Displaystyle я = 1, ldots, к}$ и ${ displaystyle j = 0, ldots, r_ {j}.}$

Рассмотрим многочлен

{ displaystyle P_ {i} (X) = sum _ {j = 0} ^ {r_ {i} -1} { frac {a_ {i, j}} {j!}} (X-x_ {i }) ^ {j}.}

Это многочлен Тейлора порядка ${ displaystyle r_ {i} -1}$ в ${ displaystyle x_ {i}}$ , неизвестного полинома ${ Displaystyle P (X).}$ Следовательно, мы должны иметь

{ Displaystyle P (X) Equiv P_ {i} (X) { pmod {(X-x_ {i}) ^ {r_ {i}}}}.}

Наоборот, любой многочлен ${ Displaystyle P (X)}$ что удовлетворяет эти ${ displaystyle k}$ сравнения, в частности, проверяет, для любых ${ Displaystyle я = 1, ldots, к}$

{ Displaystyle P (X) = P_ {i} (X) + o (X-x_ {i}) ^ {r_ {i} -1}}

следовательно ${ displaystyle P_ {i} (X)}$ - его многочлен Тейлора порядка ${ displaystyle r_ {i} -1}$ в ${ displaystyle x_ {i}}$ , то есть, ${ Displaystyle P (X)}$ решает исходную задачу интерполяции Эрмита. Китайская теорема об остатках утверждает, что существует ровно один многочлен степени меньше, чем сумма ${ displaystyle r_ {i},}$ что удовлетворяет этим ${ displaystyle k}$ конгруэнции.

Есть несколько способов вычисления решения ${ Displaystyle P (X).}$ Можно использовать метод, описанный в начале § Над одномерными кольцами многочленов и евклидовыми областями. Также можно использовать конструкции, приведенные в § Существование (конструктивное доказательство) или же § Существование (прямое доказательство).

Обобщение на непростые модули

Китайская теорема об остатках может быть обобщена на непростые модули. Позволять ${ displaystyle m, n, a, b}$ быть любыми целыми числами, пусть ${ Displaystyle г = НОД (т, п)}$ , и рассмотрим систему сравнений:

{ Displaystyle { begin {выровнено} х & эквив а { pmod {m}} х & эквив б { pmod {n}}, конец {выровнено}}}

Если ${ Displaystyle а эквив б { pmod {г}}}$ , то эта система уравнений имеет единственное решение по модулю ${ displaystyle operatorname {lcm} (m, n) = mn / g}$ . В противном случае у нее нет решений.

Если мы используем Личность Безу написать ${ displaystyle g = um + vn}$ , то решение

{ displaystyle x = { frac {avn + bum} {g}}.}

Это определяет целое число, как $грамм$ разделяет оба $м$ и $п$ . В остальном доказательство очень похоже на доказательство для взаимно простых модулей.

Обобщение на произвольные кольца

Китайскую теорему об остатках можно обобщить на любые звенеть, используя взаимно простые идеалы (также называемый минимальные идеалы ). Два идеала $я$ и $J$ взаимно просты, если есть элементы ${ displaystyle i in I}$ и ${ displaystyle j in J}$ такой, что ${ displaystyle i + j = 1.}$ Это отношение играет роль Личность Безу в доказательствах, связанных с этим обобщением, которые в остальном очень похожи. Обобщение можно сформулировать следующим образом.^[16]

Позволять $я 1, ..., я k$ быть двусторонние идеалы кольца ${ displaystyle R}$ и разреши $я$ быть их пересечением. Если идеалы попарно взаимно просты, имеем изоморфизм:

{ displaystyle { begin {align} R / I & to R / I_ {1} times cdots times R / I_ {k} x { bmod {I}} & mapsto (x { bmod {I}} _ {1}, , ldots, , x { bmod {I}} _ {k}), end {выравнивается}}}

между кольцо частного ${ displaystyle R / I}$ и прямой продукт из ${ displaystyle R / I_ {i},}$ куда " ${ Displaystyle х { bmod {I}}}$ "обозначает изображение элемента ${ displaystyle x}$ в фактор-кольце, определяемом идеалом ${ displaystyle I.}$ Более того, если ${ displaystyle R}$ является коммутативный, то идеальное пересечение попарно взаимно простых идеалов равно их товар; то есть

{ displaystyle I = I_ {1} cap I_ {2} cap cdots cap I_ {k} = I_ {1} I_ {2} cdots I_ {k},}

если $я я$ и $я j$ взаимно просты для $я \neq j$ .

Приложения

Нумерация последовательностей

Китайская теорема об остатках была использована для построения Гёделевская нумерация последовательностей, который участвует в доказательстве Теоремы Гёделя о неполноте.

Быстрое преобразование Фурье

В алгоритм БПФ с простым коэффициентом (также называемый алгоритмом Гуда-Томаса) использует китайскую теорему об остатках для сокращения вычислений быстрое преобразование Фурье размера ${ displaystyle n_ {1} n_ {2}}$ к вычислению двух быстрых преобразований Фурье меньшего размера ${ displaystyle n_ {1}}$ и ${ displaystyle n_ {2}}$ (при условии что ${ displaystyle n_ {1}}$ и ${ displaystyle n_ {2}}$ взаимно просты).

Шифрование

Наиболее реализации RSA используют китайскую теорему об остатках во время подписания HTTPS сертификаты и при расшифровке.

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

Разрешение неоднозначности диапазона

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

Теорема Дедекинда

Теорема Дедекинда о линейной независимости характеров. Позволять $M$ быть моноид и $k$ ан область целостности, рассматриваемого как моноид, если рассматривать умножение на $k$ . Тогда любое конечное семейство $(ж я) я \in я$ различных гомоморфизмов моноидов $ж я : M \to k$ линейно независима. Другими словами, каждая семья $(α я) я \in я$ элементов $α я \in k$ удовлетворение

{ displaystyle sum _ {я in I} alpha _ {i} f_ {i} = 0}

должен быть равен семье $(0) я \in я$ .

Доказательство. Сначала предположим, что $k$ является полем, иначе заменим область целостности $k$ по его полю частного, и ничего не изменится. Мы можем линейно продолжить гомоморфизмы моноидов $ж я : M \to k$ к $k$ -алгебр гомоморфизмы $F я : k [M] \to k$ , куда $k [M]$ это моноидное кольцо из $M$ над $k$ . Тогда по линейности условие

{ displaystyle sum _ {я in I} alpha _ {i} f_ {i} = 0,}

дает

{ displaystyle sum _ {я in I} alpha _ {i} F_ {i} = 0.}

Далее для $я, j \in я; я \neq j$ два $k$ -линейные карты $F я : k [M] \to k$ и $F j : k [M] \to k$ не пропорциональны друг другу. Иначе $ж я$ и $ж j$ также были бы пропорциональны и, следовательно, равны, поскольку как гомоморфизмы моноидов они удовлетворяют: $ж я (1) = 1 = ж j (1)$ , что противоречит предположению об их различии.

Следовательно, ядра $Ker F я$ и $Ker F j$ различны. С $k [M] / Ker F я ≅ F я (k [M]) = k$ это поле, $Ker F я$ является максимальным идеалом $k [M]$ для каждого $я \in я$ . Потому что они четкие и максимальные идеалы $Ker F я$ и $Ker F j$ взаимно просты, когда $я \neq j$ . Китайская теорема об остатках (для общих колец) дает изоморфизм:

{ displaystyle { begin {align} phi: k [M] / K & to prod _ {i in I} k [M] / mathrm {Ker} F_ {i} phi (x + K) & = left (x + mathrm {Ker} F_ {i} right) _ {i in I} end {align}}}

куда

{ displaystyle K = prod _ {i in I} mathrm {Ker} F_ {i} = bigcap _ {i in I} mathrm {Ker} F_ {i}.}

Следовательно, карта

{ Displaystyle { begin {align} Phi: k [M] & to prod _ {i in I} k [M] / mathrm {Ker} F_ {i} Phi (x) & = left (x + mathrm {Ker} F_ {i} right) _ {i in I} end {align}}}

сюръективно. При изоморфизмах $k [M] / Ker F я \to F я (k [M]) = k,$ карта $Φ$ соответствует:

{ Displaystyle { begin {align} psi: k [M] & to prod _ {i in I} k psi (x) & = left [F_ {i} (x) right ] _ {я in I} end {выровнен}}}

Сейчас же,

{ Displaystyle сумма _ {я в I} альфа _ {я} F_ {я} = 0}