простые-числа - Количество простых чисел вида 4k+3

Верно общее утверждение о том, что в любой арифметической прогрессии вида $%an+b$% бесконечно много простых чисел, где $%a$%, $%b$% -- взаимно простые натуральные числа (теорема Дирихле). Но её доказательство достаточно сложное, поэтому здесь уместно рассмотреть отдельные решения для указанных частных случаев.

Первый вариант несколько проще. Рассуждая от противного, допустим, что в конечном списке $%p_1$%, ... , $%p_m$% содержатся все простые числа вида $%4k+3$%. Рассмотрим число $%N=4p_1\ldots p_m-1$%, которое очевидным образом не делится ни на одно из указанных. Тогда, будучи нечётным, оно является произведением нечётных простых, среди которых все должны иметь вид $%4k+1$%. Значит, и оно само при делении на 4 должно давать в остатке 1, но это не так по построению (единицу мы вычитали, а не прибавляли).

Второе условие чуть посложнее. Здесь нужно использовать такое вспомогательное утверждение: всякий нечётный делитель числа вида $%n^2+1$% имеет вид $%4k+1$%. Этот факт выводится из малой теоремы Ферма. Если $%p$% -- нечётное простое, на которое делится $%n^2+1$%, то числа $%-1$% и $%n^2$% сравнимы по модулю $%p$%. Возводя сравнение в степень с показателем $%\frac{p-1}2$%, мы получим, что $%(-1)^\frac{p-1}2$% по модулю $%p$% сравнимо с $%n^{p-1}$%, что сравнимо с единицей по модулю $%p$% в силу малой теоремы Ферма. Значит, $%\frac{p-1}2$% чётно, так как $%-1$% и $%1$% не сравнимы по нечётному модулю.

Теперь применяем тот же метод, что и выше, выписывая все простые числа вида $%4k+1$% в предположении, что их множество конечно. Пусть это $%p_1$%, ... , $%p_m$%; рассматриваем число $%N=4(p_1\ldots p_m)^2+1$%. Оно нечётно, и простыми делителями могут быть только числа вида $%4k+1$%, согласно сказанному выше. Однако все они содержатся в конечном списке, и $%N$% по построению не делится ни на одно из них.