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

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

Такое доказательство (одно из существующих) дал ещё Евклид, и основано оно как раз исследовании произведения всех простых чисел.

Ну ещё раз: пусть простых чисел — конечное количество, и пусть Р — произведение всех простых чисел, от первого до n-го. И рассмотрим число Р+1.

Возможны два варианта.

Либо Р+1 — простое число, но тогда мы сразу приходим к противоречию с исходным предположением о конечности множества простых чисел. Оказывается — ни фига, есть ещё одно.

Либо Р+1 — не простое число, но тогда его можно разложить на простые множители, которые, по предположению, должны быть из нашего конечного набора. Ну пусть среди таких множителей есть и число k. Коль скоро и Р делится на k (Р ведь — произведение всех-всех-всех простых чисел, включая k), и Р+1 делится на k, то на это же k должна делиться и разность двух чисел. Только вот разность эта равна 1, а 1 не может делиться ни на что, если мы собираемся оставаться в рамках целых чисел.

Значит, предположение о конечности набора простых чисел неверное. Вся любовь.

Множество простых чисел бесконечно — а как это доказать?

Простых чисел бесконечно много. Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (книга IX, утверждение 20). Его доказательство может быть кратко воспроизведено так:

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

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

Love Soft

Загрузки всякие

Связь

Содержание

Простые числа. Делители

Из книги Паоло Джордано The Solitude of Prime Numbers («Одиночество простых чисел»):

Простые числа делятся только на единицу и самих себя. Они занимают свое место в бесконечном ряду простых чисел, которые, как и остальные числа, зажаты между двумя другими, но на один шаг дальше, чем предыдущие. Эти числа подозрительны и одиноки, и Маттиа казалось, что они волшебные. Иногда он думал, что они очутились в этом ряду по ошибке, как жемчужины, нанизанные на нитку ожерелья. А порой ловил себя на мысли, что они тоже предпочли бы быть обычными числами, однако по какой-то причине не сложилось. […]

Простые числа — атомы арифметики. Согласно греческому происхождению слова «атом», простые числа являются «атомными», то есть «неделимыми». И подобно тому как все сложено из атомов, каждое число слагается из простых чисел. Например, 60 равно 2 × 2 × 3 × 5. Мы говорим, что 60 — это составное число, и его можно представить в виде произведения простых множителей 2 (дважды), 3 и 5.

А как быть с 1? Это простое число? Нет. И когда мы поймем это, то узнаем, почему 1 — самое одинокое число, даже более одинокое, чем любое простое число.

Простые числа

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

Число называется простым, если оно делится только на 1 и само на себя.

Является ли заданное число простым можно проверить, последовательно деля его на все натуральные числа, меньшие его.

Как определить, является ли данное целое число простым? В теории достаточно перебрать все возможные потенциальные делители и убедиться, что остаток от деления всегда будет отличен от нуля. Но на практике определение простых чисел требует объемных вычислений: представьте, что вам нужно найти делители числа, состоящего, например, из миллиона цифр. Эта задача неподвластна современным компьютерам.

Последовательность простых чисел начинается так:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, …

Следующий вопрос звучит так: существуют ли общие формулы, позволяющие получить все простые числа или хотя бы некоторые из них? Так, выражения n² и 7n позволяют найти все квадраты и все числа, кратные 7, соответственно (для этого достаточно заменить n натуральными числами). Существует ли математическая формула, результатом которой для каждого n будет простое число? Такой формулы не существует, поскольку простые числа поистине загадочны. Можно даже сказать, что они распределены случайным образом.

Я уже говорил, что для простых чисел не существует никакой формулы, никакой комбинации алгебраических операций над n, выполняя которые можно было бы получить очередное, п-ое простое число. Многие люди впадали в заблуждение на этот счет, достигнув некоторых первоначальных успехов. Хорошо иллюстрирует подобные заблуждения шуточная поговорка, известная любому студенту-математику. В ней говорится о трех способах доказательства того, что все нечетные числа простые:

МАТЕМАТИК: 3 — это простое число, 5 — простое, 7 — простое …, а дальше доказательство по индукции.

ФИЗИК: 3 — простое число, 5 — простое, 7 — простое, 9 — ошибка эксперимента, 11 — простое …

ИНЖЕНЕР: 3 — простое число, 5 — простое, 7 — простое, 9 — простое …

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

Но, может быть, существует формула, которая дает, пусть не все, но только простые числа? Пьер Ферма, знаменитый французский математик XVII в., думал, что нашел такую формулу, когда написал $2^ <2^n>+ 1$. Он полагал, что какое значение ни подставь в эту формулу, результатом будет простое число. Однако этот мыльный пузырь, пущенный Ферма, лопнул после его смерти, когда швейцарский математик Леонард Эйлер нашел делители для пятого Ферма: 4 294 967 297 = 641 х 6700417.

Фильм Куб

В фильме Куб группа незнакомцев просыпается посреди футуристической кубической комнаты. Они должны найти выход из нее, пройдя через множество комнат, полностью идентичных первой. Со временем герои фильма обнаруживают, что в некоторых комнатах находятся смертельные ловушки. Студентка-математик Левен разгадывает шифр, указывающий, в каких комнатах нет ловушек: на двери в каждую комнату записаны три трехзначных числа. Если какое-то из этих чисел равно некоторой степени простого числа, то в комнате находится ловушка, которую нужно избежать. Таким образом, чтобы обнаружить ловушку, нужно найти простые делители всех чисел, записанных на двери в комнату. Однако Левен утверждает, что произвести необходимые расчеты очень сложно: «…Никто в целом мире не сможет сделать эти расчеты в уме. Посмотри на числа: 567, 898, 545. Разложить их на множители невозможно — потребуется огромный объем расчетов!» Заметьте, что все исходные числа меньше 1000, а √1000 = 31,62… Таким образом, чтобы определить, является ли трехзначное число простым, достаточно определить, делится ли оно на 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 или 31. Чтобы произвести подобные расчеты в уме, необходимы терпение и сноровка, однако они вполне посильны. Более того, в нашем случае нетрудно показать, что 567 делится на 3, 898 — на 2, 545 — на 5.

Мир математики, выпуск 34 — Искусство подсчета

Составные числа

Натуральные числа, большие единицы и не являющиеся простыми, называются составными.

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

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

$$1200 = 2^4 × 3^1 × 5^2 = 3 × 2 × 2 × 2 × 2 × 5 × 5 = 5 × 2 × 3 × 2 × 5 × 2 × 2 = etc.$$

Представление натурального числа в виде произведения простых называется разложением на простые или факторизацией числа. На предполагаемой большой вычислительной сложности задачи факторизации базируется криптосистема RSA и некоторые другие.

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

Возможно ли распознать простое число, как говорится, с первого взгляда? Если вы зачерпнули в сито сразу много чисел, сверкнет ли среди них простое, как золотой самородок? Некоторые считают, что да. Например, числа, оканчивающиеся на 1, часто оказываются искомыми, скажем, такие как 11, 31, 41. Однако при этом следует быть осторожным и не принять фальшивое золото за чистое, как, скажем, 21 или 81. По мере роста величины чисел, единица на конце все чаще вводит нас в заблуждение. Создается даже впечатление будто простые числа в конце концов просто исчезают, как полагали некоторые древние греки. Существует ли последнее, самое большое по величине простое число?

Простых чисел бесконечно много. Самое старое известное доказательство этого факта было дано Евклидом:

НОВИЧОК: Эй, мистер! Как далеко вниз по течению заходят простые числа?

СТАРОЖИЛ: До самого моря Бесконечности, парень.

НОВИЧОК: Я вам не верю. Мы здесь на уровне миллионов, а мне еще ни разу не повезло за целый день.

СТАРОЖИЛ: Эх, молодежь, вам нужно все объяснять! Смотри, допустим, ты дошел до последнего простого числа. После него их уже не существует, так?

СТАРОЖИЛ: Назовем его n. Составим произведение из всех простых чисел вплоть до n. Это будет 2х3х5х7х…n. Теперь прибавим к произведению 1 и назовем это число p.

НОВИЧОК: И что же, вы хотите сказать, что p — простое число?

СТАРОЖИЛ: Конечно. Простое — проще некуда. Смотри, ты не можешь разделить его на 2, потому что остается 1. Ты не можешь разделить его на 3, потому что остается 1. Каждый раз всегда остается 1, вплоть до n. Ее никак не обойдешь.

НОВИЧОК: Вот оно что! Значит, вы правы, им конца нет.

СТАРОЖИЛ: Так-то вот. Ну ладно, чего стоишь без дела, помоги-ка мне с этим промывным желобом.

Проблемы

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

Письмо Гольдбаха Эйлеру, датированное 7 июня 1742 (Латынь-Немецкий).

С простыми числами связан ряд проблем, на протяжении десятилетий и даже веков не поддающихся решению. Одна из таких проблем — гипотеза Гольдбаха-Эйлера, сформулированная в XVIII веке: любое четное число, большее двух, можно представить в виде суммы двух простых чисел. Эта гипотеза до сих пор не доказана и не опровергнута.

Пример. 100 = 3 + 97 = 11 + 89 = 17 + 83 = 29 + 71 = 41 + 59 = 47 + 53

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

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

Гипотеза Гольдбаха — одна из самых известных открытых математических проблем; в совокупности с гипотезой Римана включена под номером 8 в список проблем Гильберта (1900) и является одной из немногих проблем Гильберта, до сих пор остающихся нерешёнными по состоянию на 2010-е годы.

На апрель 2012 года бинарная гипотеза Гольдбаха была проверена для всех чётных чисел, не превышающих $4×10^<18>$.

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

Число способов записать четное число n как сумму двух простых (4 ≤ n ≤ 1,000,000)

Отыскание простых чисел

Решето Эратосфена

Решето Эратосфена — простой алгоритм нахождения всех простых чисел до некоторого целого числа n, путём вычёркивания всех чисел которые делятся на простой делитель: 2, 3, 5, 7 и т.д. Пускай нам нужно отыскать простые числа в промежутке от единицы до некоторого N ≤ 10^6. Мы заводим массив на N элементов и заполняем его true. Затем последовательно проходим по нему до корня из N, и встречая true, вычеркиваем все числа с этим шагом до N.

Решето только по нечётным числам: поскольку все чётные числа, кроме 2, — составные, то можно вообще не обрабатывать никак чётные числа, а оперировать только нечётными числами. Во-первых, это позволит вдвое сократить объём требуемой памяти. Во-вторых, это уменьшит количество выполняемых алгоритмом операций (примерно вдвое). Это можно обобщить на числа взаимно простые с 3, 5 и т. д.

Решето Аткина

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

Интервалы между простыми числами

Интервалы между простыми числами — это разности между двумя последовательными простыми числами.

Первые 30 интервалов между простыми числами следующие:

1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14

Последовательность $g_n$ интервалов между простыми хорошо изучена.

Существуют сколь угодно большие интервалы между простыми числами. Наибольший известный интервал между простыми числами — это интервал длины 337446.

Уже во второй тысяче имеется интервал, длиной 34 числа, в котором нет простых чисел — (1327-1361). Причём, этот интервал удерживает свой рекорд длины до десятой тысячи. Крупные интервалы в пределах первого миллиона: 114 чисел: 492113-492227, 112 чисел: 370261-370373.

В начале позапрошлого века была высказана (подкреплённая наблюдением за простыми числами) гипотеза, согласно которой число простых чисел, меньших данного числа n, приближённо выражается соотношением n/ln(n) (ln — натуральный логарифм) и что данное приближение тем лучше, чем больше число n. Эта удивительная теорема, известная под названием «теорема об асимптотическом распределении простых чисел», была строго доказана в 1896 году.

Насколько быстро простые числа разрежаются по течению реки Континуума? Из первых 10 чисел 4 являются простыми, таким образом их доля составляет 40%. В первой сотне их содержание падает до 25%, и оно продолжает падать с ростом величины чисел более или менее регулярно. В общем количество простых чисел до n включительно приблизительно равно n/ln(n). В данном случае это приближение является асимптотическим. Другими словами, если количество простых чисел, меньших либо равных n, обозначить р(n), то отношение р(n) к величине n/logn все ближе приближается к 1, по мере того как n становится все больше и больше. Таким образом, вниз по течению Континуума простые числа разрежаются пропорционально натуральному логарифму от n.

Репьюниты

Репьюниты — Простые, состоящие из единиц

Генри Э. Дьюдени ещё в 1907 году отметил, что 11 — не единственное из известных простых чисел, которое состоит из одних лишь единиц. (Число, состоящее из повторения любой другой цифры, очевидно, составное). Дьюдени сумел доказать, что все числа, состоящие из 3,4,…,18 единиц составные. Дьюдени заинтересовал вопрос, существуют ли более чем 18-значные простые числа, запись которых состоит из одних лишь единиц. Ответ на этот вопрос нашёл один из читателей Дьюдени: он доказал, что 19-значное число 1 111 111 111 111 111 — простое. Позднее было доказано, что число, записанное с помощью 23 единиц, тоже простое. Ответы на многие вопросы, связанные с «единичными» числами, неизвестны до сих пор. Никто не знает, существует ли среди них бесконечно много простых чисел и даже существует ли вообще четвёртое простое число, записанное с помощью одних единиц. Ближайший кандидат в простые числа состоит из 47 единиц (числа из 29,31,37,41,43,53,61 и 73 единиц составные).

Википедия: Числа, состоящие из 2, 19, 23, 317, 1031, 49081, 86453, 109297, 270343 единиц, являются простыми

Простые палиндромы

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

Ясно, что любой простой палиндром состоит из нечётного количества цифр (за исключением числа 11), так как любой палиндром с чётным количеством цифр всегда делится на 11. Первыми простыми палиндромами являются такие числа:

2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601, 11311,…

Простые числа-близнецы

Математики давно обратили внимание, что распределение простых чисел в бесконечном числовом пространстве имеет определённые закономерности. В частности, странным феноменом выступают простые числа-близнецы, которые отличаются друг от друга на 2. Чем больше количество знаков, тем реже встречаются числа-близнецы, но всё равно они продолжают встречаться снова и снова.

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

Гипотеза. Существует бесконечно много таких простых p, что и p + 2 — тоже простое

Итан Чжан доказал 1) , что существует бесконечно много пар простых чисел, расстояние между которыми не превышает 70 миллионов. Эти пары будут встречаться всё реже и реже, но не исчезнут никогда, несмотря на действие теоремы о среднем расстоянии между простыми числами в 2,3 × N, где N — количество разрядов.

Другими словами, среднее расстояние между числами будет приближаться к бесконечности, по мере роста количества разрядов, но при этом всегда будут встречаться простые числа, удалённые друг от друга не более чем на 70 млн, что просто удивительно.

И можно довольно несложно указать диапазон в 70 млн, в котором нет ни одного простого числа: (70млн+1)! + 2, (70млн+1)! + 3, (70млн+1)! + 4,…, (70млн+1)! + (70млн+1).

Первые простые числа-близнецы:

Постулат Бертрана

Один из интереснейших фактов о простых числах: между натуральными n и 2n всегда найдётся простое число.

Если n — натуральное, то существует простое p, такое, что n < p < 2n.

Скатерть Улама

из журнала Квант 5-1975

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

Рассмотрим многочлен $x^2 + x + 41$ — его изучал ещё Леонард Эйлер. Этот многочлен принимает простые значения при x = 1, 2, …, 40. При x = 41 его значение — составное. Давно известно, что из 2398 первых значений, принимаемых этим трёхчленом, ровно половина простые. Перебрав все значения знаменитого трёхчлена, не превышающие 10 000 000, Улам, Стейн и Уэллс обнаружили, что доля простых чисел среди них составляет 0,475…

Интерес к представлению простых чисел в виде значений квадратных многочленов недавно возродился в связи с неожиданным наблюдением С. М. Улама. Начав на спирали из всех натуральных чисел отмечать простые числа, Улам с удивлением обнаружил, что простые числа выстраиваются по диагоналям, образуя довольно длинные цепочки. (Докажите, что числа, расположенные вдоль какой-либо диагонали в пределах, ограниченных на рис. 1 красными линиями — это значения некоторого квадратного многочлена с целыми коэффициентами).

Ещё более удивительным оказалось то, что закономерность эта наблюдалась и тогда, когда спираль была продолжена (с помощью компьютера) до больших чисел — на рис. светлыми точками отмечены простые числа на спирали из первых 10 000 чисел. Узор получил название «скатерть Улама».

Как было сделано это наблюдение, красочно рассказывает М. Гарднер в «Математических досугах» (1972).

В зависимости от расположения целых чисел простые числа могут образовывать тот или иной узор. Однажды математику Станиславу М. Уламу пришлось присутствовать на одном очень длинном и очень скучном, по его словам, докладе. Чтобы как-то развлечься, он начертил на листке бумаги вертикальные и горизонтальные линии и хотел было заняться составлением шахматных этюдов, но потом передумал и начал нумеровать пересечения, поставив в центре 1 и двигаясь по спирали против часовой стрелки. Без всякой задней мысли он обводил все простые числа кружками. Вскоре, к его удивлению, кружки с поразительным упорством стали выстраиваться вдоль прямых. … Для удобства числа вписаны в клетки, а не стоят на пересечении линий.

Вблизи центра выстраивания простых чисел вдоль прямых ещё можно было ожидать, поскольку плотность простых чисел вначале велика и все они, кроме числа 2, нечётны. Если клетки шахматной доски перенумеровать по спирали, то все нечётные числа попадут на клетки одного и того же цвета. Взяв 17 пешек (соответствующих 17 простым числам, не превосходящим числа 64) и расставив их наугад на клетки одного цвета, вы обнаружите, что пешки выстроились вдоль диагональных прямых. Однако не было оснований ожидать, что и в области больших чисел, где плотность простых чисел значительно меньше, те также будут выстраиваться вдоль прямых. Улама заинтересовало, как же будет выглядеть его спираль, если её продолжить до нескольких тысяч простых чисел. …

Улам вместе с Майроном Л. Стейном и Марком Б. Уэллсом составили программу для вычислительной машины MANIAC, позволившую нанести на спираль последовательные целые числа от 1 до 65 000. Обратите внимание на то, что даже у края картины простые числа продолжают послушно укладываться на прямые.

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

Спираль Улама подняла много новых вопросов, относящихся к закономерностям и случайностям в распределении простых чисел. Существуют ли прямые, на которых лежит бесконечно много простых чисел? Какова максимальная плотность распределения простых чисел вдоль прямых? Существенно ли различаются плотности распределения простых чисел в квадрантах «скатерти» Улама, если считать, что она продолжается неограниченно? Спираль Улама — забава, но её следует принимать всерьёз.

Феномен со стремлением простых чисел располагаться в цепочки вдоль диагоналей был обнаружен сравнительно недавно и ещё не получил какого-либо математического объяснения.

Выделяющиеся на графике темные линии — это залежи простых чисел. Каким образом можно выразить эту геологическую картину на языке математики? У самого центра диаграммы одно такое месторождение пролегает сверху вниз и справа налево. Оно состоит из последовательности чисел: 7, 23, 47, 79… . Оказывается, эту последовательность можно описать квадратичной функцией $4x^2 + 4х — 1$.

Те, у кого остались в памяти кое-какие сведения из школьной алгебры, смогут подобрать формулы практически для любой линии на диаграмме. Формула может оказаться справедливой и для множества простых чисел, лежащих далеко за пределами приведенной диаграммы. Эйлер, который так многим не дал сделать карьеру в математике, предвосхитив множество математических результатов, тоже аналогичную формулу еще в XVIII в.: $х^2 + х + 41$. Эта формула не видна на диаграмме Улама, чтобы ее увидеть, нужно в качестве начального числа спирали выбрать другое значение. Если начать спираль с 41, то мы получим месторождение, содержащее сразу 40 последовательных простых чисел!

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

Тесты простоты

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

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

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

Перебор делителей

Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа n и в вычислении остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число i равен 0, то i является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу (если тестируется простота n), либо n сокращается на i и процедура повторяется (если осуществляется факторизация n). По достижении квадратного корня из n и невозможности сократить n ни на одно из меньших чисел n объявляется простым.

Для ускорения перебора часто не проверяются чётные делители, кроме числа 2, а также делители, кратные трём, кроме числа 3. При этом тест ускоряется в три раза, так как из каждых шести последовательных потенциальных делителей необходимо проверить только два, а именно вида 6·k±1, где k — натуральное число.

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

Довольно неожиданно, что существует ряд способов проверить простоту числа, не находя его делителей.

Тест Миллера

Тест Миллера — Рабина разработан в 1976 г. Алгоритм Миллера гарантированно распознает простые и составные числа при условии выполнения недоказанной расширенной гипотезы Римана. Алгоритм Миллера — Рабина не зависит от справедливости гипотезы, но является вероятностным.

Как и тесты Ферма и Соловея — Штрассена, тест Миллера — Рабина опирается на проверку ряда равенств, которые выполняются для простых чисел. Если хотя бы одно такое равенство не выполняется, это доказывает что число составное.

Идея теста заключается в том, чтобы проверять для случайно выбранных чисел, являются ли они свидетелями простоты числа. Если на определённом шаге алгоритма было проверено k чисел, и все они оказались свидетелями простоты, то вероятность того, что число составное не более (1/4)^k.

Быть может, Бог не играет в кости со Вселенной, но с простыми числами определенно что-то не так.

Некоторые простые числа

Задача. Найти простые числа, которые остаются простыми после вычеркивания одной цифры?