остатки от деления.

[yestlmush]

Добрый день!

У меня такой вопрос: если мы имеем набор остатков $x\mod p_1, x\mod p_2, ..., x\mod p_k$,
$p_i$ --- простые числа.
Можно ли получить по этим данным остаток от деления $x$ на произведение $p_i$?
Т.е. можно ли получить, и если да, то как получить $x\mod p_1 p_2 ... p_k$?

[nnosipov]

Прочитайте где-нибудь про китайскую теорему об остатках.

[yestlmush]

nnosipov в сообщении #522213 писал(а):

Прочитайте где-нибудь про китайскую теорему об остатках.

Я знаю китайскую теорему, но она гласит, что "найдется" такое. Как находить --- непонятно.

[bot]

В доказательстве есть и рецепт нахождения "такого".

[yestlmush]

тем не менее, я не понимаю, как от независимых остатков перейти к остатку от деления на произведение.

[nnosipov]

yestlmush, найдите конструктивное доказательство, дающее алгоритм (формулу) для отыскания искомого остатка. Или придумайте сами, сведя задачу к решению сравнений 1-й степени с одним неизвестным.