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

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

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

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

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

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

История

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

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

Работа Сунь-цзы не содержит ни доказательства, ни полного алгоритма. Что представляет собой алгоритм решения этой проблемы, был описан Арьябхатой (VI век). Особые случаи китайской теоремы об остатках были также известны Брахмагуптам (седьмой век), и появляются в Фибоначчах «s Liber Abaci (1202). Позже результат был обобщен в виде полного решения под названием Да-ян-шу (大衍術) в « Математическом трактате 1247 года в девяти разделах» Цинь Цзю-шао (數書九章, Шу-шу Цю-чан ). переведена на английский язык в начале 19 века британским миссионером Александром Вайли .

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

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

Заявление

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

Китайская оставшаяся теорема утверждает , что если п _я являются попарно взаимно просты , и если в ₁ , ..., _к представляют собой целые числа , такие , что 0 ≤ _я < п _я для каждого I , то есть одно и только одно целое число х , такие , что 0 ≤ х < н , а остальная часть евклидового деления из й по п _я это _я для каждого I .

В терминах сравнений это можно переформулировать следующим образом : если n _i попарно взаимно просты и если a ₁ , ..., a _k - любые целые числа, то система

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

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

В абстрактной алгебре теорема часто переформулируется следующим образом: если n _i попарно взаимно просты, отображение

{\ displaystyle x {\ bmod {N}} \; \ mapsto \; (x {\ bmod {n}} _ {1}, \, \ ldots, \, x {\ bmod {n}} _ {k} )}

определяет изоморфизм колец

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

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

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

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

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

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

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

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

Карта

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

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

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

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

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

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

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

{\ 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 {выровнено}}}

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

Общий случай

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

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

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

{\ displaystyle x \ Equiv a_ {1,2} {\ pmod {n_ {1} n_ {2}}}.}

Поскольку другие взаимно просты с этим, решение исходной задачи $k$ уравнений сводится к аналогичной задаче с уравнениями. Итерируя этот процесс, в конечном итоге можно получить решение исходной проблемы. ${\ displaystyle n_ {i}}$ ${\ displaystyle n_ {1} n_ {2},}$ ${\ 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 i \ neq j,}$

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

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

Вычисление

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

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

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

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

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

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

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

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

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

Наименьшие два решения, 23 и 128, исходной формулировки китайской проблемы теоремы об остатках, найденные с помощью сита

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

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

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}.}$

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

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

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

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

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

Китайская теорема об остатке для многочленов такова: пусть (модули) будут, для $i$ $= 1, ...,$ $k$ , попарно взаимно простыми многочленами в . Пусть будет степень , и будет сумма If многочлены такие , что и для каждого $I$ , то есть один и только один многочлен , таким образом, что и остальная часть евклидовой деления из по является для каждого $I$ . ${\ displaystyle P_ {i} (X)}$ ${\ 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} <d_ {i}}$ ${\ Displaystyle P (X)}$ ${\ Displaystyle \ deg P <D}$ ${\ 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 {выравнивается}}}

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

{\ 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}).}$

Теперь, пусть будут константы (полиномы степени 0) как в интерполяции Лагранжа, так и в китайской теореме об остатках, утверждающих существование единственного полинома степени меньше, чем такой, что ${\ Displaystyle A_ {1}, \ ldots, A_ {k}}$ ${\ 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}}}

Частичное разложение фракции из IS ${\ 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})}}. }

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

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

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

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

Это многочлен Тейлора порядка at неизвестного многочлена Следовательно, мы должны иметь ${\ 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}}

следовательно, является его многочленом Тейлора порядка at , то есть решает исходную задачу интерполяции Эрмита. Китайская теорема об остатках утверждает, что существует ровно один многочлен степени меньше суммы, удовлетворяющий этим сравнениям. ${\ 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}}, \ end {выровнено}}}

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

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

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

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

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

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

Пусть $I 1, ..., I 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 {align}}}

между кольцом вычетов и прямым произведением из где « » обозначает образ элемента в факторе - кольце , определенном идеал Более того, если это коммутативное , то идеал пересечение попарно взаимно простых идеалов, равно их продукт ; то есть ${\ 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},}

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

Приложения

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

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

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

Алгоритм FFT прайма-фактор (также называемый алгоритмом Good-Thomas) использует китайскую теорему об остатках для уменьшения вычисления быстрого преобразования Фурье размера для вычисления двух быстрых преобразований Фурье меньших размеров и ( при условии , что и взаимно просто). ${\ displaystyle n_ {1} n_ {2}}$ ${\ displaystyle n_ {1}}$ ${\ displaystyle n_ {2}}$ ${\ displaystyle n_ {1}}$ ${\ displaystyle n_ {2}}$

Шифрование

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

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

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

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

Разложение сюръекций конечных абелевых групп

Учитывая сюръекцию конечных абелевых групп , мы можем использовать китайскую теорему об остатках, чтобы дать полное описание любого такого отображения. Прежде всего, теорема дает изоморфизмы ${\ displaystyle \ mathbb {Z} / n \ to \ mathbb {Z} / m}$

${\ displaystyle {\ begin {align} \ mathbb {Z} / n & \ cong \ mathbb {Z} / p_ {n_ {1}} ^ {a_ {1}} \ times \ cdots \ times \ mathbb {Z} / p_ {n_ {i}} ^ {a_ {i}} \\\ mathbb {Z} / m & \ cong \ mathbb {Z} / p_ {m_ {1}} ^ {b_ {1}} \ times \ cdots \ раз \ mathbb {Z} / p_ {m_ {j}} ^ {b_ {i}} \ end {align}}}$

где . Кроме того, для любой индуцированной карты ${\ displaystyle \ {p_ {m_ {1}}, \ ldots, p_ {m_ {j}} \} \ substeq \ {p_ {n_ {1}}, \ ldots, p_ {n_ {i}} \}}$

${\ Displaystyle \ mathbb {Z} / p_ {n_ {k}} ^ {a_ {k}} \ to \ mathbb {Z} / p_ {m_ {l}} ^ {b_ {l}}}$

из исходной сюръекции, мы имеем и , поскольку для пары простых чисел , единственные ненулевые сюръекции ${\ displaystyle a_ {k} \ geq b_ {l}}$ ${\ displaystyle p_ {n_ {k}} = p_ {m_ {l}}}$ ${\ displaystyle p, q}$

${\ Displaystyle \ mathbb {Z} / p ^ {a} \ to \ mathbb {Z} / q ^ {b}}$

можно определить, если и . ${\ displaystyle p = q}$ ${\ displaystyle a \ geq b}$

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

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

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

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

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

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

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

дает

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

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

Следовательно, ядра $Ker F i$ и $Ker F j$ различны. Так как $K [M] / Ker F я ≅ Р я (к [М]) = K$ является полем, $Кер Р я$ имеет максимальный идеал $к [М]$ для каждого $I \in I$ . Поскольку они различны и максимальны, идеалы $Ker F i$ и $Ker F j$ взаимно просты, если $i \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}}}

сюръективно. Под изоморфизмов $к [М] / Кер F я \to F я (к [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}