Стратегия (евклидовский аргумент по противоречию):
1. Предположим, что простых чисел вида $4k+3$ всего конечное число: $p_1,\dots ,p_n$.
2. Рассмотрим число $$N=4\cdot p_1{p}_2\cdots p_n-1.$$ Тогда $N\equiv -1(\mathrm{mod}4)$, т.е. $N\equiv 3(\mathrm{mod}4)$.
3. Возьмём любой простый делитель $q$ числа $N$. Показать две вещи:
- $q$ не равен ни одному из $p_i$ (ибо если $q\mid p_1\cdots p_n$, то $q\mid 4\cdot p_1\cdots p_n$, и тогда $q\mid (4\cdot p_1\cdots p_n)-(4\cdot p_1\cdots p_n-1)=1$, противоречие).
- $q\ne 2$ (так как $N$ нечётно), и обязательно $q\equiv 3(\mathrm{mod}4)$. Доказательство последнего пункта: если все простые делители $q$ числа $N$ были бы $\equiv 1(\mathrm{mod}4)$, то по мультипликативности вычетов получалось бы $N\equiv 1(\mathrm{mod}4)$, что противоречит $N\equiv 3(\mathrm{mod}4)$. Значит существует делитель $q\equiv 3(\mathrm{mod}4)$, и он не среди $p_i$ — получили новый простой того же вида, противоречие с конечностью множества.
Ключевые леммы и факты:
- Если целое $M\equiv 3(\mathrm{mod}4)$, то в его разложении на простые имеется по крайней мере один простой $\equiv 3(\mathrm{mod}4)$. (Иначе произведение всех простых делителей по модулю $4$ давало бы $1$.)
- Если простой $q$ делит $4\cdot p_1\cdots p_n-1$, то $q$ не делит $p_1\cdots p_n$. (Иначе $q$ делил бы разность и число $1$.)
- Простое $2$ не относится к классу $4k+3$ — нужно не забывать исключать $2$.
Потенциальные ловушки и типичные ошибки:
- Неправильно выбрать конструкцию числа $N$. Например, взять $N=p_1\cdots p_n-1$ без контроля по модулю $4$ — тогда $N$ может быть $\equiv 1$ или $\equiv 0(\mathrm{mod}4)$, и аргумент про делитель $\equiv 3(\mathrm{mod}4)$ не следует автоматически.
- Игнорирование возможности чётных степеней простых $\equiv 3(\mathrm{mod}4)$: при анализе вычетов по модулю $4$ учитывать степени в разложении (но достаточно смотреть на наличие хотя бы одного простого $\equiv 3(\mathrm{mod}4)$ с нечётной кратностью).
- Забытие исключения простого $2$.
- Необоснованное утверждение, что само $N$ обязательно простое: достаточно наличия простого делителя нового вида, $N$ может быть составным.
Альтернативы/общие замечания:
- Можно заменить $4\cdot P-1$ на любое число, дающее $\equiv 3(\mathrm{mod}4)$ и не делящееся на $p_i$ (классический выбор — $4P-1$ удобен и прост).
- Существуют более мощные методы (теорема Дирихле об арифметических прогрессиях, аргументы с гауссовыми целыми), но приведённый евклидовский приём сам по себе даёт чистое элементарное доказательство бесконечности простых вида $4k+3$.