Задача 7.6 ∗ . Конечно или бесконечно множество про- стых чисел? Обсуждение

сложным, не так ли? Во всяком случае, конечно ли мно-
жество пар простых чисел-близнецов (т. е. отличающих-
ся друг от друга на 2), неизвестно до сих пор. Как не
найдено и никакой формулы, позволяющей бесконечно
вычислять одно простое число за другим. А некоторые
простые по формулировке вопросы теории чисел реше-
ны весьма сложными современными методами (например,
великая теорема Ферма или тернарная проблема Гольд-
баха). Но вот вопрос о бесконечности множества простых
чисел древние греки смогли не только поставить, но и
решить. Приведем удивительное по красоте и простоте
доказательство от противного, восходящее к «Началам»
Евклида.
Решение. Пусть множество простых чисел конечно. То-
гда можно выписать все простые числа: p
1
, p
2
, p
3
, . . . , p
n
.
Произведение всех этих чисел делится на каждое из них.
А если его немножко «испортить», прибавив 1, то полу-
ченное число: p
1
p
2
p
3
. . . p
n
+ 1 не будет делиться ни на
одно из простых чисел p
1
, p
2
, p
3
, . . . , p
n
. Можно ли это
число разложить на простые множители? Если можно,
то среди этих простых множителей нет известных нам
чисел p
1
, p
2
, p
3
, . . . , p
n
(то есть мы выписали не все про-
стые числа!). А если нельзя, то это число само простое,
причем большее всех выписанных нами чисел. В любом
случае выписать все простые числа не удалось. Значит, их
множество бесконечно.
Комментарий. Является ли приведенное доказатель-
ство доказательством от противного? Если да, то требова-
лось бы доказать, что из А следует Б. А мы вместо этого
доказывали бы, что из «не Б» следует «не А». Но где же
условие А? В задаче вообще ничего не дано!
Условие А появится, если переформулировать задачу
так: «Пусть дано множество всех простых чисел. Дока-
зать, что оно бесконечно». Предположив, что множество
простых чисел конечно, мы убедились, что рассмотрели
не все простые числа.
70

Метод от противного оказался эффективен, потому что
помог от бесконечного количества, с которым непонятно
что делать, перейти к конечному, которое можно перечис-
лить. А затем придумать, как по любому конечному набо-
ру простых чисел указать еще одно простое число. Теперь,
когда решение придумано, его можно изложить и без ха-
рактерных для метода от противного слов: возьмем про-
извольный набор простых чисел, к ним можно добавить
еще одно, затем еще одно и т. д. Так можно делать сколь-
ко угодно раз, поэтому простых чисел бесконечно много.
Еще раз убеждаемся, что сила метода от противного не в
магических заклинаниях: он и без них работает!

жүктеу/скачать 1.3 Mb.

Достарыңызбен бөлісу: