Глава 2. Китайская теорема об остатках

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

Одним из важных результатов теории чисел является так называемая китайская теорема об остатках (KTO). По существу эта теорема утверждает, что можно восстановить целое число по множеству его остатков от деления на числа из некоторого набора попарно взаимно простых чисел. Эта теорема в её арифметической формулировке была описана в трактате китайского математика Сунь Цзы «Сунь Цзы Суань Цзин» (кит.упр.?¤lєв?, пиньинь: sunzi suanjing), предположительно датируемом третьим веком н.?э. и затем была обобщена Цинь Цзюшао в его книге «Математические рассуждения в 9 главах» датируемой 1247 годом, где было приведено точное решение.Существует несколько формулировок данной теоремы, я предоставлю здесь некоторые из них.

Теорема. Пусть , 1 ? i ? k, взаимно простые числа

и пусть ai целые числа. Тогда существует такое число x,

что имеет место

x? mod ,

x? ,

…

x? .

Наконец, рассмотрим еще одну формулировку теоремы,

которую будем использовать в практических работах.

Теорема. Пусть {} - взаимно простые числа и M =

Пусть 0 ? ? , целые числа. Введем обозначение = . Пусть число, которое удовлетворяет сравнению ?1 mod .При этих условиях сравнение

x? mod , имеет на интервале [0, M - 1] единственное решение,которое определяется формулой x = + + … +

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

Арифметическая формулировка КТО:

Если числа попарно взаимно просты, то для любых остатков таких, что при всех i= 1,2,...n., найдётся число N, которое при делении на даёт остаток при всех i= 1,2,...n.

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

Применим индукцию по n. При n=1 утверждение теоремы очевидно. Пусть теорема справедлива при n= k-1, т. е. существует число M, дающее остаток при делении на при .Обозначим и рассмотрим числа . Покажем, что хотя бы одно из этих чисел даёт остаток при делении на . Допустим это не так. Поскольку количество чисел равно , а возможных остатков при делении этих чисел на может быть не более чем (ведь ни одно число не даёт остаток ), то среди них найдутся два числа, имеющих равные остатки (принцип Дирихле). Пусть это числа и при и . Тогда их разность делится на , что невозможно, т.к. и взаимно просто с , ибо числа попарно взаимно просты (по условию). Противоречие.

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

Наиболее используемая формулировка КТО:

Пусть - попарно взаимно простые числа и - произвольные целые числа. Тогда существует целое число ,такое что Целое число у удовлетворяет условию тогда и только тогда когда

Доказательство: Обозначим М=и . Тогда числа являются взаимно простыми для всех i. Cледовательно существует целое число такое что где . Положимтогда , поскольку числа . Аналогично доказывается, что . Пусть - остаток от деления числа a на M. Тогда и ? a (mod M). В частности Далее, пусть целое чисто у удовлетворяет условию . Тогда т. е. Число делится на каждое из чисел .В силу того, что числа попарно взаимно простые, получаем что делится на число . Таким образом, ?0 (mod ).Теорема доказана.