Не просто прогрессии

1. Зачастую знание ответа может очень помочь при решении. Так вот ответ: да, существует!

2. Попробуйте предположить противное.

1. Итак, всё что нам осталось — это придумать пример такой арифметической прогрессии. Подумаем, как она могла бы быть устроена. По требованию условия наибольший общий делитель любых двух членов такой прогрессии должен быть равен 1, то есть единственный их общий делитель — это 1. Пусть a и b — два каких-либо члена прогрессии, d — её разность. Заметим, что все общие делители чисел a и b являются делителями числа a – b (но конечно же, у a – b могут быть делители, просто они не должны являться делителями a или b). При этом a – b = k · d, k ∈ ℕ, и достаточно придумать такую разность, чтобы первые 100 членов прогрессии не имели с ней (и с ней, умноженной на 1, 2, 3, ..., 99, 100) никаких общих делителей.

2. Воспользуемся первой подсказкой и предположим, что нашлась арифметическая прогрессия, состоящая только из простых чисел. Остаётся придумать рассуждение, приводящее нас к противоречию.

Для удобства обозначим первый член прогрессии за a и разность за d. Тогда все последующие члены будут иметь вид a + k · d, где k — любое натуральное число. Остаётся совсем немного — найти среди них числа имеющие общие делители, отличные от 1.

1. Рассмотрим прогрессию с разностью d = 99! и первым членом a₁ = 1 + 99! (напомним, что запись вида n! обозначает произведение всех натуральных чисел от 1 до n, например 5! = 1·2·3·4·5 = 120, см. также факториал); 99! — это очень большое число, в нем 156 цифр. Любой член этой прогрессии будет иметь вид a_k = 1 + k·99!. Нас интересуют только первые 100 членов этой прогрессии, поэтому k — натуральное число от 1 до 100. Заметим, что a_k не делится ни на одно простое число от 1 до 99 (потому что все время дает при делении на такое простое число остаток 1). Кроме того, разность произвольных двух ее членов a_k и a_l равна (k − l)·99! и может делиться только на простые числа от 1 до 99 (и, конечно, на их произведения в различных степенях), но не может делиться ни на какие простые числа, большие 99. Поэтому у чисел a_k и a_k − a_l нет никаких общих делителей, кроме 1. Наконец, вспомним, что наибольший общий делитель чисел m и m − n равен наибольшему общему делителю чисел m и n (это несложное утверждение лежит в основе алгоритма Евклида и остается читателям в качестве упражнения), поэтому из взаимной простоты a_k и a_k − a_l следует взаимная простота a_k и a_l.

2. Заметим, что если число k делится на a, то и число a + kd делится на a. Поэтому в любой прогрессии, состоящей из натуральных чисел, с первым членом a и разностью d член с номером a + 1 (он равен a + ad = a(d + 1)) будет делиться на a. Если оказалось, что a = 1, то надо то же рассуждение применить к слегка модифицированной прогрессии: в качестве «начала» нужно взять ее второй член. Получается, что в любой бесконечной прогрессии из натуральных чисел обязательно встретится составное число.

Во второй задаче мы без особого труда выяснили, что не бывает арифметических прогрессий, состоящих только из простых чисел, с бесконечным количеством членов. Оказывается, однако, что для любого числа N такая прогрессия из N членов существует. Попробуйте придумать пример для N = 5 (см. ответ для этого и некоторых других случаев). Этот факт — один из примеров того, как за понятной формулировкой скрывается очень сложная проблема.

Наверное, самая известная задача такого рода — это Великая теорема Ферма. Но есть и множество ещё не доказанных утверждений, формулировки которых понятны школьнику старших классов. Вот одна из них. Все мы знаем, что простых чисел бесконечно много, но до сих пор неизвестно, конечно или бесконечно количество простых чисел-близнецов — так называются пары простых чисел, отличающихся друг от друга на 2 (например, 3 и 5, 5 и 7, 11 и 13, 17 и 19, ...). Предполагается, что простых чисел-близнецов тоже бесконечно много, но это не доказано и не опровергнуто.

Но существование прогрессии из простых чисел любой наперед заданной длины — уже доказанная в 2004 году Беном Грином и Теренсом Тао теорема. При этом доказательство совершенно не элементарно и, более того, оно не конструктивно, то есть не предлагает алгоритма для поиска такой прогрессии. Интересно, что на настоящий момент самая длинная из прогрессий, в которой есть только простые числа, состоит всего из 26 членов. Этот пример был найден в 2010 году:
43 142 746 595 714 191 + 23 681 770·223 092 870·n, где n принимает значения от 0 до 25.

Важно еще отметить, что очень часто такого рода задачи полезны не сами по себе, не «конечным результатом», а, скорее, «процессом»: в ходе их решения появляются новые методы, а иногда и целые теории, которые потом находят многочисленные применения. Вот что Давид Гильберт сказал по поводу Великой теоремы Ферма в 1900 году (почти за 100 лет до ее окончательного доказательства!):

«Проблема доказательства этой неразрешимости являет разительный пример того, какое побуждающее влияние на науку может оказать специальная и на первый взгляд малозначительная проблема. Ибо, побуждённый задачей Ферма, Куммер пришёл к введению идеальных чисел и к открытию теоремы об однозначном разложении чисел в круговых полях на идеальные простые множители — теоремы, которая теперь, благодаря обобщениям на любую алгебраическую числовую область, полученным Дедекиндом и Кронекером, является центральной в современной теории чисел и значение которой выходит далеко за пределы теории чисел в область алгебры и теории функций.»

Конечно же, имя Пауля Эрдеша не могло не возникнуть рядом с такой задачей: гипотеза Эрдеша об арифметических прогрессиях утверждает, что если взять какое-либо подмножество натуральных чисел такое, что сумма ряда из обратных к этим числам величин расходится, то это подмножество содержит арифметические прогрессии сколь угодно большой длины. Если в качестве такого подмножества взять простые числа (сумма обратных к ним величин расходится), то получится теорема Грина — Тао.

Существуют и другие обобщения теоремы Грина—Тао, например такое. Рассмотрим произвольную последовательность многочленов от одной переменной с целыми коэффициентами и нулевым свободным членом. Пусть эта последовательность имеет длину N: P₁(x), ..., P_N(x). Тогда существует бесконечно много пар чисел a, x таких, что все члены последовательности a + P₁(x), a + P₂(x), ..., a + P_N(x) — простые числа. Несложно видеть, что если взять в качестве P_k(x) многочлен k·x, то вновь получится утверждение теоремы Грина—Тао.