Докажите, что для всех простых чисел $%p > 2000$% сумма $%1 + 2^{2000} + 3^{2000} + ... + (P-1)^{200}$% делится на $%p$%.

задан 27 Май '15 10:48

изменен 27 Май '15 16:33

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

@zalan, Если вам дан исчерпывающий ответ, отметьте его как верный (нажмите на галку рядом с выбранным ответом).

(27 Май '15 16:33) Виталина
10|600 символов нужно символов осталось
2

Рассмотрим такой вспомогательный факт: для любого натурального $%k$% существуют целые числа $%a_1$%, ... , $%a_k$% такие, что имеет место тождество $$n^k=a_1C_n^1+a_2C_n^2+\cdots+a_kC_n^k$$ для всех натуральных $%n$%. Здесь имеется в виду, что $%C_n^m=0$% при $%n < m$%.

Действительно, $%n^1=n=C_n^1$%; $%n^2=n+(n^2-n)=C_n^1+2C_n^2$%, и далее по индукции. При $%k > 2$% рассматриваем разность $%n^k-k!\cdot C_n^k$%, равную $%n^k-n(n-1)\ldots(n-(k-1))$%, где старшие члены $%n^k$% сокращаются, и получается многочлен с целыми коэффициентами от $%n^{k-1}$%, ... , $%n$% (свободного члена не будет). А эти степени мы уже умеем раскладывать по сочетаниям в силу предположения индукции.

Явный вид коэффициентов нам здесь не нужен -- важно, что они целые.

Положим $%k=2000$%. Заметим, что $%p > k+1$%, так как 2001 -- составное число. Сумму $%1^k+2^k+\cdots+(p-1)^k=\sum\limits_{n=1}^{p-1}n^k$% мы можем записать как $%a_1\sum\limits_{n=1}^{p-1}C_n^1+\cdots+a_k\sum\limits_{n=1}^{p-1}C_n^k$%. Заметим, что $%C_m^m+C_{m+1}^m+\cdots+C_n^m=C_{n+1}^{m+1}$%, что легко выводится из свойств треугольника Паскаля. Следовательно, мы имеем дело с суммой $%a_1C_p^2+a_2C_p^3+\cdots+a_kC_p^{k+1}$%.

Остаётся заметить, что число $%C_p^m=\frac{p!}{m!(p-m)!}$%, будучи целым, делится на $%p$% при любом простом $%p$% для всякого $%m$% от $%1$% до $%p-1$%, так как множитель $%p$% в числителе не сокращается ни с чем в знаменателе. В итоге мы получили, что вся сумма делится на $%p$%.

ссылка

отвечен 27 Май '15 13:21

изменен 27 Май '15 13:22

10|600 символов нужно символов осталось
2

Название вопроса неудачное - здесь не сумма простых чисел.

Запишем $%P_m(n)=\sum_{k=1}^nk^m$% через многочлен Бернулли: $$P_m(n)=\sum_{k=1}^nk^m=\frac1{m+1}\left(B_{m+1}(n+1)-B_{m+1}(1)\right).$$ Поскольку $$P_m(0)=\frac1{m+1}\left(B_{m+1}(1)-B_{m+1}(1)\right)=0,$$ то многочлен $%P_m(n)$% делится на $%n$%.

Из формулы $$B_m(x)=\sum_{i=0}^m\frac{1}{i+1}\sum_{j=0}^i(-1)^jC_i^j(x+j)^m$$ следует, что знаменатели коэффициентов многочлена Бернулли не делятся на простое $%p>m+1$%.

Поэтому $%P_{2000}(p-1)=P_{2000}(p)-p^{2000}$% делится на простое $%p>2000$%.

ссылка

отвечен 27 Май '15 14:00

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×91

задан
27 Май '15 10:48

показан
1894 раза

обновлен
27 Май '15 16:33

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru