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

Теорема о решении одновременных сравнений

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

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

Например, если мы знаем, что остаток от деления n на 3 равен 2, остаток от деления n на 5 равен 3, а остаток от деления n на 7 равен 2, то, не зная значения n , мы можем определить, что остаток от n , разделенный на 105 (произведение 3, 5 и 7), равен 23. Важно отметить, что это говорит нам о том, что если n — натуральное число меньше 105, то 23 — единственное возможное значение n .

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

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

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

История

Самая ранняя известная формулировка теоремы как задачи с конкретными числами содержится в книге китайского математика Суньцзы V века «Суньцзы Суаньцзин» ^{: [1]}

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

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

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

Понятие сравнений было впервые введено и использовано Карлом Фридрихом Гауссом в его «Disquisitiones Arithmeticae» ¹⁸⁰¹ года . солнечному и лунному циклу и римскому индикту». ^[10] Гаусс представляет процедуру решения задачи, которая уже использовалась Леонардом Эйлером , но на самом деле представляла собой древний метод, появлявшийся несколько раз. ^[11]

Заявление

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

Китайская теорема об остатках утверждает, что если n _i попарно взаимно просты и если a ₁ , ..., a _k — целые числа такие, что 0 ⩽ a _i < n _i для каждого i , то существует одно и только одно целое число x , такой, что 0 ≤ _x < N и остаток евклидова деления x на n i равен a _i для каждого i .

Это можно переформулировать следующим образом в терминах сравнений : если они попарно взаимно просты и если a ₁ , ..., a _k — любые целые числа, то система ${\displaystyle n_{i}}$

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\,\,\,\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}}$

имеет решение, и любые два решения, скажем, _{x1 и x2} , конгруэнтны по _модулю N , то есть x1 ≡ x2 (mod N  ) . ^[12]

В абстрактной алгебре теорему часто переформулируют так: если n i _{попарно} взаимно просты, отображение

${\displaystyle x{\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 и прямым произведением колец целых чисел по модулю n _i . Это означает, что для выполнения последовательности арифметических операций в каждом из них можно выполнить одно и то же вычисление независимо, а затем получить результат, применив изоморфизм (справа налево). Это может быть намного быстрее, чем прямое вычисление, если N и количество операций велико. Это широко используется под названием «многомодульные вычисления » для линейной алгебры над целыми или рациональными числами . ${\displaystyle \mathbb {Z} /N\mathbb {Z} ,}$ ${\displaystyle \mathbb {Z} /n_{i}\mathbb {Z} }$

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

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

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

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

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

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

Карта

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

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

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

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

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

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

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

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}},\end{aligned}}}$

где и взаимно просты . ${\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{aligned}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{aligned}}}$

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

Общий случай

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

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}}$

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

Фактически, как и кратно for, мы имеем ${\displaystyle N_{j}}$ ${\displaystyle n_{i}}$ ${\displaystyle i\neq j,}$

${\displaystyle x\equiv a_{i}M_{i}N_{i}\equiv a_{i}(1-m_{i}n_{i})\equiv a_{i}{\pmod {n_{i}}},}$

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

Вычисление

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

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\\\end{aligned}}}$

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

${\displaystyle {\begin{aligned}x&\equiv 0{\pmod {3}}\\x&\equiv 3{\pmod {4}}\\x&\equiv 4{\pmod {5}}.\end{aligned}}}$

Представлено несколько методов расчета. Два первых полезны для небольших примеров, но становятся очень неэффективными, когда продукт большой. Третий использует доказательство существования, данное в § Существование (конструктивное доказательство). Это наиболее удобно, когда произведение большое или для компьютерных вычислений. ${\displaystyle n_{1}\cdots n_{k}}$ ${\displaystyle n_{1}\cdots n_{k}}$

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

Легко проверить, является ли значение x решением : достаточно вычислить остаток от евклидова деления x по каждому n _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 мод 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 по модулю 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\times 4+(-1)\times 3=1.}$

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

${\displaystyle 0\times 1\times 4+3\times (-1)\times 3=-9}$

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

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

${\displaystyle 5\times 5+(-2)\times 12=1.}$

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

${\displaystyle 5\times 5\times 3+12\times (-2)\times 4=-21.}$

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

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

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

${\displaystyle {\begin{aligned}x&=a_{1}+x_{1}n_{1}\\&\vdots \\x&=a_{k}+x_{k}n_{k},\end{aligned}}}$

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

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

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

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

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

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

Китайская теорема об остатках для многочленов такова: Пусть (модули) будут для попарно взаимно простыми полиномами в . Позвольте быть степенью и суммой Если полиномы такие, что или для каждого i , то существует один и только один полином , такой, что и остаток евклидова деления by соответствует каждому i . ${\displaystyle P_{i}(X)}$ ${\displaystyle i=1,\dots ,k}$ ${\displaystyle R=K[X]}$ ${\displaystyle d_{i}=\deg P_{i}}$ ${\displaystyle P_{i}(X)}$ ${\displaystyle D}$ ${\displaystyle d_{i}.}$ ${\displaystyle A_{i}(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 i=1,\ldots ,k.}$

Рассмотрим полиномы

${\displaystyle {\begin{aligned}Q(X)&=\prod _{i=1}^{k}P_{i}(X)\\Q_{i}(X)&={\frac {Q(X)}{P_{i}(X)}}.\end{aligned}}}$

Разложение в частные дроби дает k многочленов таких степеней , что ${\displaystyle 1/Q(X)}$ ${\displaystyle S_{i}(X)}$ ${\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 i\leq k.}$

Это решение может иметь степень больше, чем. Единственное решение степени меньше, можно получить, рассматривая остаток евклидова деления на. Это решение есть ${\displaystyle D=\sum _{i=1}^{k}d_{i}.}$ ${\displaystyle D}$ ${\displaystyle B_{i}(X)}$ ${\displaystyle A_{i}(X)S_{i}(X)}$ ${\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{aligned}Q(X)&=\prod _{i=1}^{k}(X-x_{i})\\[6pt]Q_{i}(X)&={\frac {Q(X)}{X-x_{i}}}.\end{aligned}}}$

Разложение на частичные дроби ${\displaystyle {\frac {1}{Q(X)}}}$

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

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

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

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

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

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

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

${\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 g=\gcd(m,n)}$ ${\displaystyle M=\operatorname {lcm} (m,n)}$

${\displaystyle {\begin{aligned}x&\equiv a{\pmod {m}}\\x&\equiv b{\pmod {n}},\end{aligned}}}$

Если , то эта система имеет единственное решение по модулю . В противном случае она не имеет решений. ${\displaystyle a\equiv b{\pmod {g}}}$ ${\displaystyle M=mn/g}$

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

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

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

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

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

Пусть I ₁ , ..., I _k — двусторонние идеалы кольца и I — их пересечение . Если идеалы попарно взаимно просты, мы имеем изоморфизм : ${\displaystyle R}$

${\displaystyle {\begin{aligned}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{aligned}}}$

между фактор-кольцом и прямым произведением где " " обозначает образ элемента в фактор-кольце, определяемом идеалом. Более того, если коммутативно , то идеальное пересечение попарно взаимно простых идеалов равно их произведению ; то есть ${\displaystyle R/I}$ ${\displaystyle R/I_{i},}$ ${\displaystyle x{\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 ≠ j .

Интерпретация в терминах идемпотентов

Пусть – попарно взаимно простые двусторонние идеалы с и ${\displaystyle I_{1},I_{2},\dots ,I_{k}}$ ${\displaystyle \bigcap _{i=1}^{k}I_{i}=0,}$

${\displaystyle \varphi :R\to (R/I_{1})\times \cdots \times (R/I_{k})}$

— изоморфизм, определенный выше. Пусть будет элементом, все компоненты которого равны 0 , кроме i  -го, равного 1 , и ${\displaystyle f_{i}=(0,\ldots ,1,\ldots ,0)}$ ${\displaystyle (R/I_{1})\times \cdots \times (R/I_{k})}$ ${\displaystyle e_{i}=\varphi ^{-1}(f_{i}).}$

Это центральные идемпотенты , попарно ортогональные ; это означает, в частности, что и для каждых i и j . Более того, есть и ${\displaystyle e_{i}}$ ${\displaystyle e_{i}^{2}=e_{i}}$ ${\displaystyle e_{i}e_{j}=e_{j}e_{i}=0}$ ${\textstyle e_{1}+\cdots +e_{n}=1,}$ ${\displaystyle I_{i}=R(1-e_{i}).}$

Таким образом, эта обобщенная китайская теорема об остатках представляет собой эквивалентность между предоставлением попарно взаимно простых двусторонних идеалов с нулевым пересечением и предоставлением центральных и попарно ортогональных идемпотентов, сумма которых равна 1 . ^[19]

Приложения

Порядковая нумерация

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

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

Алгоритм БПФ с простым коэффициентом (также называемый алгоритмом Гуда-Томаса) использует китайскую теорему об остатках для сведения вычисления быстрого преобразования Фурье размера к вычислению двух быстрых преобразований Фурье меньших размеров и (при условии, что и взаимно просты). ${\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{aligned}\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 \times \mathbb {Z} /p_{m_{j}}^{b_{j}}\end{aligned}}}$

где . Кроме того, для любого индуцированного отображения ${\displaystyle \{p_{m_{1}},\ldots ,p_{m_{j}}\}\subseteq \{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 . Тогда любое конечное семейство (  fi  ) _{i ∈ I} различных  моноидных гомоморфизмов fi _: M → k линейно независимо _. Другими словами, каждое семейство ₍ αi ) i _{∈ I элементов} αi ∈ k , _{удовлетворяющее} условиям  

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

должно быть равно семейству (0) _{i ∈ I} .

Доказательство. Сначала предположим, что k — поле , в противном случае замените область целостности k ее полем частных , и ничего не изменится. Мы можем линейно расширить моноидные гомоморфизмы f _i  : M → k до гомоморфизмов k -алгебр F _i  : k [ M ] → k , где k [ M ] — кольцо моноида M над k . Тогда по линейности условие 

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

урожайность

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

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

Следовательно, ядра Ker  F _i и Ker  F _j различны. Поскольку k [ M ]/Ker  F i _≅ F i ₍  k [ M ] ) = k — поле, Ker F _i — максимальный идеал k [ M ] для каждого i из I . _{Поскольку они различны и максимальны ,} идеалы Ker  Fi и Ker  F _j взаимно просты всякий раз, когда i ≠ j . Китайская теорема об остатках (для общих колец) дает изоморфизм:

${\displaystyle {\begin{aligned}\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{aligned}}}$

где

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

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

${\displaystyle {\begin{aligned}\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{aligned}}}$

является сюръективным. При изоморфизмах k [ M ]/Ker  F _i → F _i  ( k [ M ]) = k отображение Φ соответствует:

${\displaystyle {\begin{aligned}\psi :k[M]&\to \prod _{i\in I}k\\\psi (x)&=\left[F_{i}(x)\right]_{i\in I}\end{aligned}}}$

Сейчас,

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

урожайность

${\displaystyle \sum _{i\in I}\alpha _{i}u_{i}=0}$

для каждого вектора ( u _i ) _{i ∈ I} в образе отображения ψ . Поскольку ψ сюръективен, это означает, что

${\displaystyle \sum _{i\in I}\alpha _{i}u_{i}=0}$

для каждого вектора

${\displaystyle \left(u_{i}\right)_{i\in I}\in \prod _{i\in I}k.}$

Следовательно, ( α _я ) _{я ∈ I} знак равно (0) _{я ∈ I} . КЭД.

Смотрите также

• Система покрытия
• Принцип Хассе
• Система нумерации остатков

Примечания

1. Кац 1998, с. 197
2. Денс и Денс 1999, с. 156
3. Даубен 2007, с. 302
4. Как 1986 г.
5. Пизано 2002, стр. 402–403.
6. Даубен 2007, с. 310
7. Либбрехт 1973
8. Гаусс 1986, ст. 32–36
9. Ирландия и Розен 1990, с. 36
10. Руда 1988, с. 247
11. Руда 1988, с. 245
12. Ирландия и Розен 1990, с. 34
13. Ирландия и Розен 1990, с. 35
14. Дюше 1995
15. Розен 1993, с. 136
16. Руда 1952.
17. Ирландия и Розен 1990, с. 181
18. Сенгупта 2012, с. 313
19. Бурбаки, Н. 1989, с. 110

Рекомендации

• Даубен, Джозеф В. (2007), «Глава 3: Китайская математика», в книге Кац, Виктор Дж. (редактор), « Математика Египта, Месопотамии, Китая, Индии и ислама: справочник» , Princeton University Press, стр. 187–384, ISBN 978-0-691-11485-9
• Денс, Джозеф Б.; Денс, Томас П. (1999), Элементы теории чисел, Academic Press, ISBN 9780122091308
• Дюше, Пьер (1995), «Гиперграфы», в Грэме, РЛ; Гретшель, М .; Ловас Л. (ред.), Справочник по комбинаторике, Vol. 1, 2 , Амстердам: Elsevier, стр. 381–432, MR  1373663.. См., в частности, раздел 2.5 «Собственность Хелли», стр. 393–394.
• Гаусс, Карл Фридрих (1986), Disquisitiones Arithemeticae , перевод Кларка, Артура А. (второе, исправленное издание), Нью-Йорк: Springer , ISBN 978-0-387-96254-2
• Ирландия, Кеннет; Розен, Майкл (1990), Классическое введение в современную теорию чисел (2-е изд.), Springer-Verlag, ISBN 0-387-97329-Х
• Как, Субхаш (1986), «Вычислительные аспекты алгоритма Арьябхаты» (PDF) , Индийский журнал истории науки , 21 (1): 62–71
• Кац, Виктор Дж. (1998), История математики / Введение (2-е изд.), Аддисон Уэсли Лонгман, ISBN 978-0-321-01618-8
• Либбрехт, Ульрих (1973), Китайская математика в тринадцатом веке: «Шу-шу Цзю-чан» Цинь Цзю-шао , Dover Publications Inc, ISBN 978-0-486-44619-6
• Оре, Эйстейн (1952), «Общая китайская теорема об остатках», The American Mathematical Monthly , 59 : 365–370, doi : 10.2307/2306804, MR  0048481
• Оре, Эйстейн (1988) [1948], Теория чисел и ее история , Дувр, ISBN 978-0-486-65620-5
• Пизано, Леонардо (2002), Liber Abaci Фибоначчи, перевод Сиглера, Лоуренса Э., Springer-Verlag, стр. 402–403, ISBN 0-387-95419-8
• Розен, Кеннет Х. (1993), Элементарная теория чисел и ее приложения (3-е изд.), Аддисон-Уэсли, ISBN 978-0201-57889-8
• Сенгупта, Амбар Н. (2012), Представление конечных групп, полупростое введение , Springer, ISBN 978-1-4614-1232-8
• Бурбаки, Н. (1989), Алгебра I, Springer, ISBN 3-540-64243-9

дальнейшее чтение

• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001), Введение в алгоритмы (второе изд.), MIT Press и McGraw-Hill, ISBN 0-262-03293-7. См. раздел 31.5: Китайская теорема об остатках, стр. 873–876.
• Дин, Цуньшэн; Пей, Динъи; Саломаа, Арто (1996), Китайская теорема об остатках: приложения в вычислениях, кодировании, криптографии, World Scientific Publishing, стр. 1–213, ISBN 981-02-2827-9
• Хангерфорд, Томас В. (1974), Алгебра, Тексты для выпускников по математике, Vol. 73, Springer-Verlag, стр. 131–132, ISBN. 978-1-4612-6101-8
• Кнут, Дональд (1997), Искусство компьютерного программирования , том. 2: Получисловые алгоритмы (Третье изд.), Аддисон-Уэсли, ISBN 0-201-89684-2. См. раздел 4.3.2 (стр. 286–291), упражнение 4.6.2–3 (стр. 456).

Внешние ссылки

• «Китайская теорема об остатках», Математическая энциклопедия , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. , «Китайская теорема об остатках», MathWorld
• Китайская теорема об остатках на сайте PlanetMath .
• Полный текст Сунь-цзы Суань-цзин (китайский) - Проект китайского текста