Задачи олимпиад по математике

главная страница сайта Приглашение в мир математики
===============

ММ124 (4 балла)

Пусть S_n = 2 + 3 + 5 + 7 +\dots+ p_n - сумма n первых простых чисел.
Доказать, что S_n является простым тогда и только тогда, когда существует такое простое число q, что S_n + q кратно 2, 3, 5, \dots, p_n.

================

Решение

Приведу решение Виктора Филимоненкова.

1. Пусть такое число q для $S_n$ существует. Тогда $S_n$ не делится ни на одно из чисел $2, 3, \dots, p_n$. Действительно, если $S_n = p \cdot b$, где p - одно из первых n простых, и $S_n + q$ кратно p, то и q кратно p, а поскольку q простое, то q = p. Тогда $S_n + q = p*(b+1)$ - делится на $2\cdot 3\dots p_n$, в то время как $p\cdot b = 2+3+...+p_n$. То есть сумма n чисел, не меньших 2, лишь на одно слагаемое меньше их произведения, что для суммы первых простых чисел, очевидно, не верно начиная с $S_3$ (для $S_1$ и $S_2$ утверждение доказывается непосредственно).

Но раз $S_n$ не делится на $2, 3, \dots, p_n$, то оно простое. Действительно, $S_n < n\cdot p_n$, а поскольку $n < p_n$, то $S_n$ не делится на все простые, меньшие квадратного корня из $S_n$, то есть простое.

2. Пусть, наоборот, $S_n$ простое. Покажем, что простое q существует. Рассмотрим арифметическую прогрессию с первым членом $-S_n$ и разностью $2 \cdot 3 \dots p_n$. Поскольку $S_n$ простое, то оно взаимно просто с $2 \cdot 3 \dots p_n$, и значит в этой прогрессии, по теореме Дирихле, есть бесконечное количество простых чисел. Любое из них годится в качестве q. Обсуждение

Для меня было неожиданностью, что ряд опытных, искушенных марафонцев испытывали некоторые затруднения при решении этой, на мой взгляд, простой задачи. (Конечно, теорема Дирихле о простых числах в арифметической прогрессии - утверждение нетривиальное. Но зато широко известное :)). При желании, я мог придраться к большему числу решений. Читая утверждения типа "составное число, меньшее $p^2$, не может иметь делителей, больших p", я был близок к "кровопролитию". Но сдержался :)

В OEIS последовательность простых $S_n$ представлена под номером A013918.

Интересно, конечно ли множество n, для которых $S_n$. Интуиция подсказывает, что:
1) бесконечно;
2) доказательство первого пункта нетривиально :)

Награды

За правильное решение этой задачи Виктор Филимоненков, Эдвард Туркевич, Анатолий Казмерчук, Алексей Волошин и Mathusic получают по 4 призовых балла. Сергей Половинкин, Николай Дерюгин и Евгений Машеров получают по 2 призовых балла.

Эстетическая оценка задачи 4.3

================

Обзор задачи ММ124 подготовлен Владимиром Лецко

Задайте вопрос на блоге о математике