Конкурсная задача ММ124 (4 балла)

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

Решение

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

1. Пусть такое число q для S_n существует. Тогда S_n не делится ни на одно из чисел 2, 3, …, p_n. Действительно, если S_n = p*b, где p - одно из первых n простых, и S_n + q кратно p, то и q кратно p, а поскольку q простое, то q = p. Тогда S_n + q = p*(b+1) - делится на 2*3*…*p_n, в то время как pb = 2+3+…+p_n. То есть сумма n чисел, не меньших 2, лишь на одно слагаемое меньше их произведения, что для суммы первых простых чисел, очевидно, не верно начиная с S₃ (для S₁ и S₂ утверждение доказывается непосредственно).

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

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

Обсуждение

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

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

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

Награды

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

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

---