Вспомогательная страница к пункту ☞ Теорема Эйлера.
Теорема [Эйлер]. Для любых натуральных взаимно простых $ A_{} $ и $ M_{}>1 $ выполняется:
$$ A^{\phi(M)}\equiv 1 \pmod{M} \ , $$ здесь $ \phi $ означает функцию Эйлера.
Доказательство. Пусть известно каноническое разложение числа $ M_{} $: $$ M=p_1^{{\mathfrak m}_1}p_2^{{\mathfrak m}_2}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}} \ . $$ Тогда из теоремы Эйлера следует, что $$ \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} $ по формуле бинома Ньютона: $$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}\} .$$ Тогда справедливы (сравнение можно возводить в степень, см. теорему ☞ ЗДЕСЬ ) и сравнения $$ 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 $, приведенная ☞ ЗДЕСЬ, позволяет перемножить модули: $$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} \ .$$ ♦
Обобщенной функцией Эйлера называется функция $ 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} $ — наименьшее общее кратное. Очевидно, что $ 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} \} \ .$$ Теорема 4 позволяет перемножить модули, что и влечет за собой справедливость доказываемого сравнения. ♦