28
\[x \to {x^{ - 1}}{\text{ - биекция в }}\mathbb{Z}_p^ \times \]
29

\[\begin{array}{l} {\text{Если }}x{\text{ пробегает полную систему вычетов по модулю }}p{\text{ и }}\left( {a,p} \right) = 1, \hfill \\ {\text{то }}ax{\text{ также пробегает полную систему вычетов по модулю }}p. \hfill \\ \end{array}\]

31
§
\[\begin{array}{l} {\text{Функция Эйлера }}\varphi \left( n \right){\text{ - мультипликативная арифметическая функция}}{\text{,}} \hfill \\ {\text{равная количеству натуральных чисел}}{\text{, меньших }}n{\text{ и взаимно простых}} \hfill \\ {\text{с ним}}{\text{.}} \hfill \\ \end{array}\]
1414.
\[{\text{Докажите}}{\text{, что при любом натуральном }}k{\text{ не существует }}n{\text{ такого}}{\text{, что }}\varphi \left( n \right) = 2 \cdot {7^k}.\]
1415.
\[{\text{Докажите}}{\text{, что если }}{x^{{2^k}}} + 1 \equiv 0\left( {\bmod p} \right){\text{, то }}p \equiv 1\left( {\bmod {2^{k + 1}}} \right).\]
1395.
\[{\text{Решить в натуральных числах уравнение }}{2^k} - {5^m} = 3.\]
1529.
\[{\text{Пусть }}p{\text{ и }}q{\text{ - простые числа}}{\text{. Докажите}}{\text{, что }}{p^{q - 1}} + {q^{p - 1}} - 1{\text{ делится на }}p \cdot q.\]
1683.
\[\begin{array}{l} {\text{Пусть }}p{\text{ - нечётное простое число}}{\text{. Докажите}}{\text{, что простые делители}} \hfill \\ {\text{чисел }}\frac{{{a^p} - 1}}{{a - 1}}{\text{ и }}\frac{{{a^p} + 1}}{{a + 1}}{\text{ сравнимы с единицей по модулю }}p. \hfill \\ \end{array}\]
1682.
\[\begin{array}{l} {\text{Пусть }}p{\text{ - нечётное простое и }}f\left( x \right) = \sum\limits_{k = 0}^{\frac{{p - 1}}{2}} {\left( {\begin{array}{*{20}{c}} p \\ {2k} \end{array}} \right){x^{2k}}} {\text{,}} \hfill \\ q{\text{ - нечётный простой делитель числа }}f\left( n \right),{\text{ }}n \in \mathbb{N}. \hfill \\ {\text{Докажите}}{\text{, что }}q \equiv 1\bmod p. \hfill \\ \end{array}\]
27
Теорема
§

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

\[\begin{array}{l} {\text{Натуральное число }}p{\text{ является простым тогда и только тогда}}{\text{,}} \hfill \\ {\text{когда }}\left( {p - 1} \right)! + 1{\text{ делится на }}p. \hfill \\ \end{array}\]
1434.
\[\begin{array}{l} {\text{Пусть }}q{\text{ - простое число}}{\text{. Докажите}}{\text{, что если }}p{\text{ - простой делитель}} \hfill \\ {\text{числа }}\frac{{{x^q} + {y^q}}}{{x + y}}{\text{, то }}p \equiv 1\left( {\bmod q} \right). \hfill \\ \end{array}\]
1429.
\[{\text{Пусть }}p = 2k + 1{\text{ - простое число}}{\text{. Докажите}}{\text{, что }}k{!^4} - 1{\text{ делится на }}p.\]
1435.
\[{\text{Докажите}}{\text{, что }}23{!^2} \equiv 1\bmod 47.\]
35
Теорема
§

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

\[\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}\]
35
§
\[\begin{array}{l} {\text{Пусть }}a{\text{ - целое число}}{\text{, и }}p{\text{ - простое число}}{\text{, отличное от 2}}{\text{.}} \hfill \\ {\text{Символ Лежандра }}\left( {\frac{a}{p}} \right){\text{ определяется следующим образом:}} \hfill \\ \left( {\frac{a}{p}} \right) = 0,{\text{ если }}a{\text{ делится на }}p; \hfill \\ \left( {\frac{a}{p}} \right) = 1,{\text{ если }}a{\text{ является квадратичным вычетом по модулю }}p; \hfill \\ \left( {\frac{a}{p}} \right) = - 1,{\text{ если }}a{\text{ является квадратичным невычетом по модулю }}p. \hfill \\ \end{array}\]
1317.
\[\begin{array}{l} {\text{Ненулевые квадратичные вычеты образуют подгруппу индекса 2}} \hfill \\ {\text{в мультипликативной группе кольца }}{\mathbb{Z}_p}. \hfill \\ \end{array}\]
1406.
\[{\text{Докажите}}{\text{, что 5 - квадратичный вычет по простому модулю }}p = 10k + 1.\]
1351.
\[\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}\]
1355.
\[\begin{array}{l} {\text{Пусть }}a,p \in \mathbb{N},{\text{ }}p{\text{ - простое}}{\text{, }}a{\text{ - первообразный корень по модулю }}p,{\text{ }}{p^2}\not |\left( {{a^{p - 1}} - 1} \right). \hfill \\ {\text{Докажите}}{\text{, что }}a{\text{ - первообразный корень по модулю }}{p^2}. \hfill \\ \end{array}\]
1407.
\[{\text{Докажите}}{\text{, что 2 не является первообразным корнем по простому модулю }}p = {n^4} + 1.\]
54
Теорема
§

Квадратичный закон взаимности

\[\begin{array}{l} {\text{Пусть }}p{\text{ и }}q{\text{ - различные нечётные простые числа}}{\text{, }}\left( {\frac{p}{q}} \right){\text{ - символ Лежандра}}{\text{.}} \hfill \\ {\text{Тогда}} \hfill \\ \left( {\frac{p}{q}} \right) \cdot \left( {\frac{q}{p}} \right) = {\left( { - 1} \right)^{\frac{{p - 1}}{2} \cdot \frac{{q - 1}}{2}}}. \hfill \\ {\text{Дополнения}}{\text{.}} \hfill \\ \left( {\frac{{ - 1}}{p}} \right) = {\left( { - 1} \right)^{\frac{{p - 1}}{2}}}. \hfill \\ \left( {\frac{2}{p}} \right) = {\left( { - 1} \right)^{\frac{{{p^2} - 1}}{8}}}. \hfill \\ \left( {\frac{a}{p}} \right) = \left( {\frac{a}{q}} \right){\text{, если }}p \equiv q\left( {\bmod 4a} \right). \hfill \\ \end{array}\]
1681.
\[\begin{array}{l} {\text{Докажите}}{\text{, что }}16{k^2} - 20k + 5{\text{ не имеет простых делителей}}{\text{,}} \hfill \\ {\text{сравнимых с 3 и 7 по модулю 10}}{\text{.}} \hfill \\ \end{array}\]