Докажите, что существует бесконечно много простых чисел, каждое из которых имеет вид 4n + 3. Докажите, что существует бесконечно много простых чисел, каждое из которых имеет вид 6n + 5.

Рассмотрим оба утверждения отдельно. В обоих случаях используется идея Евклида: предположим, что таких простых чисел конечное число, и построим новое число, которое обязано иметь простой делитель нужного вида, но не совпадающий ни с одним из уже перечисленных.

1. Бесконечно много простых чисел вида (4n+3)

Предположим противное: простых чисел, сравнимых с (3) по модулю (4), конечное число. Обозначим их через

[
p_1,p_2,\ldots,p_k.
]

То есть каждый (p_i) имеет вид (4n+3).

Построим число

[
N=4p_1p_2\cdots p_k-1.
]

Тогда:

[
N\equiv -1\equiv 3 \pmod 4.
]

Кроме того, ни одно из чисел (p_i) не делит (N), потому что при делении (N) на (p_i) получаем остаток (-1):

[
N=4p_1p_2\cdots p_k-1\equiv -1\pmod {p_i}.
]

Число (N>1), поэтому у него есть простой делитель. Пусть (q) — простой делитель числа (N).

Так как (N) нечётно, то (q\neq 2). Следовательно, любой простой делитель (q) числа (N) имеет один из двух видов:

[
q\equiv 1\pmod 4
\quad\text{или}\quad
q\equiv 3\pmod 4.
]

Предположим, что все простые делители числа (N) имеют вид (4m+1). Тогда и их произведение, то есть число (N), также давало бы остаток (1) при делении на (4), поскольку произведение чисел, сравнимых с (1) по модулю (4), снова сравнимо с (1) по модулю (4).

Но мы уже получили:

[
N\equiv 3\pmod 4.
]

Противоречие. Значит, среди простых делителей числа (N) есть хотя бы один простой делитель (q), для которого

[
q\equiv 3\pmod 4.
]

Однако (q) не совпадает ни с одним из (p_1,\ldots,p_k), потому что ни одно (p_i) не делит (N). Мы нашли новое простое число вида (4n+3), не вошедшее в полный предполагаемый список.

Полученное противоречие показывает, что простых чисел вида

[
4n+3
]

бесконечно много.

2. Бесконечно много простых чисел вида (6n+5)

Предположим теперь, что простых чисел вида (6n+5) лишь конечное число:

[
p_1,p_2,\ldots,p_k.
]

Построим число

[
N=6p_1p_2\cdots p_k-1.
]

Тогда

[
N\equiv -1\equiv 5\pmod 6.
]

Как и раньше, ни одно из чисел (p_i) не делит (N), поскольку

[
N\equiv -1\pmod {p_i}.
]

Число (N) не делится ни на (2), ни на (3): оно нечётно и имеет остаток (2) при делении на (3). Поэтому любой его простой делитель (q) больше (3).

Каждое простое число больше (3) имеет вид

[
6m+1
\quad\text{или}\quad
6m+5.
]

Действительно, остатки при делении на (6) могут быть (0,1,2,3,4,5). Простое число больше (3) не может быть делимо ни на (2), ни на (3), поэтому остаются только остатки (1) и (5).

Пусть все простые делители числа (N) имеют вид (6m+1). Тогда их произведение также имело бы вид (6m+1), то есть

[
N\equiv 1\pmod 6.
]

Но по построению

[
N\equiv 5\pmod 6.
]

Противоречие. Следовательно, среди простых делителей числа (N) должен быть хотя бы один простой делитель (q), такой что

[
q\equiv 5\pmod 6.
]

Этот делитель не совпадает ни с одним из (p_1,\ldots,p_k), так как ни одно из этих чисел не делит (N). Значит, найдено новое простое число вида (6n+5), не вошедшее в предполагаемый полный список.

Следовательно, простых чисел вида

[
6n+5
]

бесконечно много.