Математикадан республикалық олимпиада, 2016-2017 оқу жылы, 9 сынып

$\mbox{ЕҮОБ}(a,p!)=1$ болатын натурал $a$ және жай $p$ саны берілген. ${{a}^{(p-1)!}}-1$ санының $p!$-ға бөлінетінін дәлелдеңіздер. ( Ануарбеков Т. )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Решение. По малой теореме Ферма ${{a}^{p-1}}\equiv 1 \pmod p$, следовательно ${{a}^{\left( p-1 \right)!}}\equiv 1\pmod p$. Пусть $\left( p-1 \right)!=q_1^{{\alpha _1}}q_2^{{\alpha _2}} \ldots q_k^{{\alpha _k}}$ — каноническое разложение числа ${(p-1)!}$. Так как $p-1\ge {{q}_{1}}-1$ и $(q_1^{\alpha _1},{{q}_{1}}-1)=1$, то $\left( p-1 \right)!\vdots {{q}_{1}}^{{{\alpha }_{1}}-1}\left( {{q}_{1}}-1 \right)=\varphi \left( {{q}_{1}}^{{{\alpha }_{1}}} \right)$.
По теореме Эйлера $a^{\varphi (q_1^{\alpha_1})} \equiv 1 \pmod { q_1^{\alpha_1}}$, следовательно ${{a}^{\left( p-1 \right)!}}\equiv 1 \pmod {q_1^{\alpha_1}}$. Аналогично для каждого $i=2,3,\ldots ,k$ получаем, что ${{a}^{\left( p-1 \right)!}}\equiv 1 \pmod{ q_i^{\alpha_i}}$. Значит, $${{a}^{\left( p-1 \right)!}}-1\vdots p \cdot q_1^{{\alpha _1}}q_2^{{\alpha _2}} \ldots q_k^{{\alpha _k}}=p!,$$ что и требовалось доказать.

Факт: пусть $n=p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}$, $p \in \mathbb{P}, (a,p)=1$, и $\lambda (n)=[ \phi (p_1^{\alpha_1}), \phi (p_2^{\alpha_2}), \phi (p_k^{\alpha_k})]$. Тогда $a^{\lambda (n)} \equiv 1 \mod n$ (1)

Из факта (1) выходит, что достаточно доказать $\lambda (p!) \mid (p-1)!$ Для этого докажем, что $V_q(\lambda (p!)) \le V_q((p-1)!), \forall q \in \mathbb{P}$.Пусть $p! =p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}$ - каноническое разложение числа $p!$. Тогда $V_q( \lambda (p!)) = max[ V_q( \phi (p_1^{ \alpha_1})), V_q(\phi (p_2^{\alpha_2})), \dots V_q(\phi (p_k^{\alpha_k})] = V_q(\phi (p_j^{\alpha_j}))$Но $\phi (p_j^{\alpha_j})$$= (p_j-1)(p_j^{\alpha_j-1})$ и очевидно $p_j^{\alpha_j-1}(p_j-1) \mid (p-1)! \rightarrow V_q(\lambda (p!)) \le V_q((p-1)!)$, ч.т.д.

Абзал аби мощь