Расширенный вариант китайской теоремы об остатках

[AlexanderPlus]

Заранее извиняюсь, если напутал что-нибудь с терминологией, старался как мог.

Имеется набор остатков от деления числа $x$ на различные числа $a_i$
$ \begin{cases} r_1 = x\mod a_1\\ r_2 = x\mod a_2\\ ...\\ r_i = x\mod a_n \end{cases} $

причем многие числа $a_i$ и $a_j$ не взаимно простые ( $ \verb НОД (a_i, a_j) > 1$ )

Требуется восстановить число $x$ по набору $(r_1,r_2, ..., r_n)$ - нужен алгоритм

Если бы любые 2 числа $a_i$ и $a_j$ были бы попарно взаимно простыми - мы имели бы дело с широко известной Китайской теоремой об остатках и могли использовать предложенный в ней алгоритм восстановления числа $x$.
К сожалению, этот алгоритм не подходит для нашего случая, т.к. использует обратные числа по модулю, вида $a_i^{-1} \mod a_j$, которые не существуют, если $a_i$ и $a_j$ не взаимно простые, например: $6^{-1}\ (\mod 15)$
Для упрощения можно считать что все $r_i \neq 0$ - в этом случае, насколько я понимаю, число $x$ всегда существует и не нужно дополнительных проверок

[iifat]

Как вариант: зная остаток от деления на $ab$, мы можем узнать остатки отделения как на $a$, так и на $b$. Разбиваем каждую пару взаимно не простых чисел на тройку из НОД и двух частных и имеем каноническую задачу.

[bot]

Чуть подробнее:
Каждое сравнение $x\equiv r\pmod{a=p_1^{k_1}\ldots p_s^{k_s}}$ равносильно системе сравнений по примарным модулям. Система из двух сравнений

$$\left\{\begin{matrix} x\equiv r \pmod{p^k}\\ \ x\equiv r' \pmod{p^{k'}} \\ k\geqslant k'\end{matrix}\right.$$

либо несовместна (если $r\not\equiv r' \pmod{p^{k'}}$) либо равносильна первому. Отсюда в случае совместности

iifat в сообщении #728813 писал(а):

имеем каноническую задачу.

[iifat]

И правда. Спасибо. Это уже не просто идея, а, по сути, готовый алгоритм.

[ИСН]

AlexanderPlus в сообщении #728782 писал(а):

можно считать что все $r_i \neq 0$ - в этом случае, насколько я понимаю, число $x$ всегда существует

$ \begin{cases}3\equiv x\mod15\\ 2\equiv x\mod6\end{cases} $
"и чо"

[AlexanderPlus]

bot, iifat - большое спасибо!
ИСН - это вы так вежливо указали мне на мою ошибку? Действительно, для гарантированного существования $x$ надо исключить не только $r_i = 0$, но ещё и $r_i$ кратные НОД $(a_i, a_j)$