2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Расширенный вариант китайской теоремы об остатках
Сообщение26.05.2013, 23:26 
Заранее извиняюсь, если напутал что-нибудь с терминологией, старался как мог.

Имеется набор остатков от деления числа $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$ всегда существует и не нужно дополнительных проверок

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

 
 
 
 Re: Расширенный вариант китайской теоремы об остатках
Сообщение27.05.2013, 07:49 
Аватара пользователя
Чуть подробнее:
Каждое сравнение $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 писал(а):
имеем каноническую задачу.

 
 
 
 Re: Расширенный вариант китайской теоремы об остатках
Сообщение27.05.2013, 08:37 
И правда. Спасибо. Это уже не просто идея, а, по сути, готовый алгоритм.

 
 
 
 Re: Расширенный вариант китайской теоремы об остатках
Сообщение27.05.2013, 09:04 
Аватара пользователя
AlexanderPlus в сообщении #728782 писал(а):
можно считать что все $r_i \neq 0$ - в этом случае, насколько я понимаю, число $x$ всегда существует

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

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

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group