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

Займёмся теперь выяснением вопроса о количестве простых чисел. Следующая теорема впервые появилась в “Началах” Евклида и имеет множество различных доказательств, из которых приведём лишь одно.

Теорема (Евклида о бесконечности числа простых чисел). Простых чисел бесконечно много.

Доказательство. Предположим, вопреки доказываемому, что множество простых чисел конечно и состоит из элементов p₁ = 2 < p₂ = 3 < … < p_n . Рассмотрим число N = p₁p₂ … p_n + 1 > 1. Оно, с одной стороны, раскладывается в произведение простых множителей (по основной теореме арифметики), а с другой – не может делиться ни на одно из простых чисел p_i (1  i  n): если p_i | N , то p_i | (N – p₁ … p_i … p_n) = 1) – противоречие.

Теорема доказана.

Эта теорема утверждает бесконечность числа простых чисел в арифметической прогрессии 1 + 1n (n  N₀). Конечно, есть арифметические прогрессии a + bn (n  N₀), в которых совсем нет простых чисел: такова, например, прогрессия 4 + 4n (n  N₀), в которой каждое число делится на 4.

Вообще, если D = НОД(a, b), то на D делится любой член последовательности a + bn (n  N₀), так что при составном D в такой арифметической прогрессии нет ни одного простого числа. Если D = p – простое, то любое число прогрессии делится на p, так что она может содержать только простое число p. Эта возможность реализуется только в том случае, когда a₁ + b₁k = 1, где при некотором k  N₀ . Например, прогрессия 49 + 7n (n  N₀) не содержит простых чисел, а прогрессия 7 – 42n (n  N₀) содержит простое число 7.

Условие a₁ + b₁k = 1 будет выполнено для некоторого k  N₀ тогда и только тогда, когда либо a₁ = 1, либо a₁ – 1  b₁ и (a₁ – 1)b₁ < 0. Таким образом, доказана

Теорема (об арифметических прогрессиях с малым числом простых). Если D = НОД(a, b) > 1, то арифметическая прогрессия a + bn (n  N₀) содержит единственное простое число р в случае D = p = a или, если D = p, a₁ – 1  b₁ , (a₁ – 1)b₁ < 0. Если D составное число, то в арифметической прогрессии нет простых чисел.

Остаётся вопрос о количестве простых чисел в арифметической прогрессии a + bn (n  N₀) со взаимно простыми начальным членом a и разностью b. Оказывается, имеет место следующая удивительная теорема:

Теорема (Дирихле). Любая арифметическая прогрессия вида a + bn (n  N₀) со взаимно простыми a, b содержит бесконечно много простых чисел.

Без доказательства.

Примеры: 1. Арифметическая прогрессия 1 + 2n (n  N₀) содержит все нечётные простые числа.

2. Любое простое число, большее 3, при делении на 3 даёт остаток 1 или 2. По этому одна из арифметических прогрессий 1 + 3n или 2 + 3n (n  N₀) содержит бесконечно много простых чисел (на самом деле, конечно, обе !). На самом деле любое простое число p > 3 можно записать в виде 3n ± 1 (n  N₀). Это очевидно для простого числа p из арифметической прогрессии 1 + 3n (n  N₀), а p = 2 + 3n = 3 – 1 + 3n = 3(n+1) – 1, что и требовалось.

3. Любое простое число, большее 3, при делении на 4 даёт остаток 1 или 3 (остатки 0, 2 не могут встретиться, поскольку числа вида 4q, 4q + 2 являются чётными). Таким образом, одна из арифметических прогрессий 1 + 4n или 3 + 4n (n  N₀) содержит бесконечно много простых чисел (по теореме Дирихле – обе !). На самом деле любое простое число p > 3 можно записать в виде 4n ± 1 (n  N₀). Это очевидно для простого числа p из арифметической прогрессии 1 + 4n (n  N₀), а p = 3 + 4n = = 4 – 1 + 4n = 4(n+1) – 1, что и требовалось.

4. Любое простое число, большее 5, при делении на 6 даёт остатки 1 или 5 (остатки 0, 2 и 3 не могут встретиться, поскольку числа вида 6q, 6q + 2 и 6q + 3 делятся на 2 и на 3 соответственно). Таким образом, одна из арифметических прогрессий 1 + 6n или 5 + 6n (n  N₀) содержит бесконечно много простых чисел (по теореме Дирихле – обе !). На самом деле любое простое число p > 5 можно записать в виде 6n ± 1 (n  N₀). Это очевидно для простого числа p из арифметической прогрессии 1 + 6n (n  N₀), а p = 5 + 6n = 6 – 1 + 6n = 6(n+1) – 1, что и требовалось.

Теорема (о простых числах в арифметических прогрессиях 4n – 1, 6n – 1). Арифметические прогрессии 4n – 1 , 6n – 1 (n  N₀) содержат бесконечно много простых чисел.

Доказательство. Проведём рассуждения от противного одновременно для обеих указанных прогрессий вида bn – 1 (n  N₀), где b  {4, 6}, применив идею доказательства Евклида бесконечности простых чисел.

Предположим, вопреки доказываемому, что данная арифметическая прогрессия содержит конечное число простых членов p₁ < p₂ < … < p_k и рассмотрим число N = bp₂…p_k – 1 из этой прогрессии. По основной теореме арифметики, оно раскладывается в произведение простых множителей. Эти простые множители нечётны (т.к. b чётно) и не могут совпадать ни с одним из чисел p₂ , … , p_k : в противном случае –1 = N – bp₂…p_k делилось бы на одно из чисел p₂ , … , p_k , что невозможно. Поскольку каждое нечётное простое число равно 3 или имеет вид bn ± 1 (по приведённой выше классификации остатков простых чисел), то в разложении числа N могут участвовать только простые множители вида bn + 1 (объясните, почему число N не делится на 3 ?!). Однако, произведение чисел вида bn + 1 снова имеет этот же вид: (bn + 1)( bm + 1) = bs + 1, где s = n + m + bnm , и не может дать число bn – 1 (?!).

Теорема доказана.

Примеры: 1. Найти все простые числа p, для которых p – 2, p + 3 простые.

Таких чисел нет, т.к. p = 2 не годится, а для нечётного p число p + 3 делится на 2.

2. Найти все простые числа p, для которых p + 2, p + 4 простые.

Ясно, что p = 3 годится, а p = 2 – нет. Если p > 3, то p = 3n ± 1. Если p = 3n + 1, то p + 2 = 3n + 3  3. Если же p = 3n – 1, то p + 4 = 3n + 3  3.

3. Докажите, что для любого нечётного простого числа p > 3 число p² – 1 делится на 24.

Нужно доказать, что p² – 1  3 и p² – 1  8. Запишем p² – 1 = (p+1)(p–1) и заметим, что для p = 3n ± 1 одна из скобок делится на 3. Аналогично для p = 4n ± 1 одна из скобок делится на 4, а другая – на 2.