Задача 30410

Темы:    [ Простые числа и их свойства ] [ Доказательство от противного ]

Сложность: 3+ Классы: 8,9

Условие

Автор: Фольклор

Докажите, что существует бесконечно много простых чисел.

Решение

Предположим противное. Пусть p₁, p₂, ..., p_n – все простые числа. Рассмотрим число  p₁p₂...p_n + 1.  Это число не делится ни на одно из чисел p₁, p₂, ..., p_n и, следовательно, не может быть разложено в произведение простых. Противоречие.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	3
Название	Алгоритм Евклида и основная теорема арифметики
Тема	Алгебра и арифметика
параграф
Номер	1
Название	Простые числа
Тема	Основная теорема арифметики. Разложение на простые сомножители
задача
Номер	03.001
книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	4
Название	Делимость и остатки
Тема	Теория чисел. Делимость
задача
Номер	053