Фольклор

[Edward_Tur]

Для каждого $k>1$ найти наибольшее число $f(k)$ такое, что $n^k-n$ делится на $f(k)$ для всех натуральних $n$.

[Руст]

Другими словами $f(k)=lcm(2^k-1,3^k-1,5^k-1,7^k-1,...)$.
Мне кажется здесь эту задачу уже решали и находили более явный вид для $f(k)$.

[Профессор Снэйп]

$lcm$ --- это, вроде, НОК. А надо НОД.

[Руст]

Совершенно верно, описался.

Руст писал(а):

Другими словами $f(k)=gcd(2^k-1,3^k-1,5^k-1,7^k-1,...)$.
Мне кажется здесь эту задачу уже решали и находили более явный вид для $f(k)$.

[Kid Kool]

Руст писал(а):

Другими словами $f(k)=lcm(2^k-1,3^k-1,5^k-1,7^k-1,...)$.

Нет. Если f(k) делит $2^k-2$, то оно не может делить $2^k-1$ (если это не 1, конечно же).

[Edward_Tur]

Более узкая задача:
Найти все $k>1$ такие, что $n^k-n$ делится на $2^k-2$ для всех натуральних $n$.

[Руст]

Я извиняюсь за свою небрежность. Задача сводится к вычислению
$X(k)=gcd(n^k-n, \ n\in N)$. Рассмоьрим простое число p, ясно что $p^k-p$ делится только на простое число р только в первой степени $(k>1)$. Пусть a образующая мультипликативной группы $(Z/pZ)^*$. Тогда $p|a^k-a$ тогда и только тогда, когда $p-1|k-1$. Таким образом

$$X(k)=\prod_{p-1|k-1}p.$$

Более узкая задача на самом деле даже посложнее исходной и эквивалентно (в силу решения первой) условию, что $2^k-2$ бесквадратно и каждый простой делитель $p|2^k-2$ удовлетворяет условию $p-1|k-1$ (т.е. 2 образующая по модулю р). С учётом первого условия, второе эквивалентно $\phi(2^k-2)|k-1$. Но последнему условию удовлетворяет только k=2,3.

[Edward_Tur]

А $k=5$?

[Руст]

Руст писал(а):

С учётом первого условия, второе эквивалентно $\phi(2^k-2)|k-1$. Но последнему условию удовлетворяет только k=2,3.

Сделал ошибочное заключение. Вытекает только

$$lcm(p-1|| p|2^k-2)|k-1$$

.
Обозначим $l=k-1$. Тогда надо показать, что при $l>4$ у числа $2^l-1$ имеется простой делитель p, такой что p-1 не делит l. Количество нечётных простых p, удовлетворяющих этому условию не больше чем $2$ умножить на нечётных делителей $l'$ ($l=2^ml', \ l'$ нечётное) не превосходящих $\sqrt{l'}, т.е. не больше чем $[\sqrt{l'}]-1$. При $k>M$ произведение $[\sqrt k]$ простых чисел не превосходящих k меньше чем $2^{k-1}-1$.