b. Простые числа в арифметических прогрессиях

Если доказательство того, что в последовательности всех натуральных чисел 1,2,3,4, . . . содержится бесконечное множество простых чисел, носит вполне элементарный характер, то следующий шаг в сторону таких последовательностей, как, например, 1, 4, 7, 10, 13, ... или 3, 7, 11, 15, 19, . . ., или, вообще говоря, в сторону произвольной арифметической прогрессии а, а + d, а + 2d, ..., а + nd, ... (где а и d не имеют общих множителей), оказался связанным с гораздо большими трудностями. Все наблюдения только подтверждали тот факт, что в каждой такой прогрессии содержится бесконечное число простых чисел, как и в простейшей из них 1, 2, 3, ... . Но понадобились величайшие усилия для того, чтобы доказать эту общую теорему. Успех был достигнут Лежёном Дирихле (1805-1859), одним из ведущих математиков прошлого столетия, который применил при доказательстве самые усовершенствованные средства математического анализа из известных в то время. Его замечательные работы в этой области даже для настоящего времени остаются непревзойденными; прошло около ста лет, но доказательства Дирихле все еще не упрощены настолько, чтобы они могли быть поняты теми, кто не овладел полностью аппаратом математического анализа и теории функций.

Мы не будем здесь пытаться привести доказательство общей теоремы Дирихле, а ограничимся рассмотрением более легкой задачи: обобщим евклидово доказательство о существовании бесконечного множества простых чисел таким образом, чтобы оно охватило некоторые специальные прогрессии, например 4n + 3 или 6n + 5. Рассмотрим первую из этих прогрессий. Заметим прежде всего, что всякое простое число, большее 2, непременно нечетное (иначе оно делилось бы на 2) и, следовательно, имеет вид 4n + 1 или 4n + 3 (при целом n). Далее, произведение двух чисел вида 4n + 1 также есть число того же вида, так как

Допустим теперь, что существует лишь конечное число простых чисел вида 4n + 3; обозначим их р₁, р₂, ..., р_n и рассмотрим число

Одно из двух: либо число N простое, либо оно разлагается на произведение простых чисел, среди которых, однако, не может быть ни одного из чисел р₁, р₂, ..., p_n, так как эти числа делят N с остатком -1.

Заметим теперь, что все множители, входящие в N, не могут быть вида 4n + 1, так как само N не этого вида, тогда как мы видели, что произведение чисел вида 4n + 1 является числом того же вида. Итак, хоть один из множителей, входящих в N, должен быть вида 4n + 3, а это невозможно, так как ни одно из чисел р не входит множителем в N, а числами р все простые числа вида 4n + 3 по предположению исчерпываются. Таким образом, допуская, что существует лишь конечное число простых чисел вида 4n + 3, мы приходим к противоречию, и, значит, число таких чисел бесконечно.

Упражнение. Докажите соответствующую теорему для прогресии 6n + 5.