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, ... и т.д.

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

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

Одним из самых древних и эффективных способов вычисления простых чисел является «решето Эрастофена».

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

Кстати сказать, что для некоторых классов чисел существуют специализированные эффективные тесты простоты. К примеру, для проверки чисел Мерсенна на простоту применяют тест Люка-Лемера, а для проверки на простоту чисел Ферма - тест Пепина.

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

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

Теорема распределения простых чисел утверждает, что количество простых чисел меньших n, обозначаемое π(n), растёт как n / ln(n).

За тысячи лет исследования простых чисел, было выявлено, что наибольшим известным простым числом является 243112609 − 1. Это число включает 12 978 189 десятичных цифр и является простым числом Мерсенна (M43112609). Это открытие было сделано 23 августа 2008 года на математическом факультете университета uCLA в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS.

Главной отличительной особенностью чисел Мерсенна является наличие высоко эффективного теста простоты Люка - Лемера. С его помощью простые числа Мерсенна на протяжении длительного периода времени являются самыми большими из известных простых чисел.

Однако по сей день многие вопросы относительно простых чисел не получили точных ответов. На 5-м Международном математическом конгрессе Эдмунд Ландау сформулировал основным проблемы в области простых чисел:

Проблема Гольдбаха или первая проблема Ландау заключается в том, что необходимо доказать или опровергнуть, что каждое чётное число, большее двух, может быть представлено в виде суммы двух простых чисел, а каждое нечётное число, большее 5, может быть представлено в виде суммы трёх простых чисел.
Вторая проблема Ландау требует найти ответ на вопрос: бесконечно ли множество «простых близнецов» - простых чисел, разность между которыми равна 2?
Гипотеза Лежандра или третья проблема Ландау такова: верно ли, что между n2 и (n + 1)2 всегда найдётся простое число?
Четвёртая проблема Ландау: бесконечно ли множество простых чисел вида n2 + 1?
Помимо вышеперечисленных проблем существует проблема определения бесконечного количества простых чисел во многих целочисленных последовательностях типа числа Фибоначчи, числа Ферма и т. д.

Еще со времен древних греков простые числа были очень привлекательны для математиков. Они постоянно ищут разные способы их нахождения, но самым эффективным способом «поимки» простых чисел, считается способ, найденный александрийским астрономом и математиком Эратосфеном. Этому способу уже около 2000 лет.

Какие числа являются простыми

Как же определить простое число? Многие числа делятся без остатка на другие числа. Число, на которое делится целое число, мы называем делителем.

В данном случае мы говорим о делении без остатка. Например, число 36 можно разделить на 1, 2, 3, 4, 6, 9, 12, 18 и на само себя, то есть на 36. Значит, 36 имеет 9 делителей. Число 23 делится только на себя и на 1, то есть это число имеет 2 делителя – это число является простым.

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

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

В этой таблице все простые числа меньше 48 отмечены оранжевым цветом . Найдены они так:

1 – имеет единственный делитель и поэтому не является простым числом;
2 – наименьшее простое число и единственное четное, так как все остальные четные числа делятся на 2, то есть имеют не меньше 3 делителей, эти числа сведены в фиолетовую колонку ;
3 – простое число, имеет два делителя, все остальные числа, которые делятся на 3, исключаются – эти числа сведены в желтую колонку . Колонка, отмеченная и фиолетовым , и желтым , содержит числа делящиеся и на 2 и на 3;
5 – простое число, все числа, которые делятся на 5, исключаются – эти числа обведены зеленым овалом ;
7 – простое число, все числа, которые делятся на 7, обведены красным овалом – они не являются простыми;

Все числа не являющиеся простыми отмечены синим цветом . Далее эту таблицу можно составить самому по образу и подобию.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Yandex.RTB R-A-339285-1

Простые и составные числа – определения и примеры

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

Определение 1

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

Определение 2

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

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

Определение 3

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

Определение 4

Составное число – это натуральное число, имеющее более двух положительных делителей.

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

Определение 5

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

Простые числа: 2 , 3 , 11 , 17 , 131 , 523 . Они делятся только сами на себя и на 1 . Составные числа: 6 , 63 , 121 , 6697 . То есть число 6 можно разложить на 2 и 3 , а 63 на 1 , 3 , 7 , 9 , 21 , 63 , а 121 на 11 , 11 , то есть его делители будут 1 , 11 , 121 . Число 6697 разложится на 37 и 181 . Заметим, что понятия простых чисел и взаимно простых чисел – разные понятия.

Для того, чтобы было проще использовать простые числа, необходимо использовать таблицу:

Таблица для всех существующих натуральных чисел нереальна, так как их существует бесконечное множество. Когда числа достигают размеров 10000 или 1000000000 , тогда следует задуматься об использовании решета Эратосфена.

Рассмотрим теорему, которая объясняет последнее утверждение.

Теорема 1

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

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

Возьмем, что а является натуральным числом, которое больше 1 , b является наименьшим отличным от единицы делителем для числа а. Следует доказать, что b является простым числом при помощи метода противного.

Допустим, что b – составное число. Отсюда имеем, что есть делитель для b , который отличен от 1 как и от b . Такой делитель обозначается как b 1 . Необходимо, чтобы условие 1 < b 1 < b было выполнено.

Из условия видно, что а делится на b , b делится на b 1 , значит, понятие делимости выражается таким образом: a = b · q и b = b 1 · q 1 , откуда a = b 1 · (q 1 · q) , где q и q 1 являются целыми числами. По правилу умножения целых чисел имеем, что произведение целых чисел – целое число с равенством вида a = b 1 · (q 1 · q) . Видно, что b 1 – это делитель для числа а. Неравенство 1 < b 1 < b не соответствует, потому как получим, что b является наименьшим положительным и отличным от 1 делителем а.

Теорема 2

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

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

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

Примем на рассмотрение число р, которое равняется p 1 , p 2 , … , p n + 1 . Оно не равняется каждому из чисел, соответствующих простым числам вида p 1 , p 2 , … , p n . Число р является простым. Тогда считается, что теорема доказана. Если оно составное, тогда нужно принять обозначение p n + 1 и показать несовпадение делителя ни с одним из p 1 , p 2 , … , p n .

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

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

Так как простых чисел очень много, то таблицы ограничивают числами 100 , 1000 , 10000 и так далее.

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

Рассмотрим пошагово.

Если начать с числа 2 , то оно имеет только 2 делителя: 2 и 1, значит, его можно занести в таблицу. Также и с числом 3 . Число 4 является составным, следует разложить его еще на 2 и 2 . Число 5 является простым, значит, можно зафиксировать в таблице. Так выполнять вплоть до числа 100 .

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

Способ при помощи решета Эратосфена считают самым удобным. Рассмотрим на примере таблиц, приведенных ниже. Для начала записываются числа 2 , 3 , 4 , … , 50 .

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

Переходим к вычеркиванию чисел, кратных 5 . Получим:

Вычеркиваем числа, кратные 7 , 11 . В конечном итоге таблица получает вид

Перейдем к формулировке теоремы.

Теорема 3

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

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

Необходимо обозначить b наименьший делитель составного числа а. Существует такое целое число q , где a = b · q , причем имеем, что b ≤ q . Недопустимо неравенство вида b > q , так как происходит нарушение условия. Обе части неравенства b ≤ q следует умножить на любое положительное число b , не равное 1 . Получаем, что b · b ≤ b · q , где b 2 ≤ a и b ≤ a .

Из доказанной теоремы видно, что вычеркивание чисел в таблице приводит к тому, что необходимо начинать с числа, которое равняется b 2 и удовлетворяет неравенству b 2 ≤ a . То есть, если вычеркнуть числа, кратные 2 , то процесс начинается с 4 , а кратных 3 – с 9 и так далее до 100 .

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

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

Пример 1

Доказать что число 898989898989898989 является составным.

Решение

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

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

Пример 2

Определить составное или простое число 11723 .

Решение

Теперь необходимо найти все делители для числа 11723 . Необходимо оценить 11723 .

Отсюда видим, что 11723 < 200 , то 200 2 = 40 000 , а 11 723 < 40 000 . Получаем, что делители для 11 723 меньше числа 200 .

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

При разложении получим, что 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 – это все простые числа. Весь данный процесс можно изобразить как деление столбиком. То есть разделить 11723 на 19 . Число 19 является одним из его множителей, так как получим деление без остатка. Изобразим деление столбиком: