как доказать что простых чисел бесконечно много
Как понять теорему Евклида о бесконечном множестве простых чисел?
Не могу понять эту теорему. Вот нашел текст доказательства:
Доказательство от противного. Допустим, что простых чисел конечное множество, т. е есть наибольшее простое, назовем его Р. Перемножим все простые числа от 2 до Р и добавим 1:
Но как вот по этому факту:
сделали вот эти два вывода:
или оно составное, тогда оно должно делиться на некоторое простое число, бОльшее чем Р, но это тоже противоречит предположению.
. Не улавливаю причинно-следственной связи.
Любое натуральное число, большее 1, имеет простой делитель.
M > 1, следовательно, имеет простой делитель, который не может совпадать ни с одним из входящих в рассмотренное произведение, так как не делится ни на один из них.
Представим, что количество простых чисел конечно. Перемножим их и прибавим единицу. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включённое в этот набор.
Основная теорема арифметики утверждает, что любое составное число может быть разложено в произведение простых множителей
Отнюдь не понятнее, по прежнему не понятно, как по этому факту:
>Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу.
>Значит, число должно делиться на некоторое простое число, не включённое в этот набор.
Но товарищ AVKor мне уже объяснил. Правило
>Любое натуральное число, большее 1, имеет простой делитель.
отвечает на все вопросы, и теорема арифметики действительно не нужна.
vibe-vibe: Как раз таки из:
>Основная теорема арифметики утверждает, что любое составное число может быть разложено в произведение простых множителей
Следует что:
Любое натуральное число, большее 1, имеет простой делитель
————
Т.е я всё верно привел.
D’ Normalization: Всё ровно наоборот. Основную теорему арифметики как раз выводят из существования простого делителя у любого натурального числа, большего 1.
Кроме того, основную теорему формулируют не для составных чисел, а любых натуральных, больших 1 (можно и 1 тоже включить, что сделано в книге Айерленда и Роузена).
И M не обязательно составное (и это и не требуется).
Предполагается, что всего существует ограниченное количество простых чисел, причем значение каждого из них нам известно: 2, 3, 5, 7 и так далее вплоть до самого большого простого числа P – и всё, больше простых чисел нет. Все остальные (даже очень большие) натуральные числа большие P – числа составные – их можно представить в виде произведения некоторого количества этих простых чисел, каждое из которых может быть взято некоторое количество раз.
Рассмотрим число M: оно больше P, и тогда, исходя из сказанного выше, оно должно быть составным. Но тогда M должно делится на хотя бы на одно простое число из нашего набора известных простых чисел без остатка, а это не так. Следовательно, изначальное утверждение неверно. А неверно оно может быть двумя способами: или M – всё-таки составное, но между P и M существует еще одно или несколько простых чисел больше P, на которые M делится без остатка (например, 2*3*5*7*11*13*17 + 1 = 510511 = 19*97*227 – примеры таких чисел), или само число M – простое (например, 2*3*5*7 + 1 = 211 – 47-е простое число), что впрочем вовсе не значит, что между P и M нет других простых чисел.
В любом случае мы находим простое число большее известного нам «наибольшего простого числа» P, и это число само становится «наибольшим простым числом» – а так как подобную операцию можно проделать с любым «наибольшим простым числом», то получается, что «наибольшего простого числа» не существует, иначе говоря, количество простых чисел бесконечно.
>или M – всё-таки составное
>или само число M – простое
Посмотрите на ответ пользователя AVKor, он мне дает ответ на этот вопрос. А может, вы изначально предполагали, что я знаю это правило?
Бесконечность множества простых чисел
Одним из свойств простых чисел является утверждение, что множество простых чисел бесконечно, то есть среди простых чисел нет наибольшего. Доказал это свойство Евклид, поэтому его называют теоремой Евклида. При этом он использовал метод от противного.
Доказательство бесконечности множества простых чисел
Предположим обратное – множество простых чисел конечно. Тогда все остальные числа являются составными.
Если множество простых чисел конечно, значит, мы можем перемножить все простые числа между собой. Найдем их произведение и к результату добавим единицу.
Очевидно, полученное число больше любого из простых. Из предположения, что множество простых чисел конечно, следует, что получившееся число составное.
Но если оно составное, то должно при разложении на множители содержать простые сомножители. Однако это не могут быть множители, которые использовались при нахождении этого числа. Ведь к результату была добавлена единица.
Следовательно, произведение уже не делится нацело ни на одно из ранее использованных простых чисел. Потому что будет оставаться остаток 1. Это значит, что должны быть другие простые делители, если уж число действительно составное. Или же само число должно быть простым.
Отсюда приходим к выводу, что всегда найдутся другие простые числа, сколько бы простых чисел мы не использовали для нахождения произведения с последующим добавлением единицы.
2 × 3 × 5 × 7 + 1 = 211. Число 211 само является простым.
2 × 3 × 5 × 7 × 11 × 13 + 1= 30031. Это число делится на 59, которое является простым.
В первом случае произведение простых чисел, сложенное с единицей, само оказалось простым числом. Во втором случае был найден простой делитель, которого не использовался для нахождения произведения.
Таким образом, какой бы исходный список простых чисел не взяли, мы так или иначе найдем новое простое число. Им окажется либо само произведение + 1, либо простое число, которое больше исходных сомножителей, если они были взяты подряд от самого наименьшего простого числа.
Научный форум dxdy
Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Правила форума
В этом разделе нельзя создавать новые темы.
Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе «Помогите решить/разобраться (М)».
Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.
Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.
Бесконечность простых вида 6m+1[Теория чисел]
 |
Здравствуйте, дорогие друзья!
Доказать, что простых чисел вида 
бесконечного много.
Мой эскиз доказательства: Пусть простых чисел вида конечное число и обозначим их через 
и пусть 
.
Рассмотрим такое число 
. Нетрудно проверить, что число 
имеет вид так как 
и 
. Кроме того, число не делится ни на одно из чисел 
.
Первый случай: Если — простое число, тогда все хорошо.
Второй случай: Если — составное число, тогда он делится на некоторое простое число 
. Отсюда вытекает, что имеет вид и 
. В
обоих случаях получаем противоречие.
Во втором случае использовалось следующее утверждение: Сравнение 
разрешимо тогда и только тогда, когда имеет вид .
Скажите пожалуйста это доказательство правильное?
С уважением, Whitaker.
| Заслуженный участник |
 |
Верно. Можно слегка усилить утверждение и доказать тем же методом, что простых чисел вида 
бесконечно много.
Вот ещё для тренировки список прогрессий, где метод Евклида работает: 
, 
, 
, 
, 
, , 
. Можно также попробовать разобраться с прогрессией 
, где 
1$» title=»$m>1$» /> произвольно, но здесь понадобятся круговые многочлены.
|
Верно. Можно слегка усилить утверждение и доказать тем же методом, что простых чисел вида бесконечно много.
Вот ещё для тренировки список прогрессий, где метод Евклида работает: , , , , , , . Можно также попробовать разобраться с прогрессией , где 1$» title=»$m>1$» /> произвольно, но здесь понадобятся круговые многочлены.
| Заслуженный участник |
|
|
Последний раз редактировалось Whitaker 26.07.2014, 14:02, всего редактировалось 2 раз(а).
Да было бы отлично! Отправьте пожалуйста.
nnosipov
Хочу такой вопрос спросить. Я вот могу доказать при каких числа 
будет квадратичным вычетов. Для чисел 
аналогичное рассуждение?
| Заслуженный участник |
|
Кто сейчас на конференции
Сейчас этот форум просматривают: нет зарегистрированных пользователей
5 самых старых нерешенных задач Математики о простых числах
Математика была предметом, который веками бросал вызов величайшим умам в истории человечества. Пожалуй, одной из наиболее исследуемых областей Математики является изучение простых чисел.
Наши размышления о закономерностях в простых числах привели к некоторым сложнейшим проблемам, нерешенным даже величайшими математическими гениями. Сегодня мы рассмотрим 5 старейших математических задач о простых числах, которые интуитивно понятны старшекласснику, но все еще не доказаны даже после упорных попыток в течение 500-2000 лет.
1. Совершенные числа: существуют ли нечетные совершенные числа? Бесконечны ли четные совершенные числа?
Рассмотрим числа 6, 28, 496, 8128…
Что в них особенного? Если вы не знаете, то я бы посоветовал сделать небольшую паузу и попытаться найти красивое свойство, которым обладают эти числа.
Если посмотреть на собственные делители этих чисел, то нетрудно заметить то самое «красивое» свойство:
Числа, для которых сумма собственных делителей равна самому числу, называются совершенными числами. Самое раннее исследование совершенных чисел затеряно в истории. Однако, мы знаем, что пифагорейцы 525годдон.э. изучали совершенные числа.
Что мы знаем о таких числах?
Евклид доказал, что для данного n, если 
— простое число, то 
— совершенное число. В качестве упражнения попробуйте доказать это самостоятельно.
Окей, краткий экскурс.
Простые числа Мерсенна: простые числа вида 
для некоторого n. Мерсенн предположил, что все числа вида 
простые, когда n простое. (Мы знаем, что это неправда. Например, 
).
Открытый вопрос: существует ли бесконечно много простых чисел Мерсенна? На данный момент нам известно 47 простых чисел Мерсенна.
В 18 веке Эйлер показал обратное: любое четное совершенное число имеет вид 
Другими словами, существует взаимно однозначное соответствие между четными совершенными числами и простыми числами Мерсенна.
Как видите, мы знаем о четных совершенных числах и способах их получения еще со времен Евклида около300годдон.э.. Но нам неизвестно, существую ли нечетные совершенные числа. насамомделе,прогрессврешенииэтойпроблемыпрактическиотсутствует.
Подводя итог, можно сказать, что изучение совершенных чисел ставит две давние открытые проблемы, а именно «существование нечетных совершенных чисел» и «существование бесконечно большого числа простых чисел Мерсенна».
Евклид (ок. 300 г. до. н. э.) первым доказал то, что простых чисел бесконечно много.
2. Гипотеза о близнецах: простых чисел-близнецов бесконечно много
Простые числа-близнецы — это пара вида (p, p + 2), где p и p + 2 являются простыми числами.
Точное происхождение гипотезы о простых числах-близнецах не установлено. Первая формулировка гипотезы о простых числах-близнецах была дана в 1846 году французским математиком Альфонсом де Полиньяком. Однако греческий математик Евклид дал старейшее из известных доказательств существования бесконечного числа простых чисел. Но он не предполагал, что существует бесконечное число простых чисел-близнецов.
На протяжении 2000 лет в доказательстве этого утверждения практически не было прогресса.
Что мы знаем!
Существует бесконечно много простых пар вида (p, p + k), где k = 4 на самом деле является суммой не более чем 6 простых чисел (т.е. С
Дата-центр ITSOFT — размещение и аренда серверов и стоек в двух дата-центрах в Москве. За последние годы UPTIME 100%. Размещение GPU-ферм и ASIC-майнеров, аренда GPU-серверов, лицензии связи, SSL-сертификаты, администрирование серверов и поддержка сайтов.
math4school.ru
Бесконечность ряда простых чисел
Постановка вопроса
Число 6 равно произведению двух чисел: 2 и 3. Число 7 нельзя разложить подобным образом на два сомножителя. Поэтому 7 называют простым числом. Вообще простым или первоначальным числом называется целое положительное число, которое нельзя разложить на два меньших сомножителя. 5 и 3 тоже простые числа; напротив, число 4 не простое, так как
Сама двойка также является простым числом. По отношению к 1 обсуждение вопроса о возможности разложения числа на множители теряет смысл. Таким образом, первые простые числа суть
С первого же взгляда видно, что ряд несколько причудлив; никакого простого закона в его строении непосредственно не обнаруживается.
Любое число можно разлагать на сомножители до тех пор, пока оно не распадется на одни только простые числа. Представив 6 в виде 2 · 3, мы убеждаемся в этом для 6 непосредственно;
является произведением трех простых сомножителей;
24 = 3 · 8 = 3 · 2 · 4 = 3 · 2 · 2 · 2
разлагается на четыре сомножителя, из которых один, именно 2, повторяется несколько раз. Ясно, что при допущении таких повторений подобное разложение на простые множители осуществимо для всякого числа. Поэтому простые числа являются в этом смысле как бы основными элементами, из которых построен весь числовой ряд.
В IX книге «Начал» Евклида ставится вопрос: имеет ли последовательность простых чисел конец? И там же дается ответ на этот вопрос: доказывается, что ряд простых чисел бесконечен, т.е. за каждым простым числом может быть указано еще одно, большее простое число.
Доказательство Евклида
Доказательство Евклида необычайно остроумно. Оно основывается на следующем простом замечании. Таблица, получающаяся при умножении последовательных чисел на 3:
содержит все числа, в которые входит множителем число 3; ни в какое другое число 3 не входит, в частности, оно не входит ни в одно из тех чисел, которые следуют непосредственно за числами этой последовательности, т.е. за кратными числа 3. Таковы, например,
19 = 6 · 3 + 1, 22 = 7 · 3 + 1 и т.д.
Подобным же образом число 5 не может быть множителем числа, следующего непосредственно за числами, кратными 5, например числа
то же самое будет верно по отношению к 7, 11 и т.д.
Евклид строит числа
2 · 3 · 5 · 7 + 1 = 311;
2 · 3 · 5 · 7 · 11 + 1 = 2311;
2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 и т.д.,
которые получаются перемножением нескольких первых простых чисел и прибавлением единицы к полученному произведению.
Легко видеть, что получающиеся таким образом числа не могут содержать в качестве множителей тех простых чисел, с помощью которых они сами были построены. Например, последнее из выше написанных чисел не делится на 3, так как оно на 1 больше числа, кратного 3; но оно же на 1 больше числа, кратного 5 или любого другого использованного при его образовании простого числа. Ни одно из чисел
не может, следовательно, войти в него множителем. Если бы поэтому в противоположность числам
являющимися простыми, число 30031 было не простым, то можно быть все же уверенным в том, что ни одно из чисел
уже не входит в него множителем и что самый меньший его простой множитель должен быть больше 13. И действительно, путем нескольких проб можно обнаружить, что
оба эти числа – и 59, и 509 – простые числа, большие 13.
Это рассуждение будет справедливо и в том случае, если мы продолжим процесс образования таких чисел сколь угодно далеко. Пусть р – какое-либо простое число; образуем из всех простых чисел от 2 до р число
тогда ни одно из использованных здесь простых чисел
Неизвестно, что должно нас больше всего удивлять в этом тексте Евклида: то ли, что греческие математики вообще могли поставить подобный вопрос ради него самого, из внутреннего влечения к математическому мышлению, т.е. по мотивам, не свойственным ни одному из более древних народов и переданным в наследство позднейшим культурам лишь греческой традицией; или то, что они поставили именно этот вопрос, столь легко ускользающий от наивного наблюдателя, кажущийся ему праздным и тривиальным, вопрос, вся трудность и глубина которого раскрывается лишь тому, кто безуспешно пытался отыскать простой закон для ряда простых чисел,
закон, позволяющий неограниченно продолжать этот ряд. Пожалуй, самым удивительным здесь нужно считать то, что греки сумели обойти отсутствие подобной закономерности тем искусным приемом доказательства, с которым мы только что познакомились.
Пробелы в ряде простых чисел
Чтобы дать здесь несколько более конкретное представление о сложности этой структуры, мы покажем, что в ряде простых чисел могут быть сколь угодно большие пробелы. Так, например, мы покажем, что среди тысячи следующих друг за другом чисел может не оказаться ни одного простого числа. Мы исходим при этом из соображений, весьма близких к евклидовым.
Выше мы заметили, что число
не делится ни на одно из простых чисел 2, 3, 5. Воспользуемся теперь тем простым обстоятельством, что сумма двух чисел, делящихся на 3, также делится на 3 и что подобное свойство остается верным для 5, 7, а также и для всякого другого делителя. Отсюда мы заключаем, что ни одно из чисел
не может быть простым; ведь число, прибавляемое к 30, делится во всех этих случаях или на 2, или на 3, или на 5, а так как 30 также делится на них, то делится и сумма. Лишь в отношении следующей за ними суммы
так рассуждать уже нельзя, и действительно, число 37 не делится ни на 2, ни на 3, ни на 5, и потому оно само является простым числом.
Обозначив теперь первое простое четырехзначное число, а именно 1009, через р и образовав тысячу последовательных чисел
применим к ним только что проиллюстрированный метод рассуждения. Так как каждое из чисел
делится, по крайней мере, на одно из простых чисел
делится на все эти числа, то каждая из выше написанных сумм делится, по крайней мере, на одно
из этих простых чисел; это значит, что ни одна из них не может быть простым числом. Итак, мы нашли тысячу последовательных чисел, среди которых нет ни одного простого.
Конечно, нужно зайти довольно далеко в ряду простых чисел, прежде чем встретится такого рода пробел. Но если пойти достаточно далеко, то можно, следуя тому же принципу, найти пробел, охватывающий миллион последовательных чисел, и вообще пробелы сколь угодно большой величины.
Эта вторая проблема, сколь ни близка она к первой как по характеру постановки вопроса, так и по методу доказательства, не встречается ни у кого из греческих математиков. Ее выдвинула новая математика, связав с нею целый круг дальнейших вопросов, доказываемых в большинстве случаев уже далеко не столь просто; из этих вопросов развилась одна из глубочайших, одна из самых волнующих своими нерешенными проблемами областей математического анализа.
«Разные» простые числа
Мы остановимся здесь на одном небольшом примере, который поддается исследованию методом Евклида и позволяет составить некоторое представление о том, в каком именно направлении математика нового времени расширяет проблематику греков. Выше мы рассматривали сначала числа
получающиеся от умножения последовательности чисел натурального ряда на 3, а затем последовательность следующих за ними чисел
теперь рассмотрим еще оставшиеся после этого числа:
т.е. числа, которые при делении на 3 дают в остатке 2. Покажем, что и среди одних только этих чисел содержится уже бесчисленное множество простых чисел, т.е. покажем, что последовательность простых чисел
также не имеет конца.
Доказательство нуждается в простом предварительном замечании. Если перемножить между собой два каких-либо числа последовательности
то получается число, принадлежащее к этой же последовательности. Действительно, все эти числа при делении на 3 дают в остатке единицу и имеют вид:
где z – целое число; если перемножить два таких числа, например
т.е. опять число вида
Из этого простого замечания следует, что среди простых множителей любого из чисел последовательности
всегда найдется, по крайней мере, один, принадлежащий к этой же последовательности. Так, например, для
таковым является множитель 2, а для
– множитель 5. Действительно, ни один из таких простых множителей не может принадлежать к ряду
в котором имеется лишь одно-единственное простое число 3. С другой стороны, если бы рассматриваемое число состояло из одних только простых множителей, принадлежащих к последовательности
то, согласно предыдущему замечанию, оно само должно было бы принадлежать к этой же последовательности. Таким образом, чтобы число принадлежало к последовательности
оно должно содержать, по меньшей мере, один простой множитель, принадлежащий к этой же самой последовательности.
Теперь мы сможем легко доказать высказанное выше утверждение. Для этого придется только несколько видоизменить доказательство Евклида, а именно вместо выражения
которое, будучи на единицу меньше кратного 3, принадлежит к последовательности
Таким образом, в этой последовательности заведомо имеются простые числа, превышающие сколь угодно большое простое число р и расположенные, следовательно, сколь угодно далеко.
Этим, однако, еще не предрешается вопрос о том, содержит ли также и последовательность
бесконечно много простых чисел; нет ничего невозможного в предположении, что из всей совокупности простых чисел бесконечно много их приходится на последовательность
и только конечное число – на последовательность
общее их количество при этом по-прежнему остается бесконечно большим. Доказательство того, что и вторая последовательность содержит также бесконечно много простых чисел, требует уже совершенно других методов.
Иначе обстоит дело с последовательностями:
Методами, схожими с приведёнными выше, можно доказать наличие в каждой из них бесконечного числа простых чисел.
Источник: Ганс Радемахер, Отто Тепліц. Числа і фігури (Тернопіль, «Навчальна книга – Богдан», 2010).