=====ММ5=====

**Конкурсная задача ММ5** (3 баллов)

При каком наименьшем натуральном d (натуральный ряд начинается с 1) существует арифметическая прогрессия с разностью d, в которой встречаются 7 простых чисел подряд?

**Решение**

Пусть a - первый член, а d - разность прогрессии.
Ясно, что a и d должны быть взаимно просты. Если d не кратно простому числу p, то числа a, a+d,..., a+(p-1)d бразуют полную систему вычетов по модулю p. Значит, среди них есть ровно одно кратное p. Следовательно, если мы хотим получить 7 простых членов прогрессии подряд, d должно быть кратно 2, 3 и 5, т.е. кратно 30.\\
Если d не кратно 7, то один из первых семи членов прогрессии будет кратен 7. Этот член может быть простым, только если он в точности равен 7. Но тогда этот член должен быть первым.\\
При d = 30 имеем: 7, 37, 67, 97, 127, 157 - простые. Однако седьмой член прогрессии - 187 = 11*17.\\
При d = 60 и d = 90 вновь спотыкаемся о число 187. При d = 120 составным будет число 7+2*120 = 13*19.\\
Но при d = 150 первые семь членов прогрессии: 7, 157, 307, 457, 607, 757 и 907 - простые числа.\\
Таким образом, ответ d = 150.

**Обсуждение**

Отмечу, что следующая семерка простых чисел подряд возникает при d = 210. Наименьшее подходящее a при этом равно 47.

Когда я пердлагал эту задачу теорема Грина-Тао (о существовании сколь угодно длинных арифметических прогркссий из простых чисел) еще не была доказана, а самая длинная известная прогрессия насчитывала 23 числа.

На сегодняшний день (4.10.2015) теорема доказана и даже обобщена, а самая длинная прогрессия состоит из 26-и чисел.\\
Она имеет вид 43142746595714191 + 5283234035979900n, где n изменяется от 0 до 25.


**Награды**

За правильное (но частично избыточно информатическое) решение задачи Борис Бух получает 2 призовых балла.\\
За ошибочное, но содержащее верные мысли, решение Алексей Воробьев получает 1 призовой балл.\\
Решение, в котором неверно трактуется понятие простого числа, призовыми баллами не поощряется.\ 
----