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

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

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

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

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

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

История [ править ]

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

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

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

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

Заявление [ править ]

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

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

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

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

и любые два решения, скажем x ₁ и x ₂ , конгруэнтны по модулю N , то есть x ₁ ≡ x ₂ (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 и количество операций большое. Это широко используется под названием многомодульное вычисление для линейной алгебры над целыми или рациональными числами .${\ 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 делит также х - у , и , следовательно , х и у сравнимы по модулю N . Если x и y должны быть неотрицательными и меньше N(как в первом утверждении теоремы), то их разность может быть кратной N, только если x = y .

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

Карта

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

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

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

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

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

Случай двух модулей [ править ]

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

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

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

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

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

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

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

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

В самом деле,

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

Фактически, как и кратное для, мы имеем${\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}}}$

где они попарно взаимно просты , и let В этом разделе описаны несколько методов вычисления уникального решения для , так что и эти методы применяются в примере:${\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}}}$

Систематический поиск [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

Интерполяция Эрмита [ править ]

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

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

Точнее, пусть будут элементами основного поля, а для пусть будут значениями первых производных искомого многочлена at (включая 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}.}$

Это многочлен Тейлора порядка 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 i=1,\ldots ,k}$

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

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

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

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

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

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

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

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

Пусть I ₁ , ..., I _K быть две односторонние идеалы кольца и пусть я бы их пересечение. Если идеалы попарно взаимно просты, мы имеем изоморфизм : ${\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 .

Приложения [ править ]

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

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

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

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

Шифрование [ править ]

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

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

Разрешение неоднозначности диапазона [ править ]

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

Теорема Дедекинда [ править ]

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

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

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

Доказательство. Сначала предположим, что k - поле, в противном случае замените область целостности k ее полем частных, и ничего не изменится. Мы можем линейно расширить моноидных гомоморфизмы F _I  : М → K с K - алгебра гомоморфизмы Р _я  : к [ М ] → K , где 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 также были бы пропорциональны и, следовательно, равны, поскольку как моноидные гомоморфизмы они удовлетворяют: f _i  (1) = 1 =   f _j  (1)     , что противоречит предположению об их различии.

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

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

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]

• Dauben, Joseph W. (2007), «Глава 3: Китайская математика», в Katz, Victor J. (ed.), The Mathematics of Egypt, Mesopotamia, China, India and Islam: A Sourcebook , Princeton University Press, стр. 187–384, ISBN 978-0-691-11485-9
• Денс, Джозеф Б .; Денс, Томас П. (1999), Элементы теории чисел , Academic Press, ISBN 9780122091308
• Duchet, Pierre (1995), «Hypergraphs», в Graham, RL; Grötschel, M .; Ловас, Л. (ред.), Справочник по комбинаторике, 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-X
• Как, Субхаш (1986), "Вычислительные аспекты алгоритма Арьябхата" (PDF) , Индийский журнал истории науки , 21 (1): 62–71
• Кац, Виктор Дж. (1998), История математики / Введение (2-е изд.), Аддисон Уэсли Лонгман, ISBN 978-0-321-01618-8
• Либбрехт, Ульрих (1973), Китайская математика в тринадцатом веке: «Шу-шу Чиу-чан» Цинь Цзю-шао , Dover Publications Inc, ISBN 978-0-486-44619-6
• Оре, Ойстейн (1988) [1948], Теория чисел и ее история , Дувр, ISBN 978-0-486-65620-5
• Пизано, Леонардо (2002), Liber Abaci Фибоначчи , переведенная Сиглером, Лоуренсом Э., Springer-Verlag, стр. 402–403, ISBN 0-387-95419-8
• Розен, Кеннет Х. (1993), Элементарная теория чисел и ее приложения (3-е изд.), Addison-Wesley, ISBN 978-0201-57889-8
• Сенгупта, Амбар Н. (2012), Представление конечных групп, Полупростое введение , Springer, ISBN 978-1-4614-1232-8

Дальнейшее чтение [ править ]

• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (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: получисловые алгоритмы (третье издание), Addison-Wesley, ISBN 0-201-89684-2. См. Раздел 4.3.2 (стр. 286–291), упражнение 4.6.2–3 (стр. 456).

Внешние ссылки [ править ]

• "Китайская теорема об остатках" , Энциклопедия математики , EMS Press , 2001 [1994]
• Вайсштейн, Эрик У. "Китайская теорема об остатках" . MathWorld .
• Китайская теорема об остатках в PlanetMath .
• Полный текст Sun-tzu Suan-ching (китайский) - Китайский текстовый проект