Доказательство того что простых чисел бесконечно много

Доказательство того что простых чисел бесконечно много

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

Решение

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

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

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

Проект осуществляется при поддержке и .

Теоремы о простых числах

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

Простых чисел бесконечно много.

Теорема о расходимости ряда [math]\sum_<>^<>1/n[/math]

Ряд [math]\sum_<>^<>1/n[/math] расходится.

Заметим для некоторого [math]k[/math] : [math]\sum_

^<><(1 + \frac

+ \frac + \cdots)> \ge \sum_ \frac[/math] . Теперь, пользуясь выражением [math] \ln(1+x) \approx x + o(x) [/math] и логарифмируя, выводим: [math] \sum_

<\ln(1 + \frac

+ \frac + \cdots)> \approx \sum_

< (\frac

+ \frac + \cdots)> \le \frac [/math] — расходится.

Теорема о расходимости ряда [math]\sum_<>^<>1/p[/math]

Ряд [math]\sum_<>^<>1/p[/math] , где [math]p[/math] — простое, расходится.

Работая в условиях предыдущей теоремы, продолжаем: [math] \ln(1+x) \le x[/math] , тогда [math] \sum_<>^<> <\ln(1 + \frac

+ \cdots)> \le \sum_<>^<> <( \frac

+ \frac + \cdots)>[/math] .

Доказательство того что простых чисел бесконечно много

Определение. Число р О N , р № 1, называется простым, если р имеет в точности два положительных делителя: 1 и р . Остальные натуральные числа (кроме 1) принято называть составными. Число 1 — на особом положении, по договору, оно ни простое, ни составное.

Как это часто бывает в математике, да и в других науках, прилагательным «простой» называется объект только первоначально казавшийся простым. Простые числа, как выяснилось в процессе накопления научных знаний, появляются в различных областях математики и являются одним из самых загадочных и тяжелых для изучения монстров. Любопытного читателя, любителя ужастиков и лихо закрученных сюжетов, я отсылаю здесь к изумительному рассказу математика из Боннского университета Дон Цагира «Первые пятьдесят миллионов простых чисел», опубликованному в книжке «Живые числа», М.: Мир, 1985 г.

Отметим некоторые несложные наблюдения, связанные с простыми числами.

Наблюдение 1. Наименьший делитель любого числа а О N , отличный от 1, есть число простое.

Доказательство. Пусть с | а , с № 1 и с — наименьшее с этим свойством. Если существует с 1 такое, что с 1 | с , то с 1 Ј с и с 1 | а , следовательно, с 1 = с или с 1 = 1.

Наблюдение 2. Наименьший отличный от 1 делитель составного числа а О N не превосходит Ц a .

Доказательство. с | а , с № 1, с — наименьший, следовательно

а = са 1 , а 1 | а , а 1 і с , значит аа 1 і с 2 а 1 , а і с 2 и с Ј Ц a .

Следующее наблюдение, отдавая дань уважения его автору — Евклиду, назовем теоремой.

Теорема (Евклид). Простых чисел бесконечно много.

Доказательство. От противного. Ну пусть р 1 , р 2 . р n — все простые, какие только есть. Рассмотрим число а = р 1 р 2 . р n + 1. Его наименьший отличный от 1 делитель с , будучи простым, не может совпадать ни с одним из р 1 , р 2 . р n , так как иначе с | 1. Не перестаю удивляться изобретательности ума людей тысячелетней древности!

Для составления таблицы простых чисел древний грек Эратосфен придумал процедуру, которая получила название «решето Эратосфена»:

2, 3, 4 , 5, 6 , 7, 8 , 9 , 10 , 11, 12 , 13, 14 , 15 , 16 , 17.

Идем по натуральному ряду слева направо. Подчеркиваем первое неподчеркнутое и невычеркнутое число, а из дальнейшего ряда вычеркиваем кратные только что подчеркнутому. И так много раз. Легко понять, что подчеркнутые числа — простые. Если вспомнить наблюдение 2, то становится понятно, что когда вычеркнуты все кратные простых, меньших р , то оставшиеся невычеркнутые, меньшие р 2 — простые. Это значит, что составление таблицы всех простых чисел меньших N закончено сразу, как только вычеркнуты все кратные простых, меньших Ц a .

Для чисел, растущих закономерно, например для квадратов или степеней двойки, было бы, конечно, нелепо разыскивать экземпляр, превосходящий все известные. Для простых же чисел, напротив, прилагаются громадные усилия, чтобы именно это и сделать. Чудаки люди! Например, в 1876 году француз Люка доказал, что число 2 127 — простое, и 75 лет оно оставалось наибольшим из известных простых чисел, что не покажется удивительным, если на него взглянуть:

2 127 -1 = 170141183460469231731687303715884105727.

В настоящее время составлены таблицы всех простых чисел, не превосходящих 50 миллионов, далее известны только отдельные их представители. Читателей всегда привлекает гигантизм, поэтому укажу здесь два самых больших известных на сегодняшний момент простых числа: 2 44497 — 1 и 2 86243 — 1. Последнее число записано пока в книгу рекордов Гиннеса, в нем 25962 десятичных знака. Найдено оно было, конечно, в рекламных целях — демонстрация фирмой IBM возможностей очередного суперкомпьютера, которому для проверки этого числа на простоту с помощью специальных изощренных тестов (пригодных только для чисел вида 2 n- 1) потребовалась неделя работы и куча денег. И это трата денег происходит в то время, когда у нас в России более трети населения живет за чертой бедности, а половина детей в Уганде не умеют ни читать, ни писать, а только сидят и гундят!

Самой важной и общеизвестной в этом пункте является следующая теорема (искушенные алгебраисты скажут, что она утверждает факториальность кольца Z , а я воздержусь от каких-либо комментариев в адрес этой теоремы, ибо про столь важную персону математического мира надо либо долго говорить, либо почтенно молчать). Эта теорема носит название «Основной теоремы арифметики».

Теорема. Всякое целое число, отличное от — 1, 0 и 1, единственным образом (с точностью до порядка сомножителей) разложимо в произведение простых чисел.

Доказательство. Будем доказывать утверждение теоремы только для натуральных чисел, ибо знак минус перед числом умеют ставить все умеющие ставить знак минус.

Пусть а > 1, р 1 — его наименьший простой делитель. Значит,

а = р 1 а 1 . Если, далее, а 1 > 1, то пусть р 2 — его наименьший простой делитель и а 1 = р 2 а 2 , т.е. а = р 1 р 2 а 2 , и так далее, пока а n не станет равным единице. Это обязательно произойдет, так как а > а 1 > а 2 . а натуральные числа с естественным порядком удовлетворяют условию обрыва убывающих цепей (во как выразился!). Имеем, таким образом,

a = p 1 p 2 . p n , и возможность разложения доказана.

Покажем единственность. Ну пусть a = q 1 q 2 . q n — другое разложение, т.е. p 1 p 2 . p n = q 1 q 2 . q s . В последнем равенстве правая часть делится на q 1 , следовательно, левая часть делится на q 1 . Покажем, что если произведение p 1 p 2 . p n делится на q 1 , то один из сомножителей р k обязан делиться на q 1 .

Действительно, если q 1 | p 1 , то все доказано. Пусть q 1 не делит p 1 . Так как q 1 — простое число, то ( q 1 , p 1 ) = 1. Значит найдутся такие

u , v О Z , что up 1 + vq 1 = 1. Умножим последнее равенство на p 2 . p n , получим: p 2 . p n = p 1 ( p 2 . p n ) u + q 1 ( p 2 . p n ) v . Оба слагаемых справа делятся на q 1 , следовательно, p 2 . p n делится на q 1 . Далее рассуждайте по индукции сами.

Теперь пусть, например, q 1 | p 1 . Значит q 1 = p 1 , так как p 1 — простое. Из равенства p 1 p 2 . p n = q 1 q 2 . q s банальным сокращением моментально получим равенство p 2 . p n = q 2 . q s . Снова рассуждая по индукции, видим, что n = s , и каждый сомножитель левой части равенства p 1 p 2 . p n = q 1 q 2 . q n обязательно присутствует в правой и наоборот.

Сразу отмечу без доказательства два достаточно очевидных следствия из этой теоремы.

Следствие 1. Всякое рациональное число однозначно представимо в виде

p

a 1 1

p

a 2 2

. p

a k k

,

где a 1 , a 2 . a k О Z .

Бесконечность множества простых чисел

Одним из свойств простых чисел является утверждение, что множество простых чисел бесконечно, то есть среди простых чисел нет наибольшего. Доказал это свойство Евклид, поэтому его называют теоремой Евклида. При этом он использовал метод от противного.

Доказательство бесконечности множества простых чисел

Предположим обратное – множество простых чисел конечно. Тогда все остальные числа являются составными.

Если множество простых чисел конечно, значит, мы можем перемножить все простые числа между собой. Найдем их произведение и к результату добавим единицу.

Очевидно, полученное число больше любого из простых. Из предположения, что множество простых чисел конечно, следует, что получившееся число составное.

Но если оно составное, то должно при разложении на множители содержать простые сомножители. Однако это не могут быть множители, которые использовались при нахождении этого числа. Ведь к результату была добавлена единица.

Следовательно, произведение уже не делится нацело ни на одно из ранее использованных простых чисел. Потому что будет оставаться остаток 1. Это значит, что должны быть другие простые делители, если уж число действительно составное. Или же само число должно быть простым.

Отсюда приходим к выводу, что всегда найдутся другие простые числа, сколько бы простых чисел мы не использовали для нахождения произведения с последующим добавлением единицы.

2 × 3 × 5 × 7 + 1 = 211. Число 211 само является простым.

2 × 3 × 5 × 7 × 11 × 13 + 1= 30031. Это число делится на 59, которое является простым.

В первом случае произведение простых чисел, сложенное с единицей, само оказалось простым числом. Во втором случае был найден простой делитель, которого не использовался для нахождения произведения.

Таким образом, какой бы исходный список простых чисел не взяли, мы так или иначе найдем новое простое число. Им окажется либо само произведение + 1, либо простое число, которое больше исходных сомножителей, если они были взяты подряд от самого наименьшего простого числа.