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

Пусть 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.

Заметим, что число 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 называется системой вычетов.