Китайская теорема об остатках — функция ChineseRemainder
Китайская теорема об остатках — функция ChineseRemainder
Хитрый китаец Сунь Цю около 2000 лет назад (конечно, это могло быть и 200 лет до нашей эры, и 200 лет после начала нашей эры) открыл правило "гай-йен" ("большое обобщение"), которое является частным случаем целочисленного аналога интерполяционной формулы Лагранжа для полиномов. (Правда, примерно в то же самое время, в 100 г. н. э., греческий математик Никомах знал точно тот же частный случай.) Полностью формула была сформулирована и доказана впервые, по-видимому, в 1734 году Л. Эйлером. Сформулируем китайскую (или греко-китайскую, как назвал ее Акритас, автор одного из широко известных учебников по компьютерной алгебре?) теорему об остатках и укажем соответствующее правило (формулу).
Пусть m1, m2, ..., mr — попарно взаимно простые модули (попарно взаимно простые положительные целые числа), m = m1, m2, ... mr — их произведение, а а, u1, u2, ..., ur — произвольные целые числа. Тогда существует ровно одно целое число и, такое, что а<u<а+m, удовлетворяющее всем сравнениям u = ui(modmi). Более того,
