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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Как понять теорему Евклида о бесконечном множестве простых чисел?

Не могу понять эту теорему. Вот нашел текст доказательства:

Доказательство от противного. Допустим, что простых чисел конечное множество, т. е есть наибольшее простое, назовем его Р. Перемножим все простые числа от 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, он мне дает ответ на этот вопрос. А может, вы изначально предполагали, что я знаю это правило?

Источник

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-сертификаты, администрирование серверов и поддержка сайтов.

Источник

Научный форум 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
Хочу такой вопрос спросить. Я вот могу доказать при каких числа будет квадратичным вычетов. Для чисел аналогичное рассуждение?

Заслуженный участник

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей

Источник

Закономерности в распределении простых чисел

Введение

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

Ещё до нашей эры Евклид сформулировал и доказал первые теоремы о простых числах. С тех пор математики, среди них Гаусс, Ферма, Риман, Эйлер, продолжали исследования и надо отдать им должное заметно продвинулись. Было обнаружено много интересных свойств простых чисел, выдвинуто много предположений, некоторые из которых были доказаны. Однако много гипотез связанных с простыми числами до сих пор остаются необоснованными.

Распределение простых чисел

Первостепенная задача, решение которой автоматически привело бы к решению большинства вопросов связанных с простыми числами заключается в следующем:

Получить рекуррентную формулу для очередного простого числа

Существует родственная ей задача о количестве простых чисел, не превосходящих заданной величины:

Найти функцию p(x), значение которой в точке x равно числу простых чисел на отрезке [1, x]. Где x – любое действительное число не меньшее единицы.

Функция называется функцией распределения простых чисел.

К решению вышеуказанных задач существует множество подходов. Рассмотрим некоторые из них.

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

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

Первое простое число p₁ =2. Значит все последующие простые числа должны не делится на 2, то есть иметь вид 2k+1, где k – натуральное. То есть все простые числа начиная со второго — нечётные.

Второе простое число p₂ = 3. Значит все последующие простые числа должны иметь вид 3m+1, либо 3m+2, где m – целое. Это равносильно утверждению о том, что все простые числа начиная с третьего не делятся на три. Однако при этом числа ещё должны не делится на два, то есть иметь вид 2k+1.

Решая диофантовы уравнения

найдём k и m и получим, что все простые числа начиная с p₃ обязательно представимы в виде , либо в виде , где t – целое.

И правда, какое бы простое число мы ни взяли оно представимо таким образом:

Однако обратное неверно, то есть любое натуральное число вида 6t+1 или 6t+5 не обязательно простое. Например, .

Третье простое число p₃ = 5. И если по аналогии учесть, что любое простое число, начиная с четвёртого не делится на 5, также не делится на p₁ = 2 и на p₂ = 3, то получим, что все простые числа начиная с p₄ обязательно имеют одно из представлений

Затем учтём p₄, p₅ и т.д. Проблема в том, что на каждом шаге нам придётся решать всё большую систему диофантовых уравнений, поэтому такой прямолинейный подход оказывается весьма сложным.

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

Итак, как же найти функцию F(x)? Сначала рассмотрим множество всех натуральных чисел. Какова доля чисел, которые не делятся ни на одно из простых p₁, p₂, …, p_n?

Каждое второе число делится на p₁ = 2. Значит, часть всех чисел делится на p₁.

Каждое третье число делится на 3. Значит, всех чисел делится на p₂. При этом надо учесть, что каждое шестое число делится и на 2 и на 3 одновременно.

Значит, доля чисел не делящихся ни на 2, ни на 3 равна

Если преобразовать выражение, то оно примет вид:

Опять же можно представить выражение в виде

Будем обозначать такое произведение P(n). Кстати, если учесть все простые числа (n→∞), то мы получим обратную величину от так называемого произведения Эйлера.

Почему так происходит? Когда мы получали формулу (1), мы пользовались рассуждениями, что среди всех натуральных чисел доля, делящихся на p_n, равна . Но нельзя сделать такое утверждение о конечном наборе последовательных натуральных чисел. Например, возьмём набор 1,2, 3,4,5,6,7,8,9. Здесь 4 числа из 9 делятся на два. И несложно заметить, что отличается от . То есть, при применении к конечному набору чисел, данный метод даёт результат с некоторой погрешностью.

Это будет мешать далее получать точные формулы. Но если оценить эту погрешность, то можно (например, приняв и используя приведённые выше рассуждения) получить оценку для p_n+1-го простого числа. Однако, получение таких оценок — это тема отдельной работы. И поэтому здесь я не буду на этом останавливаться, а приведу лишь некоторые результаты, полученные математиками.

Одна из оценок для простого числа с номером n:

оценка верна для всех n, начиная с 6.

А вот формула для функции распределения простых чисел:

Для функции Риман получил приближение, используя интегральный логарифм и нетривиальные нули дзета-функции Римана. Однако, это приближение верно, только если верна гипотеза Римана. Причём если гипотеза Римана верна, то оно является наилучшим.

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

Проблемы Ландау

Насчёт простых чисел выдвинуто очень много интересных гипотез. Среди них видное место занимают гипотезы Ландау (проблемы Ландау). Формулируются они так:

1. Гипотеза Гольдбаха

Можно ли любое целое чётное число, большее 2, записать в виде суммы двух простых?

2. Гипотеза о числах-близнецах

Бесконечно ли число простых p таких, что p + 2 тоже простое?

3. Гипотеза Лежандра

Всегда ли существует по меньшей мере одно простое число, лежащее между двумя последовательными полными квадратами?

4. Гипотеза о почти квадратных простых числах

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

Проблемы Ландау ни доказаны, ни опровергнуты по состоянию на 2020 год. Далее кратко расскажу про каждую из них.

1. Гипотеза Гольдбаха

Существуют две гипотезы Гольдбаха: слабая (тернарная) и сильная (бинарная).

Слабая гипотеза Гольдбаха: Каждое нечётное число, большее 5, можно представить в виде суммы трёх простых чисел.

Эту гипотезу доказал Харольд Гельфготт в 2013 году используя так называемые большие дуги. Финальная часть доказательства заняла 133 страницы.

Сильная гипотеза Гольдбаха: Каждое чётное число, большее двух, можно представить в виде суммы двух простых чисел.

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

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

Но переформулируем проблему так: существует ли такое число, что любое нечётное, большее этого числа, представимо в виде суммы двух простых чисел? Давайте проверим. Пусть существует некоторое нечётное натуральное число N, такое, что любое нечётное число представимо в виде суммы двух простых чисел.

Возьмём произвольное нечётное . По предположению существуют такие простые p₁ и p₂, что . Если сумма двух натуральных чисел нечётна, то это значит, что одно из слагаемых чётно, а другое нет. Пусть для определённости p₁ – чётное. Единственное чётное простое число — это 2. Значит, . То есть, K-2 (предыдущее перед K нечётное число) является простым. Поскольку всё вышесказанное верно для любого нечётного большего N, то получается, что все нечётные числа, начиная с N-2, являются простыми. Это неверно. Если бы это было так, то при n→ ∞. Однако, как говорилось выше при n→ ∞.

Итак, не существует такого числа, начиная с которого все нечётные числа могут быть представлены в виде суммы двух простых.

А что же насчёт чётных? Гипотеза не была опровергнута, не было найдено ни одного контрпримера. Но это не значит, что их не существует. Доказать же гипотезу полностью пока никому не удалось.

2. Гипотеза о числах-близнецах

Бесконечно ли число простых чисел близнецов?

Для начала сформулируем определение. Два простых числа называются близнецами если отличаются друг от друга на 2.

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

3. Гипотеза Лежандра

Всегда ли существует, по меньшей мере, одно простое число, лежащее между двумя последовательными полными квадратами?

Аналогичная гипотеза доказана для кубов, начиная с некоторого n. То есть, существует, по меньшей мере, одно простое число, лежащее между и для достаточно большого n. Для квадратов же, гипотеза Лежандра пока не доказана.

4. Почти квадратные простые числа

Заключение

Как мы видим, в этой области теории чисел существует очень много пробелов, а также недоказанных гипотез. Отдельно хочется сказать про численную проверку утверждений. Например, ни для одной из гипотез Ландау не был найден контрпример, даже с использованием значительных вычислительных мощностей в течение большого времени. Однако, в истории математики 20-го и 21-го века были случаи, когда контрпример, опровергающий гипотезу, был настолько огромным числом, что его не удавалось найти с помощью вычислительных машин.

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

Источник