Изменения

Сравнения n-ой степени по составному модулю

6 байтов добавлено, 6 лет назад
м
Нет описания правки
__TOC__
 
== Основные определения и утверждения==
<math>~ f(x0 x) \equiv 0(mod~n)</math>, где <math>~ deg f(x) = n, f(x)</math> - многочлен, не произвольная функция.
{{Теорема|Утверждение|Если <math>~ m_1, \ldots, m_r</math> - попарно взаимно простые числа, <math>~ m = \prod_{i=1}^r m_i</math>, тогда
<math>~ \left\{ \begin{matrix}
x \equiv a(mod~m_1) \\
x \equiv a_2(mod~m_2) \\ \ldots(m_i, m_j) = 1 \\
x \equiv a_r(mod~m_r)
\end{matrix} (2) \right.,\ (m_i, m_j) = 1 </math>
Согласно КТО эта система имеет решение <math>~ \Rightarrow</math> выпишем его: <math>~ x_0 = a_1e_1 + a_2e_2 + \ldots a_rl_r(mod~m)</math>, где <math>~ e_1, \ldots e_r</math> зависит от <math>~ m_i. x_o - </math> также решение сравнения (1).
Это утверждение позволяет свести <math>~ m = p_1^{\alpha_1} \cdot \ldots p_r^{\alpha_r}</math> к решению в случае <math>~ m = p^{\alpha}</math>. Далее этот случай сведем к <math>~ m = p</math>.
{{Пример|Пример|Возьмем <math>~ f(x) = 3x^36x36+x^2 + x +10 = 0 (mod~15); 15 = 3(m_1)\cdot 5(m_2)</math>
<math>~ (2): \left\{ \begin{matrix}
<math>~ p|f(x_0) \Rightarrow f(x_0) = 0(mod~p)</math>
<math>~ x_0 - </math> решение <math> {\color{Maroon}(1)}, f(x_0) = O(p^{\alpha}) \Leftrightarrow p^{\alpha} | \beta(x_0), p|f(x_0), f(x_0 ) \equiv 0(mod~p)</math><math>\to {\color{Maroon}(2)}</math>
<math>~ (p \to p^2 \to p^3 \to p)</math>
<math>~ f(x) \equiv 0(mod~p^3); f(x_2+p^2t_2) \equiv 0(mod~p^3)</math>
<math>~ f(x_2) + p^2t_2f'(x_0) = o0\ (mod~p^3)\cdots p^3</math>
<math>~ f'(x_2)t_2 = -\frac{f(x_2)}{p^2} (mod~p) {\color{Maroon}(*')}</math>
Editors
123
правки