Из доказательства китайской теоремы об остатках вытекает существование чисел 
удовлетворяющих условиям: 
при 
, 
и 
.
Опишем идею алгоритма вычисления чисел , удовлетворяющих перечисленным выше условиям. Положим 
. По определению, 
делится на все 
, при , а, значит и на 
. Следовательно, число можно искать в виде 
. Числа 
и взаимно просты, поэтому существует единственное решение сравнения 
, которое и равно 
, причем 
. Приведем алгоритм построения чисел .
Алгоритм Mod1.
1. Вычислим 
.
2. Положим 
.
3. Если 
, то конец, все числа 
найдены. Иначе перейдём на следующий шаг.
4. Вычислим 
.
5. Найдем решение сравнения 
.
6. Положим 
.
7. Увеличим 
на 1 и вернемся на шаг 3.
Пусть, числа найдены. Нетрудно убедиться, что число 
будет иметь набор остатков 
. Для восстановления числа осталось проследить, чтобы 
оказалось в заданном интервале от 0 до 
. Число 
, где 
- частное от деления на 
, является искомым. Тем самым получили алгоритм восстановления целого числа по остаткам. Приведём его описание.
Алгоритм Mod2.
1. Вычислим 
.
2. Найдем частное от деления 
.
3. Искомое число вычислим по формуле 
