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

${\displaystyle ~ f(x) \equiv 0(mod~n)}$, где ${\displaystyle ~degf(x)=n,f(x)}$ - многочлен, не произвольная функция.

Теорема Утверждение
Если ${\displaystyle ~m_{1},\ldots ,m_{r}}$ - попарно взаимно простые числа, ${\displaystyle ~m=\prod _{i=1}^{r}m_{i}}$, тогда 1 ${\displaystyle ~f(x)\equiv 0(mod~m)~~(1)}$ ${\displaystyle ~{\Bigg \{}{\begin{matrix}f(x)\equiv 0(mod~m_{1})\\\ldots \\f(x)\equiv 0(mod~m_{r})\end{matrix}}(2)}$ 2 Количество решений: ${\displaystyle ~\chi =\chi _{1}\ldots \chi _{r}}$
Доказательство
Рассмотрим 1 Пусть ${\displaystyle ~x_{0}-}$ решение (1) ${\displaystyle ~\Rightarrow f(x_{0})=0(mod~m)\Leftrightarrow m|f(x_{0})\forall m_{i}|m|f(x_{0});\forall m_{i}|f(x_{0})\Leftrightarrow f(x_{0})\equiv 0(mod~m_{i}),i={\overline {1,r}}}$. Из свойств сравнений известно, что ${\displaystyle ~f(x_{0})\equiv 0(mod~m_{i}),m=}$ НОК${\displaystyle ~[m_{1},\ldots m_{r}]}$, а так как все ${\displaystyle ~m_{i},i={\overline {1,r}}}$ взаимно просты ${\displaystyle ~\Rightarrow m=\prod _{i=1}^{n}m_{i}}$. 2 Если ${\displaystyle ~\exists x:=0\Rightarrow x=x_{1},\ldots x_{r}=0\Rightarrow }$ больше решений нет. Посчитаем иначе - ${\displaystyle ~a_{1}\ldots a_{r}-}$ как одно из решений (2). Тогда: ${\displaystyle ~ \left\{ \begin{matrix} x \equiv a(mod~m_1) \\ x \equiv a_2(mod~m_2) \\ \ldots \\ x \equiv a_r(mod~m_r) \end{matrix} \right. ,\ (m_i, m_j) = 1 }$ Согласно КТО эта система имеет решение ${\displaystyle ~\Rightarrow }$ выпишем его: ${\displaystyle ~x_{0}=a_{1}e_{1}+a_{2}e_{2}+\ldots a_{r}l_{r}(mod~m)}$, где ${\displaystyle ~e_{1},\ldots e_{r}}$ зависит от ${\displaystyle ~m_{i}.x_{o}-}$ также решение сравнения (1). Посчитаем, сколько ${\displaystyle ~\exists }$ таких решений: ${\displaystyle ~\chi \leq \chi _{1}\ldots \chi _{r}}$ Допустим ${\displaystyle ~x'=a_{1}'l_{1}+\ldots +a_{r}'l_{r}(mod~m)}$ ${\displaystyle ~x_{0}=x'(mod~m)\Rightarrow a_{j}e_{j}=a_{j}e_{j}(mod~m)\Leftrightarrow a_{j}=a_{j}'(mod~m_{j})}$ Следовательно, наборы ${\displaystyle ~a_{j},a_{j}'}$ взяты из одного класса, а значит ${\displaystyle ~\chi =\prod _{i=1}^{r}\chi _{i}}$

Это утверждение позволяет свести ${\displaystyle ~m=p_{1}^{\alpha _{1}}\cdot \ldots p_{r}^{\alpha _{r}}}$ к решению в случае ${\displaystyle ~m=p^{\alpha }}$. Далее этот случай сведем к ${\displaystyle ~m=p}$.

Пример Пример

Возьмем ${\displaystyle ~ f(x) = 3x^36+x^2 + x +10 = 0 (mod~15); 15 = 3(m_1)\cdot 5(m_2)}$ ${\displaystyle ~(2):\left\{{\begin{matrix}f(x)\equiv 0(mod~3)\\f(x)\equiv 0(mod~5)\end{matrix}}\right.\to (2):\left\{{\begin{matrix}x+1=0(mod~3)\\3x^{3}+x^{2}+x=0(mod~5)\end{matrix}}\right.\Rightarrow \left\{{\begin{matrix}x=-1(mod~3)\\x=0,1,2(mod~5)\end{matrix}}\right.\Rightarrow {\begin{matrix}\chi =1\\\chi =3\end{matrix}}}$ ${\displaystyle ~\chi =\chi _{1}\cdot \chi _{2}=1\cdot 3=3}$ ${\displaystyle ~\left\{{\begin{matrix}x\equiv a_{1}(mod~3)\\x\equiv a_{2}(mod~5)\end{matrix}}\right.\to x_{0}=(-5)a_{1}+6a_{2}=e_{1}a_{1}+e_{2}a_{2}}$ ${\displaystyle ~x_{1}=(-5)(-1)+6\cdot 0=5(mod~15)}$ ${\displaystyle ~x_{0}=(-5)(-1)+6\cdot 1=11(mod~15)}$ ${\displaystyle ~x_{0}=(-5)(-1)+6\cdot 2=2(mod~15)}$

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

${\displaystyle ~f(x)\equiv 0(mod~p^{\alpha });\alpha >1}$${\displaystyle \to {\color {Maroon}(1)}}$

Можно свести к решению ${\displaystyle ~f(x)\equiv 0(mod~\varphi )\to {\color {Maroon}(2)}}$

Пусть ${\displaystyle ~x-0-}$ решение ${\displaystyle {\color {Maroon}(1)}}$ это означает, что:

${\displaystyle ~f(x_{0})=0(mod~p^{\alpha })\Leftrightarrow p^{\alpha }|f(x_{0})}$

${\displaystyle ~p|f(x_{0})\Rightarrow f(x_{0})=0(mod~p)}$

${\displaystyle ~x_{0}-}$ решение ${\displaystyle {\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)}$${\displaystyle \to {\color {Maroon}(2)}}$

${\displaystyle ~(p\to p^{2}\to p^{3}\to p)}$

Пусть найдено решение сравнения ${\displaystyle {\color {Maroon}(2)}}$:

${\displaystyle ~x\equiv x_{1}(mod~p)}$ - решение ${\displaystyle {\color {Maroon}(2)}}$, из определения сравнимости ${\displaystyle ~x=x_{1}+p\cdot t_{1},t_{1}\in \mathbb {Z} }$

${\displaystyle ~f(x)\equiv 0(mod~p^{2})}$

Какие нужно взять ${\displaystyle ~x}$, чтобы удовлетворять сравнению?

${\displaystyle ~f(x_{1}+p\cdot t_{1})\equiv 0(mod~p^{2})}$

Лемма «Утверждение»
${\displaystyle ~f(x+h)=f(x)+h\cdot f'(x)+{\frac {h^{2}}{2!}}f''(x)+\ldots +{\frac {h^{n}}{n!}}f^{(n)}(x)}$ - разложение в ряд Тейлора

${\displaystyle ~f(x)=a_{0}x^{n}+a_{1}x^{n-1}+\ldots +a_{n}}$

${\displaystyle ~f'(x0=na_{0}x^{n-1}+\ldots +a_{n-1}}$

Определим ${\displaystyle ~\lim _{h\to 0}{\frac {f(x+h)-f(x)}{h}}}$

Если собрать коэффициенты при ${\displaystyle ~h}$ (после применения формулы бинома Ньютона к ${\displaystyle ~f(x+h)}$:

${\displaystyle ~f(x+h)=a_{0}(x+h)^{n}+a_{1}(x+h)^{n-1}+\ldots }$

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

${\displaystyle ~\left\{{\begin{matrix}f'(x)=na_{0}x^{n-1}+\ldots +a_{n-1}\\\cdot \\\cdot \\\cdot \\f^{n}(x)=n!a_{0}\end{matrix}}\right.}$

${\displaystyle ~f(x_{1}+pt_{1})\equiv 0(mod~p^{2})\to f(x_{1})+pt_{1}f'(x_{1})+\underbrace {{\frac {(pt_{1})^{2}}{2!}}f''(x)} _{\equiv 0(mod~p)}+\ldots \to f(x_{1})+pt_{1}f'(x_{1})\equiv 0(mod~p^{2})}$

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

${\displaystyle {\color {Maroon}(*)}}$${\displaystyle ~f'(x_{1})\cdot t_{1}=-{\frac {f(x_{1})}{p}}(mod~p)}$

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

${\displaystyle ~ax\equiv b(mod~m)}$, и оно имеет решение, тогда ${\displaystyle ~(a,m)|b}$

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

${\displaystyle {\color {Maroon}(A)}}$

${\displaystyle ~(p_{1}f'(x))=1,p\not |f(x_{1})}$

${\displaystyle ~t_{1}=t'(mod~p),t_{1}=t'+pt_{2},t_{2}\in \mathbb {Z} }$

${\displaystyle ~x=x_{1}+p(t'+pt_{2})=\underbrace {x_{2}} _{=x_{1}+pt'}+p_{1}^{2}t_{2}\Rightarrow x\equiv x_{2}(mod~p^{2})}$ - проверим, будет ли это решение удовлетворять ${\displaystyle ~p^{3}}$.

${\displaystyle ~f(x)\equiv 0(mod~p^{3});f(x_{2}+p^{2}t_{2})\equiv 0(mod~p^{3})}$

${\displaystyle ~ f(x_2) + p^2t_2f'(x_0) = 0\ (mod~p^3)}$

${\displaystyle ~f'(x_{2})t_{2}=-{\frac {f(x_{2})}{p^{2}}}(mod~p){\color {Maroon}(*')}}$

так как ${\displaystyle ~x_{1}\equiv x_{2}(mod~p)\to f(x_{1})=f(x_{2})(mod~p)}$

${\displaystyle ~x\equiv x_{2}(mod~p^{2})}$

Тогда ${\displaystyle ~t_{2}=t_{2}'(mod~p)}$

${\displaystyle ~x=x_{2}+p^{2}(t_{2}'+pt_{3})=x_{3}+p^{3}t_{3},}$

где ${\displaystyle ~x_{3}=(x_{2}+p^{2}t_{2}')}$. Получим, что ${\displaystyle ~x=x_{3}(mod~p^{3})}$

${\displaystyle {\color {Maroon}(B)}}$

${\displaystyle ~p|f'(x),p\not |()}$

${\displaystyle {\color {Maroon}(C)}}$

${\displaystyle ~p|f'(x_{1}),p|()-}$ удовлетворяет ${\displaystyle ~\forall t_{1}}$ (т.е. все ${\displaystyle ~t_{1}}$ удовлетворяют ${\displaystyle ~p^{2}}$)

${\displaystyle ~m=p_{1}^{\alpha _{1}}\ldots p_{r}^{\alpha _{r}}\to m=p^{\alpha }\to m=p}$