Конкурсная задача ММ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 призовой балл.
Решение, в котором неверно трактуется понятие простого числа, призовыми баллами не поощряется. 

---