Разбор задачи ММ124 математического марафона

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

ММ124 (4 балла)

Пусть - сумма n первых простых чисел.
Доказать, что является простым тогда и только тогда, когда существует такое простое число q, что кратно .

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

Решение

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

1. Пусть такое число q для существует. Тогда не делится ни на одно из чисел . Действительно, если , где p - одно из первых n простых, и кратно p, то и q кратно p, а поскольку q простое, то q = p. Тогда - делится на , в то время как . То есть сумма n чисел, не меньших 2, лишь на одно слагаемое меньше их произведения, что для суммы первых протсых чисел, очевидно, не верно начиная с (для и утверждение доказывается непосредственно).

Но раз не делится на , то оно простое. Действительно, , а поскольку , то не делится на все простые, меньшие квадратного корня из , то есть простое.

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

Обсуждение

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

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

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

Награды

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

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

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

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