tag:
функция_Эйлера
31
Теорема
§

Мультипликативность функции Эйлера

\[\begin{array}{l} {\text{Для любых взаимно простых чисел }}m{\text{ и }}n \hfill \\ \varphi \left( {mn} \right) = \varphi \left( m \right) \cdot \varphi \left( n \right). \hfill \\ \end{array}\]
32
утверждение
§
\[\varphi \left( {{p^n}} \right) = {p^n} - {p^{n - 1}}\]
33
Теорема
§

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

\[\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}\]
31
§
\[\begin{array}{l} {\text{Функция Эйлера }}\varphi \left( n \right){\text{ - мультипликативная арифметическая функция}}{\text{,}} \hfill \\ {\text{равная количеству натуральных чисел}}{\text{, меньших }}n{\text{ и взаимно простых}} \hfill \\ {\text{с ним}}{\text{.}} \hfill \\ \end{array}\]
46
§
\[\sum\limits_{d|n} {\varphi \left( d \right)} = n\]
48
§
\[\begin{array}{l} \varphi \left( n \right) = \sum\limits_{d|n} {d \cdot \mu \left( {\frac{n}{d}} \right)} {\text{,}} \hfill \\ {\text{где }}\mu \left( m \right){\text{ - функция Мёбиуса}} \hfill \\ \end{array}\]
1411.
\[\begin{array}{l} {\text{Пусть }}\varphi \left( n \right){\text{ - функция Эйлера}}{\text{. Известно}}{\text{, что }}\varphi \left( {{p_1} \cdot {p_2} \cdot {p_3} \cdot {p_4} \cdot {p_5} \cdot {p_6}} \right) = {2^{31}}{\text{,}} \hfill \\ {\text{где }}{p_i}{\text{ - различные простые числа}}{\text{. Найдите }}{p_i}. \hfill \\ \end{array}\]
1414.
\[{\text{Докажите}}{\text{, что при любом натуральном }}k{\text{ не существует }}n{\text{ такого}}{\text{, что }}\varphi \left( n \right) = 2 \cdot {7^k}.\]