Разделы 
Дополнительно
Задача по математике - 3061
2019-05-06 
Доказать, что существует бесконечно много простых чисел.
Решение:
Существование бесконечного числа простых чисел следует из результата задачи 2946 (из этой задачи вытекает даже, что простые числа встречаются в ряду всех целых чисел достаточно «часто», например, «чаще», чем квадраты; см. примечание к этой задаче). Из результата задачи 2802 также можно усмотреть, что простых чисел существует .бесконечно много: если бы всего существовало только $n$ простых чисел, то не могло бы быть больше чем $n$ взаимно простых друг с другом чисел. Но наиболее простым доказательством теоремы о бесконечности числа простых чисел является следующее доказательство, принадлежавшее Евклиду.
Предположим, что имеется всего $n$ простых чисел $2, 3, 5, 7, 11, \cdots, p_n$. Образуем число $N = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot \cdots \cdot p_n + 1$. Число $N$ больше всех простых чисел $2, 3, 5, \cdots, p_n$ и поэтому должно быть составным. Но так как $N-1$ делится на $2, 3, 5, 7, \cdots, p_n$, то $N$ взаимно просто со всеми простыми числами. Полученное противоречие и доказывает теорему.
Доказать, что существует бесконечно много простых чисел.
Решение:
Существование бесконечного числа простых чисел следует из результата задачи 2946 (из этой задачи вытекает даже, что простые числа встречаются в ряду всех целых чисел достаточно «часто», например, «чаще», чем квадраты; см. примечание к этой задаче). Из результата задачи 2802 также можно усмотреть, что простых чисел существует .бесконечно много: если бы всего существовало только $n$ простых чисел, то не могло бы быть больше чем $n$ взаимно простых друг с другом чисел. Но наиболее простым доказательством теоремы о бесконечности числа простых чисел является следующее доказательство, принадлежавшее Евклиду.
Предположим, что имеется всего $n$ простых чисел $2, 3, 5, 7, 11, \cdots, p_n$. Образуем число $N = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot \cdots \cdot p_n + 1$. Число $N$ больше всех простых чисел $2, 3, 5, \cdots, p_n$ и поэтому должно быть составным. Но так как $N-1$ делится на $2, 3, 5, 7, \cdots, p_n$, то $N$ взаимно просто со всеми простыми числами. Полученное противоречие и доказывает теорему.
