Простейшие понятия теории чисел

Теорема (Лагранж). Уравнение $f(x) \equiv 0\pmod p$, где $p\in \mathbb {P}$, не может иметь более, чем $\deg f$ решений, если только не все коэффициенты многочлена $f$ равны $0\pmod p$.

$\blacktriangle$
Допустим, что $f(x) = a_ n x^ n + \ldots + a_1 x + a_0$ и у уравнения $f(x) \equiv 0 \pmod p$ нашлось $n+1$ различное решение. Перепишем $f(x)$ в виде

$f(x) = b_ n (x-x_1)(x-x_2)\cdot \ldots \cdot (x-x_ n) +$ $b_{n-1}(x-x_1)\cdot \ldots \cdot (x-x_{n-1}) +$ $\ldots +$ $b_1(x-x_0) +$ $b_0$.

Подставим по очереди $x_1, \ldots , x_{n+1}$, получим $b_0\equiv 0, \ldots , b_ n\equiv 0 \pmod p$, противоречие.
$\blacksquare$

Теорема (Вильсон). $p\in \mathbb {P}\iff (p-1)! \equiv -1 \pmod p$.

$\blacktriangle$
($\Rightarrow$) $f(x) = (x-1)(x-2)\cdot \ldots \cdot (x-(p-1)) - (x^{p-1} - 1)$. $\deg f \leqslant p-2$.

У этого многочлена есть $p-1$ корней по mod  $p$. По Т. Лагранжа все коэффициенты этого многочлена $\equiv 0\pmod p \Rightarrow$ свободный член $= (-1)^{p-1}(p-1)! + 1 \equiv 0 \pmod p$.

($\Leftarrow$) Если $p=ab$, $2\leqslant a, b \leqslant p-1 \Rightarrow a, b$ содержатся в $(p-1)! \Rightarrow$ $(p-1)! \equiv 0\pmod p$. Исключение: 4, если $p$ — квадрат, но не 4, то там встречаются $a$ и $2a$.

Теорема (Китайская теорема об остатках). Если $m_1, \ldots , m_n$ — попарно взаимнопросты, то $\forall a_1, \ldots , a_ n$ система сравнений

$\begin{cases} x\equiv a_1\ (m_1),\\ x\equiv a_2\ (m_2)\\, \vdots \\x\equiv a_ n\ (m_ n). \end{cases}$

имеет единственное решение в диапазоне $[0; m_1\cdot \ldots \cdot m_ n)$.

$\blacktriangle$
Сопоставим каждому числу $x\in [0; m_1\cdot \ldots \cdot m_ n)$ набор его остатков

($x\text { mod } m_1, \ldots ,x\text { mod } m_ n$).

Заметим, что если $x' \neq x''$, то сопоставляемые им наборы разные.
$\newcommand{\divby}{\mathop{\smash{\vdots}}}$

Действительно, пусть $x'\text { mod } m_ i = x''\text { mod } m_ i \Rightarrow x'-x'' \divby m_ i \Rightarrow$ $x'-x'' \divby m_1\cdot \ldots \cdot m_ n$ (так как все $m_i$ взаимнопросты).

Значит, наше сопоставление иньективно. Т.к. чисел в диапазоне $[0; m_1\cdot \ldots \cdot m_ n)$ столько же, сколько рассматриваемых наборов остатков, то сопоставление — биекция.
$\blacksquare$