!!§!! Вспомогательная страница к пункту  <html>
  <font face="Times">
        <font color="#ff00ff" size="+2"> ☞

</font>
  </font>
</html> ((:modular#teorema_ehjlera Теорема Эйлера)).


!!Т!! **Теорема [Эйлер].** //Для любых натуральных взаимно простых// $ A_{} $ //и// $ M_{}>1 $ //выполняется//: 

$$
A^{\phi(M)}\equiv 1 \pmod{M}  \ , 
$$
//здесь// $ \phi $ //означает ((:numtheory#funkcija_ehjlera функцию Эйлера))//. 


**Доказательство.** Пусть известно каноническое разложение числа $ M_{} $:
$$
M=p_1^{{\mathfrak m}_1}p_2^{{\mathfrak m}_2}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}}  \ .
$$
Тогда из ((:numtheory#функция_эйлера теоремы Эйлера)) следует, что 
$$ \phi (M) =\prod_{j=1}^{\mathfrak r} p_j^{{\mathfrak m}_j-1}(p_j-1)\ .
$$ 
Докажем, что
$$
A^{p_j^{{\mathfrak m}_j-1}(p_j-1)} \equiv 1 \pmod{p_j^{{\mathfrak m}_j}} \ .  
$$
Действительно, из того, что $ \operatorname{HOD} (A,M)=1 $, следует, что $ A_{} $ не делится на 
$ p_{j} $, но тогда справедлива ((#теорема_ферма теорема Ферма)):
$$
A^{p_j-1} \equiv 1 \pmod{p_j} \ .  
$$
Покажем, что из этого сравнения следует:
$$
A^{p_j(p_j-1)} \equiv 1 \pmod{p_j^{2}} \ .  
$$
В самом деле, сравнение $ A^{p_j-1} \equiv 1 \pmod{p_j} $ эквивалентно утверждению, что
$ A^{p_j-1} - 1 $ делится на $ p_{j} $, т.е. существует $ q\in \mathbb Z $ такое, что 
$ A^{p_j-1} - 1=qp_j $. Возведем обе части равенства $ A^{p_j-1} = 1+qp_j $ в
степень $ p_{j} $ по формуле ((:binomial бинома Ньютона)):
$$A^{p_j(p_j-1)}=\left( A^{p_j-1} \right)^{p_j}=(1+qp_j)^{p_j}=$$
$$=1+ C_{p_j}^1\, qp_j+C_{p_j}^2\, q^2p_j^2+\dots+
C_{p_j}^{p_j-1}\, q^{p_j-1}p_j^{p_j-1}+q^{p_j}p_j^{p_j} \ ;
$$
все слагаемые, кроме первого, делятся на $ p_j^2 $.
Аналогичным приемом пользуемся и для доказательства общей формулы 
$$
A^{p_j^{{\mathfrak m}_j-1}(p_j-1)} \equiv 1 \pmod{p_j^{{\mathfrak m}_j}}  
 \quad npu \quad \forall
j\in \{1,\dots, {\mathfrak r}\} .$$
Тогда справедливы (сравнение можно возводить в степень, см. теорему  <html>
  <font face="Times">
        <font color="#ff00ff" size="+2"> ☞

</font>
  </font>
</html> ((#сравнения ЗДЕСЬ)) ) и сравнения
$$
A^{\phi(M)} \equiv 1 \pmod{p_j^{{\mathfrak m}_j}} \quad npu \quad \forall
j\in \{1,\dots, {\mathfrak r}\} \, ,
$$
поскольку $ \phi(M) $ делится нацело на $ p_j^{{\mathfrak m}_j-1}(p_j-1) $.
Теорема $ 4 $, приведенная  <html>
  <font face="Times">
        <font color="#ff00ff" size="+2"> ☞

</font>
  </font>
</html> ((:numtheory#взаимно_простые_числа ЗДЕСЬ)), позволяет перемножить модули:
$$A^{\phi(M)} \equiv 1 \pmod{\prod_{j=1}^{\mathfrak r} p_j^{{\mathfrak m}_j}}
\quad \iff \quad A^{\phi(M)} \equiv 1 \pmod{M} \ .$$
<html>
  <font face="Times">
        <font color="#ff00ff" size="+2">♦</font>
  </font>
</html>





**Обобщенной функцией Эйлера**  называется функция $ L(M) $,
определяемая для $ M=1 $ как $ L(1)=1 $, а при всех натуральных $ M>1 $ c каноническим
разложением
$$
M=p_1^{{\mathfrak m}_1}p_2^{{\mathfrak m}_2}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}}
$$
следующим образом:
$$
L(M) = \operatorname{HOK} \left(p_1^{{\mathfrak m}_1-1}(p_1-1),\ p_2^{{\mathfrak m}_2-1}(p_2-1),\ \dots,\, 
p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}-1}(p_{\mathfrak r}-1)  \right) \ ;
$$
здесь $ \operatorname{HOK} $ --- ((:numtheory#алгоритм_евклида наименьшее общее кратное)).
Очевидно, что $ L(M)=\phi(M) $ при $ M=p^{{\mathfrak m}} $ и что 
$ \phi(M) $ делится на $ L(M) $ при любых $ M_{} $.

!!П!! **Пример.**

$$ L(105840)=L(2^4\cdot 3^3 \cdot 5 \cdot 7^2)= \operatorname{HOK} \left(2^3 ,\, 
2\cdot 3^2,\, 4,\, 7\cdot 6\right)=2^3\cdot 3^2 \cdot 7 = 504 $$
при $ \phi(105840)= 24192 $ ;
$$
L(10291)=L(41\cdot 251)=\operatorname{HOK} (40,250)=1000 \quad npu \quad \phi(10291)=10000 ;
$$  
$$
L(49321)= \quad \quad  npu \quad \phi(49321)= \qquad \ .
$$ 

!!Т!! **Теорема.** 
//Для любых натуральных взаимно простых// $ A_{} $ //и// $ M>1 $ //выполняется// 

$$
A^{L(M)}\equiv 1 \pmod{M}  \ . 
$$

**Доказательство** фактически повторяет доказательство теоремы Эйлера. Вытащим из этого доказательства
следующее сравнение
$$
A^{p_j^{{\mathfrak m}_j-1}(p_j-1)} \equiv 1 \pmod{p_j^{{\mathfrak m}_j}}  
 \quad npu \quad \forall
j\in \{1,\dots, {\mathfrak r}\} .$$
Поскольку $ L(M) $ делится на любое из чисел $ p_j^{{\mathfrak m}_j-1}(p_j-1) $, то допустимо возведение в степень последнего сравнения:
$$
A^{L(M)} \equiv 1 \pmod{p_j^{{\mathfrak m}_j}}
\quad npu \ \forall j \in \{ 1,\dots,{\mathfrak r} \}  \ .$$
((:numtheory#vzaimno_prostye_chisla Теорема 4)) позволяет перемножить модули, что и влечет за собой
справедливость доказываемого сравнения. <html>
  <font face="Times">
        <font color="#ff00ff" size="+1">♦</font>
  </font>
</html>