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

Теорема.

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

Доказательство.

Предположим, что это не так. То есть, предположим, что простых чисел всего n штук, и эти простые числа есть p 1 , p 2 , …, p n . Покажем, что мы всегда можем найти простое число, отличное от указанных.

Рассмотрим число, p равное p 1 ·p 2 ·…·p n +1 . Понятно, что это число отлично от каждого из простых чисел p 1 , p 2 , …, p n . Если число p - простое, то теорема доказана. Если же это число составное, то в силу предыдущей теоремы существует простой делитель этого числа (обозначим его p n+1 ). Покажем, что этот делитель не совпадает ни с одним из чисел p 1 , p 2 , …, p n .

Если бы это было не так, то по свойствам делимости произведение p 1 ·p 2 ·…·p n делилось бы на p n+1 . Но на p n+1 делится и число p , равное сумме p 1 ·p 2 ·…·p n +1 . Отсюда следует, что на p n+1 должно делиться второе слагаемое этой суммы, которое равно единице, а это невозможно.

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

Итак, в силу того, что простых чисел бесконечно много, при составлении таблиц простых чисел всегда ограничивают себя сверху каким-либо числом, обычно, 100 , 1 000 , 10 000 и т.д.

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

Сейчас мы обсудим способы составления таблиц простых чисел. Предположим, что нам нужно составить таблицу простых чисел до 100 .

Самым очевидным методом решения этой задачи является последовательная проверка целых положительных чисел, начиная с 2 , и заканчивая 100 , на наличие положительного делителя, который больше 1 и меньше проверяемого числа (из свойств делимости мы знаем, что абсолютная величина делителя не превосходит абсолютной величины делимого, отличного от нуля). Если такой делитель не найден, то проверяемое число является простым, и оно заносится в таблицу простых чисел. Если же такой делитель найден, то проверяемое число является составным, оно НЕ заносится в таблицу простых чисел. После этого происходит переход к следующему числу, которое аналогично проверяется на наличие делителя.

Опишем несколько первых шагов.

Начинаем с числа 2 . Число 2 не имеет положительных делителей, кроме 1 и 2 . Следовательно, оно простое, поэтому, заносим его в таблицу простых чисел. Здесь следует сказать, что 2 является наименьшим простым числом. Переходим к числу 3 . Его возможным положительным делителем, отличным от 1 и 3 , является число 2 . Но 3 на 2 не делится, поэтому, 3 – простое число, и его также нужно занести в таблицу простых чисел. Переходим к числу 4 . Его положительными делителями, отличными от 1 и 4 , могут быть числа 2 и 3 , проверим их. Число 4 делится на 2 , поэтому, 4 – составное число, и его не нужно заносить в таблицу простых чисел. Обратим внимание на то, что 4 – наименьшее составное число. Переходим к числу 5 . Проверяем, являются ли его делителем хотя бы одно из чисел 2 , 3 , 4 . Так как 5 не делится ни на 2 , ни на 3 , ни на 4 , то оно простое, и его надо записать в таблицу простых чисел. Дальше происходит переход к числам 6 , 7 , и так далее до 100 .

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

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

Покажем решето Эратосфена в действии при составлении таблицы простых чисел до 50 .

Сначала записываем по порядку числа 2, 3, 4, …, 50 .

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

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

Первым следующим за 3 невычеркнутым числом является 5 . Это число простое. Теперь от числа 5 последовательно перемещаемся вправо на 5 чисел (учитываем и зачеркнутые ранее числа) и вычеркиваем их. Так будут вычеркнуты все числа, кратные пяти.

Дальше вычеркиваем числа, кратные 7 , затем, кратные 11 и так далее. Процесс заканчивается, когда не останется чисел для вычеркивания. Ниже показана законченная таблица простых чисел до 50 , полученная с помощью решета Эратосфена. Все незачеркнутые числа являются простыми, а все зачеркнутые числа – составными.

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

Теорема.

Наименьший положительный и отличный от единицы делитель составного числа a не превосходит , где - из a .

Доказательство.

Обозначим буквой b наименьший и отличный от единицы делитель составного числа a (число b является простым, что следует из теоремы, доказанной в самом начале предыдущего пункта). Тогда существует такое целое число q , что a=b·q (здесь q – положительное целое число, что следует из правил умножения целых чисел), причем (при b>q нарушится условие, что b – наименьший делитель числа a , так как q также является делителем числа a в силу равенства a=q·b ). Умножив обе части неравенства на положительное и большее единицы целое число b (это нам позволяют сделать ), получаем , откуда и .

Что же нам дает доказанная теорема, касательно решета Эратосфена?

Во-первых, вычеркивание составных чисел, кратных простому числу b следует начинать с числа, равного (это следует из неравенства ). Например, вычеркивание чисел, кратных двум, следует начинать с числа 4 , кратных трем – с числа 9 , кратных пяти – с числа 25 , и так далее.

Во-вторых, составление таблицы простых чисел до числа n с помощью решета Эратосфена можно считать законченным тогда, когда будут вычеркнуты все составные числа, кратные простым числам, не превосходящим . В нашем примере n=50 (так как мы составляем таблицу простых чисел до 50 ) и , поэтому решето Эратосфена должно отсеять все составные числа, кратные простым числам 2 , 3 , 5 и 7 , которые не превосходят арифметического квадратного корня из 50 . То есть, нам дальше не нужно заниматься поиском и вычеркиванием чисел, кратных простым числам 11 , 13 , 17 , 19 , 23 и так далее до 47 , так как они уже будут вычеркнуты, как кратные меньшим простым числам 2 , 3 , 5 и 7 .

Данное число простое или составное?

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

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

Пример.

Докажите, что число 898 989 898 989 898 989 составное.

Решение.

Сумма цифр данного числа равна 9·8+9·9=9·17 . Так как число, равное 9·17 делится на 9 , то по признаку делимости на 9 можно утверждать, что исходное число также делится на 9 . Следовательно, оно составное.

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

Самый логичный подход состоит в переборе всех возможных делителей данного числа. Если ни один из возможных делителей не будет истинным делителем данного числа, то это число будет простым, в противном случае – составным. Из теорем, доказанных в предыдущем пункте, следует, что делители данного числа a нужно искать среди простых чисел, не превосходящих . Таким образом, данное число a можно последовательно делить на простые числа (которые удобно брать из таблицы простых чисел), пытаясь найти делитель числа a . Если будет найден делитель, то число a – составное. Если же среди простых чисел, не превосходящих , не окажется делителя числа a , то число a – простое.

Пример.

Число 11 723 простое или составное?

Решение.

Выясним, до какого простого числа могут быть делители числа 11 723 . Для этого оценим .

Достаточно очевидно, что , так как 200 2 =40 000 , а 11 723<40 000 (при необходимости смотрите статью сравнение чисел ). Таким образом, возможные простые делители числа 11 723 меньше числа 200 . Это уже значительно облегчает нашу задачу. Если бы мы этого не знали, то нам бы пришлось перебирать все простые числа не до 200 , а вплоть до числа 11 723 .

При желании можно оценить более точно. Так как 108 2 =11 664 , а 109 2 =11 881 , то 108 2 <11 723<109 2 , следовательно, . Таким образом, любое из простых чисел, меньших 109 , потенциально является простым делителем данного числа 11 723 .

Теперь мы будем последовательно делить число 11 723 на простые числа 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 . Если число 11 723 разделится нацело на одно из записанных простых чисел, то оно будет составным. Если же оно не делится ни на одно из записанных простых чисел, то исходное число простое.

Не будем описывать весь этот монотонный и однообразный процесс деления. Сразу скажем, что 11 723

Числа бывают разными: натуральными, естественными, рациональными, целыми и дробными, положительными и отрицательными, комплексными и простыми, нечетными и четными, действительными и др. Из данной статьи можно узнать, что такое простые числа.

Какие числа называют английским словом “симпл”?

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

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

Противоположностью простых чисел являются составные. Они также являются натуральным, также больше единицы, но имеют не два, а большее количество делителей. Так, например, числа 4, 6, 8, 9 и т. д. являются натуральными, составными, но не простыми числами. Как видите - это в основном четные числа, но не все. А вот “двойка” - четное число и “первый номер” в ряду простых чисел.

Последовательность

Чтобы построить ряд простых чисел, необходимо совершить отбор из всех натуральных чисел с учетом их определения, то есть нужно действовать методом от противного. Необходимо рассмотреть каждое из натуральных положительных чисел на предмет того, имеет ли оно более двух делителей. Давайте постараемся построить ряд (последовательность), который составляют простые числа. Список начинается с двух, следующим идет три, поскольку оно делится только на себя и на единицу. Рассмотрим число четыре. Имеет ли оно делители, кроме четырех и единицы? Да, это число 2. Значит, четыре не является простым числом. Пять также является простым (оно, кроме 1 и 5, ни на какое другое число не делится), а вот шесть - делится. И вообще, если проследить за всеми четными числами, то можно заметить, что кроме “двух”, ни одно из них не является простым. Отсюда сделаем вывод, что четные числа, кроме двух, не являются простыми. Еще одно открытие: все числа, делящиеся на три, кроме самой тройки, будь то четные или нечетные, также не являются простыми (6, 9, 12, 15, 18, 21, 24, 27 и т.д.). То же самое касается и чисел, которые делятся на пять и на семь. Все их множество также не является простым. Давайте подведем итоги. Итак, к простым однозначным числам относятся все нечетные числа, кроме единицы и девятки, а из четных - только “два”. Сами десятки (10, 20,... 40 и др.) не являются простыми. Двузначные, трехзначные и т. д. простые числа можно определить, исходя из вышеизложенных принципов: если они не имеют других делителей, кроме их самих и единицы.

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

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

Простые числа — “строительные блоки” натуральных чисел

В арифметике есть теорема, которая называется основной. Согласно ей, любое натуральное число, кроме единицы, можно представить в виде произведения, множителями которого являются простые числа, причем порядок следования множителей единственен, этот означает, что и способ представления единственен. Он называется разложением натурального числа на простые множители. Есть и другое название этого процесса - факторизация чисел. Исходя из этого, простые числа можно назвать “строительным материалом”, "блоками" для построения натуральных чисел.

Поиск простых чисел. Тесты простоты

Множество ученых разных времен пытались найти какие-то принципы (системы) для нахождения списка простых чисел. Науке известны системы, которые называются решето Аткина, решето Сундартама, решето Эратосфена. Однако они не дают каких-то существенных результатов, и для нахождения простых чисел используется простая проверка. Также математиками были созданы алгоритмы. Их принято называть тестами простоты. Например, существует тест, разработанный Рабином и Миллером. Его используют криптографы. Также существует тест Каяла-Агравала- Саскены. Однако он, несмотря на достаточную точность, очень сложен в вычислении, что принижает его прикладное значение.

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

О том, что множество простых является бесконечностью, писал в книге “Начала” древнегреческий ученый Евклид. Он говорил так: “Давайте на минуту представим, что простые числа имеют предел. Тогда давайте перемножим их друг с другом, а к произведению прибавим единицу. Число, полученное в результате этих простых действий, не может делиться ни на одно из ряда простых чисел, потому что в остатке всегда будет единица. А это значит, что существует какое-то другое число, которое еще не включено в список простых чисел. Следовательно, наше допущение не верно, и это множество не может иметь предела. Помимо доказательства Евклида, существует более современная формула, данная швейцарским математиком восемнадцатого века Леонардом Эйлером. Согласно ему, сумма, обратная сумме первых n чисел растет неограниченно с ростом числа n. А вот формула теоремы относительно распределения простых чисел: (n) растёт, как n/ln (n).

Какое наибольшее простое число?

Все тот же Леонард Эйлер смог найти самое большое для своего времени простое число. Это 2 31 - 1 = 2147483647. Однако к 2013 году было вычислено другое наиболее точное самое большое в списке простых чисел - 2 57885161 - 1. Его называют числом Мерсенна. Оно содержит около 17 миллионов десятичных цифр. Как видите, число, найденное ученым из восемнадцатого века, в несколько раз меньше этого. Так и должно было быть, ведь Эйлер вел данный подсчет вручную, нашему же современнику наверняка помогала вычислительная машина. Более того, это число было получено на факультете математики в одном из американских факультетов. Числа, названные в честь этого ученого, проходят через тест простоты Люка-Лемера. Однако наука не желает останавливаться на достигнутом. Фонд Электронных рубежей, который был основан в 1990 году в Соединенных Штатах Америки (EFF), назначил за нахождение больших простых чисел денежную награду. И если до 2013 года приз полагался тем ученным, которые найдут их из числа 1 и 10 миллионов десятичных чисел, то сегодня это цифра достигла от 100 миллионов до 1 миллиарда. Размер призов составляет от 150 до 250 тысяч долларов США.

Названия специальных простых чисел

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

1. Мерссена.

4. Каллена.

6. Миллса и др.

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

1. Люка-Лемера.

2. Пепина.

3. Ризеля.

4. Биллхарта - Лемера - Селфриджа и др.

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

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

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

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

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

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

Простые числа не появляются в натуральном ряду беспорядочно, как это может показаться на первый взгляд. Внимательно проанализировав их, можно сразу заметить несколько особенностей, наиболее любопытные из которых связаны с так называемыми числами-«близнецами». Называют их так потому, что каким-то непостижимым образом они оказались по соседству друг с другом, разделенные только четным разграничителем (пять и семь, семнадцать и девятнадцать).

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

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

Простым числом является натуральное число, которое делится только на себя и на единицу.

Остальные числа называют составными.

Простые натуральные числа

Но не все натуральные числа являются простыми числами.

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

Примеры простых чисел:

2; 3; 5; 7; 11; 13;...

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

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

Это значит, что простые числа обязательно являются натуральными.

Но все натуральные числа являются одновременно целыми числами.

Таким образом, все простые числа являются целыми.

Примеры простых чисел:

2; 3; 5; 7; 11; 13; 17; 19; 23;...

Четные простые числа

Имеется только одно четное простое число - это число два.

Все остальные простые числа нечетные.

А почему не может быть простым числом четное число больше двух?

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