Наибольшее простое однозначное число. Теории о свойствах простых чисел

Определение 1. Простое число − это натуральное число больше единицы, которое делится только на себя и на 1.

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

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

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

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

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

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

Утверждение 1. Если p - простое число и a любое целое число, то либо a делится на p , либо p и a взаимно простые числа.

Действительно. Если p простое число, то оно делится только на себя и на 1, если a не делится на p , то наибольший общий делитель a и p равен 1. Тогда p и a взаимно простые числа.

Утверждение 2. Если произведение нескольких чисел чисел a 1 , a 2 , a 3 , ... делится на простое число p , то по крайней мере одно из чисел a 1 , a 2 , a 3 , ... делится на p .

Действительно. Если бы ни одно из чисел не делилось на p , то числа a 1 , a 2 , a 3 , ... были бы взаимно простые числа по отношению p . Но из следствия 3 () следует, что их произведение a 1 , a 2 , a 3 , ... также взаимно простое по отношению к p , что противоречит условию утверждения. Следовательно по крайней мере один из чисел делится на p .

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

Доказательство. Пусть k составное число, и пусть a 1 один из его делителей отличное от 1 и самого себя. Если a 1 составное, то имеет кроме 1 и a 1 и другой делитель a 2 . Если a 2 число составное, то имеет кроме 1 и a 2 и другой делитель a 3 . Рассуждая таким образом и учитывая, что числа a 1 , a 2 , a 3 , ... убывают и этот ряд содержит конечное число членов, мы дойдем какого-то простого числа p 1 . Тогда k можно представить в виде

Допустим существует два разложения числа k :

Так как k=p 1 p 2 p 3 ... делится на простое число q 1 , то по крайней мере один из множителей, например p 1 делится на q 1 . Но p 1 простое число и делится только на 1 и на себя. Следовательно p 1 =q 1 (т.к. q 1 ≠1)

Тогда из (2) можно исключить p 1 и q 1:

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

Разложение составного числа k можно записать в следующем виде

где p 1 , p 2 , ... различные простые числа, α, β, γ ... целые положительные числа.

Разложение (3) называется каноническим разложением числа.

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

Теорема 2. Количество простых чисел бесконечно много.

Доказательство. Предположим, что существует конечное число простых чисел, и пусть наибольшее простое число равно p . Рассмотрим все числа больше p . По предположению утверждения эти числа должны быть составными и должны делится по крайней мере на один из простых чисел. Выберем число, являющиеся произведением всех этих простых чисел плюс 1:

Число z больше p так как 2p уже больше p . p не делится ни на одно из этих простых чисел, т.к. при делении на каждое из них дает остаток 1. Таким образом мы приходим к противоречию. Следовательно существует бесчисленное множество простых чисел.

Данная теорема является частным случаем более общей теоремы:

Теорема 3. Пусть задана арифметическая прогрессия

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

Справедливо и обратное. Если каждый простой множитель числа n входит по крайней мере столько же раз в число m , то m делится на n .

Утверждение 3. Пусть a 1 ,a 2 ,a 3 ,... различные простые числа входящие в m так, что

где i =0,1,...α , j =0,1,...,β , k=0,1,...,γ . Заметим, что α i принимает α +1 значений, β j принимает β +1 значений, γ k принимает γ +1 значений, ... .

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

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

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

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

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

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

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

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

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

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

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

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

• Функция floor(x) округляет число x до ближайшего целого числа, которое меньше или равно x.

Узнайте о модульной арифметике. Операция "x mod y" (mod является сокращением латинского слова "modulo", то есть “модуль”) означает "поделить x на y и найти остаток". Иными словами, в модульной арифметике по достижении определенной величины, которую называют модулем , числа вновь "превращаются" в ноль. Например, часы отсчитывают время с модулем 12: они показывают 10, 11 и 12 часов, а затем возвращаются к 1.

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