Разделы 
Дополнительно
Задача по математике - 3062
2019-05-06 
а) Доказать, что среди членов арифметических прогрессий $3, 7, 11, 15, 19, 23, \cdots$ и $5, 11, 17, 23, 29, 35,\cdots$ имеется бесконечно много простых чисел.
б) Доказать, что среди членов арифметической прогрессии
$11, 21, 31, 41, 51, 61, \cdots$
имеется бесконечно много простых чисел.
Решение:
а) Доказательство этой теоремы очень близко к доказательству Евклида бесконечнои числа простых чисел. Предположим, что среди чисел вида $4k - 1$ имеется только конечное число простых чисел, а именно $3, 7, 11, 19, 23, \cdots, p_n$. Составим число $N = 4(3, 7, 11, 19, 23, \cdots, р_n) - 1$. Оно больше всех принадлежащих прогрессии простых чисел и, следовательно, должно быть составным. Разложим число $N$ па простые множители. Среди них не может быть чисел вида $4k-1$, так как число $N + 1 - 4(3 \cdot 7 \cdot 11 \cdot 19 \cdot 23 \cdots p_n)$ делится на все простые числа вида $4k - 1$, а следовательно, N взаимно просто со всеми этими числами. Так как N нечетно, то оно должно представлять собой произведение нескольких простых чисел вида $4k + 1$. Но это невозможно, так как произведение двух чисел вида $4k + 1$ имеет тог же вид:
$(4k_1 + 1) (4k_2 + 1) = 16k_1k_2 + 4k_1 + 4k_2 + 1 = 4(4k_1k_2 + k_1 + k_2) + 1 = 4k_3 + 1$,
а следовательно, и произведение нескольких чисел вида $4k + 1$ имеет тот же вид, в то время как число $N$ имеет вид $4k - 1$. Полученное противоречие и доказывает теорему.
Аналогично доказывается, что существует бесконечно много простых чисел, принадлежащих прогрессии $5, 11, 17, 23, \cdots$ (простых чисел вида $6k - 1$).
б) Доказательство настоящей теоремы несколько сложнее доказательств теорем задачи а), хотя построено на той же идее.
Предположим, что в ряду чисел $11, 21, 31, 41, 51, 61, \cdots$ имеется только конечное число простых: $11, 31, 41, 61, \cdots, p_n$. Составим число $N = (11 \cdot 31 \cdot 41 \cdot 61 \cdots, p_n)^5 - 1$. Оно взаимно просто со всеми простыми числами $11, 31, 41, \cdots, p_n$, так как число $N + 1$ делится на все эти числа. Обозначим произведение $11, 31, 41 \cdots, p_n$ через $a$, тогда $N = a^5 - 1 = (a - 1) (a^4 + a^3 + a^2 + a + 1)$.
Рассмотрим, какие простые делители может иметь второй множитель $a^4 + a^3 + a^2 + a + 1$ последнего произведения. Очевидно, что $a^4 + a^3 + a^2 + a + 1$ не делится на 2 (сумма пяти нечетных чисел нечетна). Далее, $a^4 + a^3 + a^2 + a + 1$ делится на 5, поскольку а оканчивается на 1 (как произведение ряда чисел, каждое из которых оканчивается на 1), $a^2, a^3$ и $a^4$ все оканчиваются на 1 и, следовательно, сумма $a^4 + a^3 + a^2 + a + 1$ оканчивается на 5. Пусть теперь $p$ есть простой делитель числа $a^4 + a^3 + a^2 + a + 1$, отличный от 5. В таком случае $a - 1$ не может делиться, на $p$, так как иначе $а$ имело бы вид $kp + 1$, следовательно, $a^2, a^3$ и $a^4$ (равные соответственно $(kp+1)^2$, $(kp+1)^3$ и $(kp+1)^4$) имели бы такой же вид и число
$a^4 + a^3 + a^2 + a + 1 = (kp+1)^4 + (kp+1)^3 + (kp+1)^2 + (kp+1) + 1$
давало бы при делении на $p$ остаток 5. Отсюда следует, что $p - 1$ должно делиться на 5. Действительно, предположим, например, что $p-1$ дает при делении на 5 остаток 4: $p-1 = 5k + 4$. Отметим, что в силу теоремы Ферма (задача 3052) $a^{p-1} - 1$ делится на $p$. Но в этом случае
$a^{p-1} - 1 = a^{5k+4} - 1 = a^4 (a^5k - 1) + (a^4 - 1)$,
а так как $a^{5k} - 1 = (a^5)^k - 1^k$ делится на $a^5 - 1$, а значит и на $p$, то и $а^4 - 1$ делится на $p$. Но $a^5 - 1 = a (a^4 - 1) + (a - 1)$; следовательно, если $a^5-1$ и $а^4 - 1$ делятся на $p$, то и $a-1$ должно было бы делиться на $p$, что, как мы уже показали выше, невозможно. Аналогично показывается, что число $p - 1$ не может давать при делении на 5 остатки 1, 2 или 3.
Итак, $p - 1$ делится на 5 и четно ($p - 1$ четно, ибо $p$ нечетно); следовательно, $p-1$ делится на 10 и, значит, $p$ имеет вид $10k + 1$, т. е. принадлежит нашей прогрессии. Итак, нами установлено, что простыми делителями числа $a^4 + a^3 + a^2 + a + 1$ могут быть только число 5 и простые числа вида $10k + 1$.
Но число $a^4 + a^3 + a^2 + a + 1$, очевидно, больше 5 и не делится на $5^2 = 25$. Действительно, число а оканчивается на 1 и, следовательно, имеет вид $5k+1$. Далее, по формуле бинома Ньютона
$a^4 + a^3 + a^2 + a + 1 = (5k + 1)^4 + (5k + 1)^3 + (5k + 1)^2 + 5k+ 1 + 1 = 625k^4 + 4 \cdot 125k^3 + 6 \cdot 25k^2 + 4 \cdot 5k + 1 + 125k^3 + 3 \cdot 25k^2 + 3 \cdot 5k + 1 + 25k^2 + 2 \cdot 5k + 1 + 1 + 5k + 1 + 1 = 625k^4 + 5 \cdot 125k^3 + 10 \cdot 25k^2 + 10 \cdot 5k + 5 = 5 \cdot [5 (25k^4 + 25k^3 + 10k^2 + 2k) + 1]$.
Отсюда следует, что это число, а значит, и число $N = a^5-1$ должно иметь хотя бы один простой делитель вида $10k + 1$. Но, по нашему предположению, N взаимно просто со всеми простыми числами вида $10k + 1$. Полученное противоречие и доказывает теорему.
а) Доказать, что среди членов арифметических прогрессий $3, 7, 11, 15, 19, 23, \cdots$ и $5, 11, 17, 23, 29, 35,\cdots$ имеется бесконечно много простых чисел.
б) Доказать, что среди членов арифметической прогрессии
$11, 21, 31, 41, 51, 61, \cdots$
имеется бесконечно много простых чисел.
Решение:
а) Доказательство этой теоремы очень близко к доказательству Евклида бесконечнои числа простых чисел. Предположим, что среди чисел вида $4k - 1$ имеется только конечное число простых чисел, а именно $3, 7, 11, 19, 23, \cdots, p_n$. Составим число $N = 4(3, 7, 11, 19, 23, \cdots, р_n) - 1$. Оно больше всех принадлежащих прогрессии простых чисел и, следовательно, должно быть составным. Разложим число $N$ па простые множители. Среди них не может быть чисел вида $4k-1$, так как число $N + 1 - 4(3 \cdot 7 \cdot 11 \cdot 19 \cdot 23 \cdots p_n)$ делится на все простые числа вида $4k - 1$, а следовательно, N взаимно просто со всеми этими числами. Так как N нечетно, то оно должно представлять собой произведение нескольких простых чисел вида $4k + 1$. Но это невозможно, так как произведение двух чисел вида $4k + 1$ имеет тог же вид:
$(4k_1 + 1) (4k_2 + 1) = 16k_1k_2 + 4k_1 + 4k_2 + 1 = 4(4k_1k_2 + k_1 + k_2) + 1 = 4k_3 + 1$,
а следовательно, и произведение нескольких чисел вида $4k + 1$ имеет тот же вид, в то время как число $N$ имеет вид $4k - 1$. Полученное противоречие и доказывает теорему.
Аналогично доказывается, что существует бесконечно много простых чисел, принадлежащих прогрессии $5, 11, 17, 23, \cdots$ (простых чисел вида $6k - 1$).
б) Доказательство настоящей теоремы несколько сложнее доказательств теорем задачи а), хотя построено на той же идее.
Предположим, что в ряду чисел $11, 21, 31, 41, 51, 61, \cdots$ имеется только конечное число простых: $11, 31, 41, 61, \cdots, p_n$. Составим число $N = (11 \cdot 31 \cdot 41 \cdot 61 \cdots, p_n)^5 - 1$. Оно взаимно просто со всеми простыми числами $11, 31, 41, \cdots, p_n$, так как число $N + 1$ делится на все эти числа. Обозначим произведение $11, 31, 41 \cdots, p_n$ через $a$, тогда $N = a^5 - 1 = (a - 1) (a^4 + a^3 + a^2 + a + 1)$.
Рассмотрим, какие простые делители может иметь второй множитель $a^4 + a^3 + a^2 + a + 1$ последнего произведения. Очевидно, что $a^4 + a^3 + a^2 + a + 1$ не делится на 2 (сумма пяти нечетных чисел нечетна). Далее, $a^4 + a^3 + a^2 + a + 1$ делится на 5, поскольку а оканчивается на 1 (как произведение ряда чисел, каждое из которых оканчивается на 1), $a^2, a^3$ и $a^4$ все оканчиваются на 1 и, следовательно, сумма $a^4 + a^3 + a^2 + a + 1$ оканчивается на 5. Пусть теперь $p$ есть простой делитель числа $a^4 + a^3 + a^2 + a + 1$, отличный от 5. В таком случае $a - 1$ не может делиться, на $p$, так как иначе $а$ имело бы вид $kp + 1$, следовательно, $a^2, a^3$ и $a^4$ (равные соответственно $(kp+1)^2$, $(kp+1)^3$ и $(kp+1)^4$) имели бы такой же вид и число
$a^4 + a^3 + a^2 + a + 1 = (kp+1)^4 + (kp+1)^3 + (kp+1)^2 + (kp+1) + 1$
давало бы при делении на $p$ остаток 5. Отсюда следует, что $p - 1$ должно делиться на 5. Действительно, предположим, например, что $p-1$ дает при делении на 5 остаток 4: $p-1 = 5k + 4$. Отметим, что в силу теоремы Ферма (задача 3052) $a^{p-1} - 1$ делится на $p$. Но в этом случае
$a^{p-1} - 1 = a^{5k+4} - 1 = a^4 (a^5k - 1) + (a^4 - 1)$,
а так как $a^{5k} - 1 = (a^5)^k - 1^k$ делится на $a^5 - 1$, а значит и на $p$, то и $а^4 - 1$ делится на $p$. Но $a^5 - 1 = a (a^4 - 1) + (a - 1)$; следовательно, если $a^5-1$ и $а^4 - 1$ делятся на $p$, то и $a-1$ должно было бы делиться на $p$, что, как мы уже показали выше, невозможно. Аналогично показывается, что число $p - 1$ не может давать при делении на 5 остатки 1, 2 или 3.
Итак, $p - 1$ делится на 5 и четно ($p - 1$ четно, ибо $p$ нечетно); следовательно, $p-1$ делится на 10 и, значит, $p$ имеет вид $10k + 1$, т. е. принадлежит нашей прогрессии. Итак, нами установлено, что простыми делителями числа $a^4 + a^3 + a^2 + a + 1$ могут быть только число 5 и простые числа вида $10k + 1$.
Но число $a^4 + a^3 + a^2 + a + 1$, очевидно, больше 5 и не делится на $5^2 = 25$. Действительно, число а оканчивается на 1 и, следовательно, имеет вид $5k+1$. Далее, по формуле бинома Ньютона
$a^4 + a^3 + a^2 + a + 1 = (5k + 1)^4 + (5k + 1)^3 + (5k + 1)^2 + 5k+ 1 + 1 = 625k^4 + 4 \cdot 125k^3 + 6 \cdot 25k^2 + 4 \cdot 5k + 1 + 125k^3 + 3 \cdot 25k^2 + 3 \cdot 5k + 1 + 25k^2 + 2 \cdot 5k + 1 + 1 + 5k + 1 + 1 = 625k^4 + 5 \cdot 125k^3 + 10 \cdot 25k^2 + 10 \cdot 5k + 5 = 5 \cdot [5 (25k^4 + 25k^3 + 10k^2 + 2k) + 1]$.
Отсюда следует, что это число, а значит, и число $N = a^5-1$ должно иметь хотя бы один простой делитель вида $10k + 1$. Но, по нашему предположению, N взаимно просто со всеми простыми числами вида $10k + 1$. Полученное противоречие и доказывает теорему.
