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

Пусть m — натуральное число, m₁, m₂, …, m_t — взаимно простые натуральные числа, произведение которых больше либо равно m.

Теорема

Любое число x: 0 <= x <= m может быть однозначно представлено в виде последовательности r(x) = (r₁, r₂, …, r_t), где r_i = x(mod m_i). Для любых чисел r₁ .. r_t, таким образом, существует единственное число x(mod m), такое что x = r_i(mod m_i), 1 <= i <= t Более того, любое решение x набора такого сравнений имеет вид

x = r₁*e₁ + … + r_t*e_t (mod m), где e_i = m / m_i * ( ( m/m_i )^-1 mod m_i ),

1 <= i <= t.

Вышеприведенная формулировка — Китайская Теорема об Остатках в том виде, в котором ее сформулировал в 1247 году нашей эры китаец Jiushao Qin. Заметим, что число m/m_i = m₁*…*m_i-1*m_i+1*…*m_t взаимно просто с m_i, а значит обратное число в формуле для e_i всегда существует. Кроме того, имеют место равенства

e_i*e_i = e_i (mod m) e_i * e_j = 0 (mod m),  i =/= j.

Знакомым с теорией колец: Z_m = Zm₁ + … + Zm_t, сумма прямая. e_i, как следует из равенств выше — ортогональные идемпотенты в кольце Zm. Иначе говоря, кольцо R = Zm разлагается в прямую сумму

R = R₁ + R₂ + … + R_t ,

где R_i = Re_i = {a*e_i (mod m): a — целое} ~ Zm_i , 1 <= i <= t.

Последовательность ( r₁, …, r_t ) называется модульным представлением x. Набор модульных представлений для всех x: 0 <= x <= m называется системой вычетов.