Лёгкая, но очень симпатичная задачка на делимость

[Xenia1996]

Найдётся ли натуральное $n$, при котором $n^n+(n+1)^n+(n+2)^n+(n+3)^n$ делится нацело на 2011?

[age]

$n=3015$

[Xenia1996]

age в сообщении #440170 писал(а):

$n=3015$

Несомненно.
$3015\equiv 1004 \pmod{2011}, 3018\equiv -1004\pmod{2011},$
$3016\equiv 1005 \pmod{2011}, 3017\equiv -1005\pmod{2011}$

При возведении в нечётную степень (3015-ую) плюсы и минусы сокращаются.

[Sonic86]

$f(n)=n^n+...+(n+3)^n \mod p$ имеет период оснований $p$, а период степеней $p-1$, значит $f(n)$ имеет период $p(p-1)$. Поскольку $p,p-1$ взаимно просты, то можно для любой пары остатков $r,ы$ подобрать такое $n$, что $n \equiv r \pmod p$ и $n \equiv s \pmod {p-1}$, и для соответствующего класса вычетов уравнение примет вид $r^s+(r+1)^s+(r+2)^s+(r+3)^s \equiv 0 \pmod p$. Возьмем для удобства $s=1$, т.е. $n=(p-1)m+1$, тогда получим уравнение $r+(r+1)+(r+2)+(r+3) \equiv 0 \pmod p$, дальше понятно

[Equinoxe]

Sonic86, это слишком сложно для данной задачи, да к тому же применимо лишь к простым $p$
http://e-science.ru/forum/index.php?showtopic=30416
Что Вы можете сказать насчет последнего вопроса?

[Sonic86]

Equinoxe писал(а):

Sonic86, это слишком сложно для данной задачи, да к тому же применимо лишь к простым $p$

я лишь хотел идею ясно выразить.
Можно было написать просто: $n=m(p-1)+1$ + МТФ.
Сейчас по ссылке посмотрю...

-- Сб апр 30, 2011 18:22:53 --

Equinoxe писал(а):

http://e-science.ru/forum/index.php?showtopic=30416
Что Вы можете сказать насчет последнего вопроса?

Ответил. 9 не делит $n+(n+1)^n$.

[Equinoxe]

Sonic86, ответила, делит при n = 13 :)

[age]

Ладно! Переформулируем (действительно олимпиадно): натуральное $n$, при котором $n^n+(n+1)^n+(n+2)^n$ делится нацело на 2011?

[Sonic86]

Equinoxe писал(а):

Sonic86, ответила, делит при n = 13 :)

Да, я наврал

Xenia1996 писал(а):

Но можно ли утверждать, что для любого натурального $m$ и нечётного $k$ найдётся такое натуральное $n$, что $n^n+(n+1)^n+\dots +(n+m-1)^n$ делится нацело на $k$?

(в цитате исправил $m$ на $m-1$ для удобства)
Похоже, что это уже нелегкая задачка, если я не торможу. Если решать в лоб для $k=p^a$, то получается, что при $a=1$ задача имеет решения, поскольку период функции $p(p-1)$ и она за этот период пробегает всевозможные суммы $m$ последовательных степеней $n^r+...+(n+m-1)^r$ и за счет этого имеет много решений (число их не считал). Для $a>1$ период $T_a=p^a(p-1)$ делит предыдущий период, значит можно строить рекуррентные формулы для решений сравнения.
Пусть мы хотим решить сравнение $n^n+...+(n+m-1)^n \equiv 0 \pmod{p^{a+1}}$. Тогда должно быть верно $n^n+...+(n+m-1)^n \equiv 0 \pmod{p^a}$. Пусть решение предыдущего сравнения - $n \equiv t \pmod {p^a}$, тогда искомое решение имеет вид $n \equiv t+qp^a(p-1) \pmod {p^{a+1}}, 0 \leq q < p$. Подставляем, учитываем $b^{p^{a}(p-1)} \equiv 1 \pmod {p^{a+1}}$ получаем:
$(t-qp^a)^t+...+(t-qp^a+m-1)^t \equiv 0 \pmod{p^{a+1}}$
Возводим в степень, выделяя предыдущее решение:
$(t^t+...+(t+m-1)^t) -p^aqt(t^{t-1}+...+(t+m-1)^{t-1}) \equiv 0 \pmod{p^{a+1}}$
Это сравнение не имеет решений, только если предыдущее решение $(t^t+...+(t+m-1)^t) \not \equiv 0 \pmod{p^{a+1}}$, и коэффициент $t^{t-1}+...+(t+m-1)^{t-1}\equiv 0 \pmod p$. И вот дальше непонятно ничего. Коэффициент плохо связан с исходным решением, поэтому он редко делится на $p$, и при этом, в зависимости, кажется, от $\gcd (n; p-1)$ исходные решения размножаются с некоторым коэффициентом (его удобно смотреть для $m=3, p=5, a=1;2;3$). Для $m=1; p=3$ этот коэффициент размножения равен $1$, но легко доказать, что следующее решение может быть построено всегда. Для $m=2; p=5$ он равен $2$, но некоторые ветви роста прерываются. В итоге - непонятно. Хотя исходное утверждение выглядит очень вероятно.

-- Сб апр 30, 2011 21:04:11 --

Для получения ощущения еще более полного тупика можно посмотреть сюда:
topic39464.html
там задача представляет собой обобщение другой олимпиадной задачи.

[age]

age в сообщении #440357 писал(а):

Ладно! Переформулируем (действительно олимпиадно)

Ничего не олимпиадно. Такая же ерунда. (посмотрел решение Equinoxe на другом форуме в одну строчку)