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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:17, 14 мая 2016.
(Новая страница: «== Основные определения и утверждения== <math>~ f(x0 \equiv 0(mod~n)</math>, где <math>~ deg f(x) = n, f(x)</math> - много…»)
 
м
 
Строка 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

Основные определения и утверждения

, где - многочлен, не произвольная функция.

TemplateTheoremIcon.svg Теорема Утверждение
Если - попарно взаимно простые числа, , тогда

1

2 Количество решений:
Доказательство

Рассмотрим

1 Пусть решение (1) . Из свойств сравнений известно, что НОК, а так как все взаимно просты .

2 Если больше решений нет. Посчитаем иначе - как одно из решений (2). Тогда:


Согласно КТО эта система имеет решение выпишем его: , где зависит от также решение сравнения (1).

Посчитаем, сколько таких решений:

Допустим

Следовательно, наборы взяты из одного класса, а значит


Это утверждение позволяет свести к решению в случае . Далее этот случай сведем к .

TemplateExampleIcon.svg Пример Пример
Возьмем



Сведение решения сравнения по примарному модулю к простому

Научимся решать систему по примарному модулю

Можно свести к решению

Пусть решение это означает, что:

решение

Пусть найдено решение сравнения :

- решение , из определения сравнимости

Какие нужно взять , чтобы удовлетворять сравнению?

TemplateLemmaIcon.svg Лемма «Утверждение»
- разложение в ряд Тейлора


Определим

Если собрать коэффициенты при (после применения формулы бинома Ньютона к :

то получим то же значение, что и в случае производной в матанализе.

Перепишем функцию по-другому:

Очевидно, пришли к виду:

, и оно имеет решение, тогда

Возможны следующие варианты:

- проверим, будет ли это решение удовлетворять .

так как

Тогда

где . Получим, что



удовлетворяет (т.е. все удовлетворяют )