Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:17, 14 мая 2016.
|
|
Строка 1: |
Строка 1: |
| + | __TOC__ |
| + | |
| == Основные определения и утверждения== | | == Основные определения и утверждения== |
− | <math>~ f(x0 \equiv 0(mod~n)</math>, где <math>~ deg f(x) = n, f(x)</math> - многочлен, не произвольная функция. | + | <math>~ f(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>~ m_1, \ldots, m_r</math> - попарно взаимно простые числа, <math>~ m = \prod_{i=1}^r m_i</math>, тогда |
Строка 23: |
Строка 25: |
| <math>~ \left\{ \begin{matrix} | | <math>~ \left\{ \begin{matrix} |
| x \equiv a(mod~m_1) \\ | | x \equiv a(mod~m_1) \\ |
− | x \equiv a_2(mod~m_2) \\ | + | x \equiv a_2(mod~m_2) \\ |
− | \ldots(m_i, m_j) = 1 \\ | + | \ldots \\ |
| x \equiv a_r(mod~m_r) | | x \equiv a_r(mod~m_r) |
− | \end{matrix} (2) \right.</math> | + | \end{matrix} \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>~ \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). |
Строка 44: |
Строка 46: |
| Это утверждение позволяет свести <math>~ m = p_1^{\alpha_1} \cdot \ldots p_r^{\alpha_r}</math> к решению в случае <math>~ m = p^{\alpha}</math>. Далее этот случай сведем к <math>~ m = p</math>. | | Это утверждение позволяет свести <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^36x^2 + x +10 = 0 (mod~15); 15 = 3(m_1)\cdot 5(m_2)</math> | + | {{Пример|Пример|Возьмем <math>~ f(x) = 3x^36+x^2 + x +10 = 0 (mod~15); 15 = 3(m_1)\cdot 5(m_2)</math> |
| | | |
| <math>~ (2): \left\{ \begin{matrix} | | <math>~ (2): \left\{ \begin{matrix} |
Строка 83: |
Строка 85: |
| <math>~ p|f(x_0) \Rightarrow f(x_0) = 0(mod~p)</math> | | <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>~ 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>~ (p \to p^2 \to p^3 \to p)</math> |
Строка 141: |
Строка 143: |
| <math>~ f(x) \equiv 0(mod~p^3); f(x_2+p^2t_2) \equiv 0(mod~p^3)</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) = o(mod~p^3)\cdots p^3</math> | + | <math>~ f(x_2) + p^2t_2f'(x_0) = 0\ (mod~p^3)</math> |
| | | |
| <math>~ f'(x_2)t_2 = -\frac{f(x_2)}{p^2} (mod~p) {\color{Maroon}(*')}</math> | | <math>~ f'(x_2)t_2 = -\frac{f(x_2)}{p^2} (mod~p) {\color{Maroon}(*')}</math> |
Текущая версия на 15:17, 14 мая 2016
Основные определения и утверждения
, где - многочлен, не произвольная функция.
 Теорема Утверждение
|
Если - попарно взаимно простые числа, , тогда
1
2 Количество решений:
|
Доказательство
|
Рассмотрим
1 Пусть решение (1) . Из свойств сравнений известно, что НОК, а так как все взаимно просты .
2 Если больше решений нет. Посчитаем иначе - как одно из решений (2). Тогда:
Согласно КТО эта система имеет решение выпишем его: , где зависит от также решение сравнения (1).
Посчитаем, сколько таких решений:
Допустим
Следовательно, наборы взяты из одного класса, а значит
|
|
Это утверждение позволяет свести к решению в случае . Далее этот случай сведем к .
 Пример Пример
|
Возьмем
|
|
Сведение решения сравнения по примарному модулю к простому
Научимся решать систему по примарному модулю
Можно свести к решению
Пусть решение это означает, что:
решение
Пусть найдено решение сравнения :
- решение , из определения сравнимости
Какие нужно взять , чтобы удовлетворять сравнению?
 Лемма «Утверждение»
|
- разложение в ряд Тейлора
|
|
Определим
Если собрать коэффициенты при (после применения формулы бинома Ньютона к :
то получим то же значение, что и в случае производной в матанализе.
Перепишем функцию по-другому:
Очевидно, пришли к виду:
, и оно имеет решение, тогда
Возможны следующие варианты:
- проверим, будет ли это решение удовлетворять .
так как
Тогда
где . Получим, что
удовлетворяет (т.е. все удовлетворяют )
ISSN 2542-0356
Следуй за Полисом
Оставайся в курсе последних событий
Лицензия
Если не указано иное, содержание этой страницы доступно по лицензии Creative Commons «Attribution-NonCommercial-NoDerivatives» 4.0, а примеры кода – по лицензии Apache 2.0. Подробнее см. Условия использования.