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

Пусть 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 набора такого сравнений имеет вид

Вышеприведенная формулировка - Китайская Теорема об Остатках в том виде, в котором ее сформулировал в 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_i = Re_i = {a*e_i (mod m): a - целое} ~ Zm_i , 1 <= i <= t.

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

Операции

Сумма представлений - последовательность w_i = r_i + u_i mod m_i

Произведение - последовательность z_i = r_i * u_i mod m_i.

Как восстановить число по системе вычетов?