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

Исходная формулировка Сунзи: 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 века «Суньцзы Суаньцзин »: китайского математика

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

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

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

Понятие сравнений было впервые введено и использовано Карлом Фридрихом Гауссом в его «Арифметических исследованиях» 1801 года. Гаусс иллюстрирует китайскую теорему об остатках в задаче, связанной с календарями, а именно: «найти годы, имеющие определенное число периодов, относительно солнечного и лунного цикла и римского индикта». Гаусс вводит процедуру решения задачи, которая уже использовалась Леонардом Эйлером, но на самом деле представляла собой древний метод, появлявшийся несколько раз.

Заявление

Пусть 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 .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Карта

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

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

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

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

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

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

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

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

где $n_{1}$ и $n_{2}$ взаимнопросты ​ .

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

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

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

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

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

Действительно,

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

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

Общий случай

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

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

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

$x\equiv a_{1,2}{\pmod {n_{1}n_{2}}}.$

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

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

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

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

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

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

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

Фактически, как $N_{j}$ кратно $n_{i}$ для $i\neq j,$ у нас есть

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

для каждого $i.$

Вычисление

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

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

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

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

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

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

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

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

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

Поиск путем просеивания

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

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

$a_{1},a_{1}+n_{1},a_{1}+2n_{1},\ldots$

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

$x_{2},x_{2}+n_{1}n_{2},x_{2}+2n_{1}n_{2},\ldots$

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

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

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. Хорошо, вот результат.

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

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

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

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

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

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

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

$1\times 4+(-1)\times 3=1.$

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

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

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

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

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

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

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

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

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

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

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

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

идеальными

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

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

кольцами одномерных многочленов и

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

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

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

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

$P(X)\equiv A_{i}(X){\pmod {P_{i}(X)}},$

для $i=1,\ldots ,k.$

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

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

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

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

и поэтому

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

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

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

На самом деле, у нас есть

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

для $1\leq i\leq k.$

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

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

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

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

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

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

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

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

для каждого $i.$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$P(X)\equiv P_{i}(X){\pmod {(X-x_{i})^{r_{i}}}}.$

Обратно , любой полином $P(X)$ который удовлетворяет этим $k$ сравнения, в частности, проверяет, для любого $i=1,\ldots ,k$

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

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

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

Обобщение на невзаимные модули

Китайскую теорему об остатках можно обобщить на невзаимно простые модули. Позволять $m,n,a,b$ любые целые числа, пусть $g=\gcd(m,n)$; $M=\operatorname {lcm} (m,n)$, и рассмотрим систему сравнений:

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

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

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

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

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

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

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

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

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

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

$I=I_{1}\cap I_{2}\cap \cdots \cap I_{k}=I_{1}I_{2}\cdots I_{k},$

если I _i и I _j взаимно просты для всех i ≠ j .

терминах

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

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

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

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

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

Приложения

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

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

Фурье

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

Шифрование

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

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

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

Основная статья: Разрешение неоднозначности диапазона

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

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

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

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

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

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

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

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

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

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

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

Теорема Дедекинда о линейной независимости характеров. Пусть M — моноид , а k — область целостности , рассматриваемая как моноид с учетом умножения на k . семейство ( fi ₎ Тогда _{i ∈ I} различных моноидных гомоморфизмов   fi _: M k → любое конечное независимо линейно . Другими словами, каждое семейство αi ) _{удовлетворяющее} i _{∈ I элементов} αi ∈ ₍ k , условиям

$\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 . Тогда по линейности условие

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

урожайность

$\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) = 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 . Китайская теорема об остатках (для общих колец) дает изоморфизм:

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

где

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

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

${\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 : отображение Φ соответствует

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

Сейчас,

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

урожайность

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

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

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

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

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

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

См. также

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

Ссылки

• Даубен, Джозеф В. (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-Publishers, 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-Publishing House, стр. 100–1. 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 .
• Полный текст Сунь-цзы Суань-цзин (китайский) - Проект китайского текста
• Китайская теорема об остатках на ProofWiki