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

Если известно разложение числа n на простые сомножители, то для решения полной системы уравнений можно воспользоваться Китайской теоремой об остатках. Основной вариант этой теоремы был открыт в первом веке китайским математиком Сун Цзе.

В общем случае, если разложение числа n на простые сомножители представляет собой p1*p2*...*pt, то система уравнений

(x mod pi) = ai, где i = 1, 2, . . . , t

имеет единственное решение, x, меньшее n. (Обратите внимание, что некоторые простые числа могут появляться несколько раз. Например, p1 может быть равно p2.) Другими словами, число (меньшее, чем произведение нескольких простых чисел) однозначно определяется своими остатками от деления на эти простые числа.

Например, возьмем простые числа 3 и 5, и 14 в качестве заданного числа. 14 mod 3 = 2, и 14 mod 5 = 4. Существует единственное число, меньшее 3*5 = 15, с такими остатками: 14. Два остатка однозначно определяют число.

Поэтому для произвольного a < p и b < q (где p и q — простые числа), существует единственное число x, меньшее pq, такое что

x º a (mod p), и x º b (mod q)

Для получения x сначала воспользуемся алгоритмом Эвклида, чтобы найти u, такое что

u*q º 1 (mod p)

Затем вычислим:

x = (((a – b) *u) mod p) * q + b

Обращение Китайской теоремы об остатках может быть использовано для решения следующей проблемы: если p и q – простые числа, и p меньше q, то существует единственное x, меньшее, чем pq, такое что

a º x (mod p), и b º x (mod q)

Если a ³ b mod p, то

x = (((a – (b mod p)) * u) mod p) * q + b

Если a < b mod p, то

x = (((a + p – (b mod p))*u) mod p)*q + b