tag:
сравнения_по_модулю
Теорема
§

Теорема Вильсона

\[\begin{array}{l} {\text{Натуральное число }}p{\text{ является простым тогда и только тогда}}{\text{,}} \hfill \\ {\text{когда }}\left( {p - 1} \right)! + 1{\text{ делится на }}p. \hfill \\ \end{array}\]
Теорема
§

Малая теорема Ферма

\[{\text{Если }}p{\text{ - простое число и }}a{\text{ - целое число}}{\text{, не делящееся на }}p{\text{, то }}{a^{p - 1}} \equiv 1{\text{ }}\left( {\bmod p} \right).\]
Теорема
§

Теорема Эйлера

\[\begin{array}{l} {\text{Если }}a{\text{ и }}m{\text{ взаимно просты}}{\text{, то}} \hfill \\ {a^{\varphi \left( m \right)}} \equiv 1{\text{ }}\left( {\bmod m} \right). \hfill \\ \end{array}\]
Теорема
§

Критерий Эйлера

\[\begin{array}{l} {\text{Пусть }}p > 2{\text{ - простое число}}{\text{. Число }}a{\text{, взаимно простое с }}p{\text{, является квадратичным}} \hfill \\ {\text{вычетом по модулю }}p{\text{ тогда и только тогда}}{\text{, когда}} \hfill \\ {a^{\frac{{p - 1}}{2}}} \equiv 1{\text{ }}\bmod p \hfill \\ {\text{и является квадратичным невычетом по модулю }}p{\text{ тогда и только тогда}}{\text{, когда}} \hfill \\ {a^{\frac{{p - 1}}{2}}} \equiv - 1{\text{ }}\bmod p. \hfill \\ \end{array}\]
\[\begin{array}{l} {\text{Пусть требуется решить систему сравнений}} \hfill \\ \left\{ \begin{array}{l} x \equiv {r_1}{\text{ }}\left( {\bmod {m_1}} \right) \hfill \\ x \equiv {r_2}{\text{ }}\left( {\bmod {m_2}} \right) \hfill \\ ... \hfill \\ x \equiv {r_n}{\text{ }}\left( {\bmod {m_n}} \right) \hfill \\ \end{array} \right. \hfill \\ {\text{Система имеет единственное решение }}x \equiv {x_0}\left( {\bmod M} \right){\text{, где}} \hfill \\ M = {m_1} \cdot {m_2} \cdot ... \cdot {m_n},{\text{ }}{x_0} = \sum\limits_{i = 1}^n {{M_i}{y_i}{r_i}} ,{\text{ }}{M_i} = \frac{M}{{{m_i}}},{\text{ }}{M_i}{y_i} \equiv 1\left( {\bmod {m_i}} \right). \hfill \\ \end{array}\]
\[{\text{Докажите}}{\text{, что 6}}{{\text{4}}^{25}} + {48^{17}}{\text{ делится на 7}}{\text{.}}\]
\[{\text{Известно}}{\text{, что }}\left( {{a^{12}} + {b^{12}}} \right) \vdots 3.{\text{ Докажите}}{\text{, что }}ab \vdots 9.\]
\[{\text{Известно}}{\text{, что }}\left( {{a^{10}} + {b^{10}}} \right) \vdots n{\text{ и }}\left( {{a^{107}} + {b^{107}}} \right) \vdots n.{\text{ Докажите}}{\text{, что }}\left( {{a^{2007}} + {b^{2007}}} \right) \vdots n.\]
\[{\text{Докажите}}{\text{, что }}{5^{2n + 1}} + {2^{n + 4}} + {2^{n + 1}}{\text{ кратно }}23.\]
\[\begin{array}{l} {\text{Докажите}}{\text{, что среди чисел вида }}{4^n} + {4^m}{\text{ нет ни одного квадрата}} \hfill \\ {\text{натурального числа}}{\text{.}} \hfill \\ \end{array}\]
Докажите, что квадрат нечётного числа при делении на 8 даёт в остатке 1.
\[1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{{p - 1}} \equiv 0{\text{ }}\left( {\bmod {p^2}} \right)\]
\[\begin{array}{l} {\text{Докажите}}{\text{, что }}{1^k} + {2^k} + ... + {\left( {p - 1} \right)^k} \equiv 0{\text{ }}\left( {\bmod p} \right){\text{, если }}p - 1\not |k{\text{,}} \hfill \\ {\text{и }} - 1\left( {\bmod p} \right){\text{, если }}p - 1|k. \hfill \\ \end{array}\]
\[\begin{array}{l} {\text{Доказать для поля характеристики }}p: \hfill \\ {\left( {a - b} \right)^{p - 1}} = \sum\limits_{j = 0}^{p - 1} {{a^j}{b^{p - 1 - j}}} \hfill \\ \end{array}\]
\[\begin{array}{l} {\text{Решить систему сравнений:}} \hfill \\ \left\{ \begin{array}{l} x \equiv 2\left( {\bmod 3} \right) \hfill \\ x \equiv 3\left( {\bmod 5} \right) \hfill \\ x \equiv 1\left( {\bmod 7} \right) \hfill \\ \end{array} \right. \hfill \\ \end{array}\]