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

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