|
Страница 1 из 3
Пусть m - натуральное число, m1, m2, ..., mt - взаимно простые натуральные числа, произведение которых больше либо равно m. Теорема Любое число x: 0 <= x <= m может быть однозначно представлено в виде последовательности r(x) = (r1, r2, ..., rt), где ri = x(mod mi). Для любых чисел r1 .. rt, таким образом, существует единственное число x(mod m), такое что x = ri(mod mi), 1 <= i <= t Более того, любое решение x набора такого сравнений имеет вид x = r1*e1 + ... + rt*et (mod m), где ei = m / mi * ( ( m/mi )-1 mod mi ), 1 <= i <= t. Вышеприведенная формулировка - Китайская Теорема об Остатках в том виде, в котором ее сформулировал в 1247 году нашей эры китаец Jiushao Qin. Заметим, что число m/mi = m1*...*mi-1*mi+1*...*mt взаимно просто с mi, а значит обратное число в формуле для ei всегда существует. Кроме того, имеют место равенства ei*ei = ei (mod m)
ei * ej = 0 (mod m), i =/= j. Знакомым с теорией колец: Zm = Zm1 + ... + Zmt, сумма прямая. ei, как следует из равенств выше - ортогональные идемпотенты в кольце Zm. Иначе говоря, кольцо R = Zm разлагается в прямую сумму R = R1 + R2 + ... + Rt , где Ri = Rei = {a*ei (mod m): a - целое} ~ Zmi , 1 <= i <= t. Последовательность ( r1, ..., rt ) называется модульным представлением x. Набор модульных представлений для всех x: 0 <= x <= m называется системой вычетов. Операции Сумма представлений - последовательность wi = ri + ui mod mi Произведение - последовательность zi = ri * ui mod mi. Как восстановить число по системе вычетов? |