Областная олимпиада по математике, 2009 год, 11 класс

Докажите, что для любого натурального числа $m$, имеющего делитель $n$, существует простое число $p$ такое, что $m^n-1$ делится на $p$, а число $m-1$ не делится на $p$.

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

Применим формулу разности $n$-ых степеней.

$m^n-1=(m-1)(m^{n-1}+m^{n-2}+\ldots+m+1)$.

Найдем НОД чисел $(m-1)$ и $(m^{n-1}+m^{n-2}+\ldots+m+1)$.

$((m-1),\,(m^{n-1}+m^{n-2}+\ldots+m+1))=$

$=((m-1),\,((m^{n-1}-1)+(m^{n-2}-1)+\ldots+(m-1)+n))=$

$=((m-1),\,n)=-1$.

Значит, числа $(m-1)$ и $(m^{n-1}+m^{n-2}+\ldots+m+1)$ взаимно простые, тогда простой делитель $p$ числа $(m^{n-1}+m^{n-2}+\ldots+m+1)$ является искомым.

А просто решить с помощью LTE?