Простые числа — это натуральные числа, больше единицы, которые делятся без остатка только на 1 и на само себя. Например: 2, 3, 5, 7, 11, 13, 17, 19, 23. Единица не является ни простым числом, ни составным.
Последовательность простых чисел начинается с 2 и является бесконечной; наименьшее простое число — это 2 (делится на 1 и на самого себя).
Составные числа — это натуральные числа, у которых есть больше двух делителей (1, оно само и например, 2 и/или 3); это противоположность простым числам. Например: 4, 6, 9, 12 (все делятся на 2, на 3, на 1 и на само себя).
Все натуральные числа считаются либо простыми, либо составными (кроме 1).
Натуральные числа — это те числа, которые возникли натуральным образом при счёте предметов; например: 1, 2, 3, 4. (нет ни дробей, ни 0, ни чисел ниже 0).
Зачастую множество простых чисел в математике обозначается буквой P.
Простые числа до 1000
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
Как определить, является ли число простым?
Очень простой способ понять, является ли число простым — нужно его разделить на простые числа и посмотреть, получится ли целое число. Сначала нужно попробовать его разделить на 2 и/или на 3. Если получилось целое число, то оно не является простым.
Если после первого деления не получилось целого числа, значит нужно попробовать разделить его на другие простые числа: 5, 7, 11 и т. д. (на 9 делить не нужно, т. к. это не простое число и оно делится на 3, а на него вы уже делили).
Более структурированный метод — это решето Эратосфена.
Решето Эратосфена
Это алгоритм поиска простых чисел. Для этого нужно:
Те числа, которые не будут вычеркнуты в конце этого процесса, являются простыми.
Взаимно простые числа
Это натуральные числа, у которых 1 — это единственный общий делитель. Например:
Число Мерсенна
Простое число Мерсенна — это простое число вида:
До 1536 г. многие считали, что числа такого вида были все простыми, пока математик Ульрих Ригер не доказал, что 2 (^11) – 1 = 2047 было составным (23 x 89). Затем появились и другие составные числа (p = 23, 29, 31, 37 и др.).
Например, для p = 23 это 2 (^23) – 1 = 8 388 607; И 47 x 178481 = 8 388 607, значит оно составное.
Почему 1 не является простым числом?
Российские математики Боревич и Шафаревич в своей знаменитой работе «Теория чисел» (1964 г.) определяют простое число как p (элемент кольца D), не равен ни 0, ни 1. И p можно называть простым числом, если его невозможно разложить на множители ab (т.е. p = ab), притом ни один из них не является единицей в D. Так как 1 невозможно представить ни в одном, ни в другом виде, 1 не считается ни простым числом, ни составным.
Почему 4 не является простым числом?
Простое число — это натуральное число, больше единицы, которое делится без остатка на 1 и на само себя. Т. к. 4 можно разделить на 1, на 2 и на 4, из-за деления на 2 оно не является простым.
Самое большое простое число
21 декабря 2018 года Great Internet Mersenne Prime Search (проект, целью которого является открытие новых простых чисел Мерсенна) обнаружил новое самое большое известное простое число:
Новое простое число также именуется M82589933 и в нём более чем на полтора миллиона цифр больше, чем в предыдущем (найденном годом ранее).
В статье рассматриваются понятия простых и составных чисел. Даются определения таких чисел с примерами. Приводим доказательство того, что количество простых чисел неограниченно и произведем запись в таблицу простых чисел при помощи метода Эратосфена. Будут приведены доказательства того, является ли число простым или составным.
Простые и составные числа – определения и примеры
Простые и составные числа относят к целым положительным. Они обязательно должны быть больше единицы. Делители также подразделяют на простые и составные. Чтобы понимать понятие составных чисел, необходимо предварительно изучить понятия делителей и кратных.
Составными числами называют целые числа, которые больше единицы и имеют хотя бы три положительных делителя.
Единица не является ни простым ни составным числом. Она имеет только один положительный делитель, поэтому отличается от всех других положительных чисел. Все целые положительные числа называют натуральными, то есть используемые при счете.
Простые числа – это натуральные числа, имеющие только два положительных делителя.
Составное число – это натуральное число, имеющее более двух положительных делителей.
Натуральные числа, которые не являются простыми, называют составными.
Таблица простых чисел
Для того, чтобы было проще использовать простые числа, необходимо использовать таблицу:
Рассмотрим теорему, которая объясняет последнее утверждение.
Наименьший положительный и отличный от 1 делитель натурального числа, большего единицы, является простым числом.
Простых чисел бесконечно много.
Видно, что может быть найдено любое простое число среди любого количества заданных простых чисел. Отсюда следует, что простых чисел бесконечно много.
Решето Эратосфена
Данный способ неудобный и долгий. Таблицу составить можно, но придется потратить большое количество времени. Необходимо использовать признаки делимости, которые ускорят процесс нахождения делителей.
Перейдем к формулировке теоремы.
Данное число простое или составное?
Перед решением необходимо выяснять, является ли число простым или составным. Зачастую используются признаки делимости. Рассмотрим это на ниже приведенных примере.
Доказать что число 898989898989898989 является составным.
Здравствуйте, уважаемые читатели блога KtoNaNovenkogo.ru. Сегодня мы поговорим о таком математическом понятии, как ПРОСТЫЕ ЧИСЛА.
В школе это проходят в 5 или 6 классе, в зависимости от программы обучения.
И интересно, что если спросить школьников, что такое простые числа, то они, скорее всего, ответят правильно.
А вот взрослые задумаются и не факт, что вспомнят точное определение. Так что это статья скорее для них.
Простые числа — это.
Итак, вот как выглядит официальное определение:
Простые числа – это такие числа, которые имеют только два делителя. Один из них – единица, а другое – само число.
Чтобы было более понятно, приведем простой пример. Для чисел 5 и 7 надо найти все возможные делители, чтобы в результате образовалось целое число.
Если вы попробуете решить эту задачку, то получите, что 5 и 7 делятся только на 1 и 5, и 1 и 7 соответственно. Во всех других случаях вы получите дробное число. И это как раз означает, что числа 5 и 7 относятся к простым.
А вот попробуем по той же схеме разобрать числа 6 и 9. В первом случае мы получим, что 6 можно поделить на 1, 2, 3 и 6, а число 9 – на 1, 3 и 9. И это уже противоречит определению простых чисел, значит, 6 и 9 таковыми не являются.
Они называются в математике – СОСТАВНЫМИ ЧИСЛАМИ.
Список и таблица простых чисел
Некоторые ошибочно полагают, что наименьшее простое число – это единица.
С одной стороны, в этом есть логика, так как 1 делится только на 1. Но это получается одно и то же число (единица), что противоречит определению простых чисел, в котором четко прописано – «делителей должно быть два».
Значит, минимальное простое число – это 2. А первоначальный ряд выглядит следующим образом:
При желании можете проверить эти числа на предмет деления. Мы же скажем, что этот ряд на самом деле не окончательный.
Количество простых чисел не ограничено. Или говоря математическим языком, оно стремится к бесконечности.
История простых чисел
Первые упоминания о простых числах относятся к Древнему Египту. В Британском музее хранится папирус, который датируется 2000 годом до нашей эры. И на нем, согласно расшифровке, содержится учебное пособие по арифметике.
В том числе и про деление чисел. Называется этот артефакт – папирус Райнда, по имени его первого владельца.
В этом документе есть таблица, в которой указаны числа, делящиеся на различные знаменатели. Причем они разделены таким образом, что становится понятно – древние египтяне может и не пользовались понятиям «простое число», но хотя бы имели о нем представление.
Ну а первые исследования простых чисел датируются 300 годом до нашей эры. И связаны они с именем знаменитого древнегреческого математика Евклида.
Как и многое другое, он описал простые и составные числа в своем известном произведении «Начала».
В частности, Евклид описал такие вещи, как:
Сейчас расскажем об этих понятиях подробнее.
Основная теорема арифметики
Основная теорема арифметики, которую придумал еще Евклид, гласит:
Любое натуральное число (это что?), которое больше единицы, может быть представлено в виде произведения простых чисел. Причем их количество не ограничено, а порядок следования неважен.
Если обозначить исходное число буквой N, а простые числа буквами Р1, Р2, Р3 и так далее, то можно записать эту теорему следующим образом:
N = Р1 * Р2 * Р3 * … * РК
Например, возьмем число 100. Его можно разложить на следующие простые числа:
Или более сложный пример – число 23244:
23244 = 149 * 13 * 3 * 2 * 2
Раскладывать на простые числа легко. Можно сперва делить на 2 и 3, а уже в конце автоматически получить более сложные делители.
Ради интереса придумайте любое число и сами найдите его составляющие.
Лемма Евклида
Еще одна теорема, которая имеет прямое отношение к простым числам. Она гласит;
Если некое простое число Р делит произведение чисел X и Y без остатка, то оно может точно так же поделить или X, или Y.
Звучит несколько сложновато, хотя на деле все это просто. Так, возьмем для примера P = 2, X = 6, Y = 9. И тогда получается, что
В нашем примере P делит это произведение без остатка:
А значит наша P может поделить без остатка или X, или Y. Очевидно, что это X:
Y/P = 9/2 = 4,5 (не подходит)
Как быстро и легко определить простые числа
И еще одно понятие, которое связано с простыми числами. Оно названо в честь другого древнегреческого математика Эратосфена Киренского.
Этот человек придумал, как быстро и легко определить простые числа. В частности, он сделал таблицу, в которой были указаны значения до 1000.
Свою таблицу он нарисовал на глиняной дощечке. А после прокалывал те клеточки, на которых были написаны составные числа. В результате получилось нечто вроде решета, отсюда собственно и название метода.
Кстати, пользоваться решетом Эратосфена весьма просто. Например, сделаем таблицу до 50.
После этого из нее надо поочередно вычеркивать числа, которые кратны 2, 3, 5, 7 и 11. В результате получится вот это:
Те числа, которые остались, и есть простые. Можете сравнить этот ряд с тем, который мы давали в начале статьи. Точно таким же способом можно составить абсолютно любой ряд простых чисел = хоть до тысячи, хоть до миллиона и больше.
Вот и все, что мы хотели рассказать о ПРОСТЫХ ЧИСЛАХ в математике.
Удачи вам! До скорых встреч на страницах блога KtoNaNovenkogo.ru
Эта статья относится к рубрикам:
Комментарии и отзывы (1)
Математика весьма хитрая наука, да и простые числа не такие уж и простые, понимание простых и составных чисел привело человечество к тому техническому прогрессу, что окружает нас сейчас.
Значимость простых чисел, как в повседневном применении, так и во всех отраслях математики, невозможно переоценить. Мы спокойно полагаемся на их особые свойства, используя их как фундамент бесчисленного количества элементов нашего общества, ведь они являются неделимой частью самой ткани природы. Простые числа, устойчивые к любому делению на множители, часто называют «атомами» мира математики. Карл Саган сказал о них так:
Очень важен статус простых чисел как фундаментальных строительных блоков всех чисел, которые сами являются строительными блоками нашего понимания Вселенной.
В природе и в нашей жизни простые числа используются повсюду: цикады выстраивают по ним свои жизненные циклы, часовщики применяют их для вычисления тиканья, а в авиационных двигателях с их помощью балансируется частота воздушных импульсов. Однако все эти области применения бледнеют на фоне факта, знакомого каждому криптографу: простые числа находятся в самом сердце современной компьютерной безопасности, то есть они напрямую несут ответственность за защиту всего. Видите замок в адресной строке браузера? Да, это значит, что используется двухключевое «рукопожатие», основанное на простых числах. Как защищается при покупках ваша кредитная карта? Тоже при помощи криптографии на основе простых чисел.
Однако несмотря на то, что мы постоянно полагаемся на их уникальные свойства, простые числа оставались для нас неуловимыми. На протяжении всей истории математики величайшие умы пытались доказать теорему о предсказании чисел, являющихся простыми, или о том, как далеко друг от друга они должны располагаться. На самом деле, некоторые нерешённые задачи, например задача о числах-близнецах, проблема Гольдбаха, простые числа-палиндромы и гипотеза Римана, связаны с этой общей непредсказуемостью и неопределённостью простых чисел при стремлении к бесконечности. Разумеется, со времён Евклида мы обнаружили алгоритмы, позволяющие предсказывать расположение некоторых чисел, но общие теоремы ещё не доказаны, а у предыдущих попыток не было инструментов для проверки больших чисел. Однако технологии 21-го века позволяют исследователям проверять предположения на чрезвычайно больших числах, но такая методика сама по себе вызывает споры, ведь проверка грубым перебором не считается надёжным доказательством. Другими словами, простые числа противятся подчиняться какой-либо универсальной формуле или уравнению, а их расположение в природе кажется случайным.
Однако, одному человеку случайными каракулями удалось доказать, что они как минимум не полностью случайны…
От закорючек к подсказке — скатерть Улама
Одно из величайших доказательств того, что расположение простых чисел не является чистым совпадением, появилось самым маловероятным образом: из бездумных и случайных каракуль одного заскучавшего слушателя лекций.
Схема скатерти Улама
Как гласит история, польский математик Станислав Улам обнаружил этот графический паттерн во время семинара в 1963 году. Рисуя сетку из линий, он решил пронумеровать пересечения по квадратно-спиральному паттерну и начал обводить те числа в спирали, которые были простыми. К его удивлению, обведённые простые числа приходились на диагональные прямые линии, или, как чуть строже сформулировал Улам, «проявляли сильно неслучайное поведение». Скатерть Улама, или спираль простых чисел — это получившееся в результате графическое отображение размеченных в квадратной спирали множества простых чисел. Изначально скатерть была опубликована и получила широкую известность в рубрике «Математические игры» Мартина Гарднера в Scientific American.
Скатерть Улама размером 377×377 (числа примерно до 142 тысяч)
Показанная выше визуализация очевидно выявляет примечательные паттерны, особенно по диагоналям. Но возможно, мы обманываем себя? Часто утверждают, что скатерть Улама — это просто трюк нашего мозга, пытающегося находить паттерны в случайности. К счастью, мы можем использовать две разные методики, чтобы убедиться, что это не так. И визуальное сравнение, и логический анализ с определённостью говорят нам, что паттерн не случаен. Во-первых, мы сравним скатерть Улама, заданную матрицей размером NxN, с матрицей того же размера, содержащей случайно заданные точки. Во-вторых, мы можем воспользоваться своими знаниями о многочленах, чтобы понять, почему нужно ожидать появления некоторого паттерна при графическом отображении простых чисел.
Как говорилось выше, скорее всего, наиболее интуитивно понятным подтверждением неслучайности паттерна будет непосредственное сравнение со скатертью Улама. Для этого нужно создать скатерть Улама и квадратную спираль со случайными расположениями того же размера. Ниже показаны две разные матрицы 200×200, представляющие числовые спирали:
При визуальном сравнении становится достаточно очевидно, что скатерть Улама содержит потрясающие паттерны, особенно вдоль диагональных осей; кроме того, в ней почти нет скоплений точек. С другой стороны, случайное расположение точек не создаёт никаких сразу же заметных паттернов и приводит к скоплению точек в разных направлениях. Несомненно, такой методике не достаёт строгости традиционных доказательств; однако в визуализации спиралей простых чисел есть нечто безупречное: это случайно обнаруженная методика, позволяющая создать график, стимулирующий логику и привлекательный эстетически.
Если подходить к природе простых чисел в более логической и традиционной манере, то вполне разумно ожидать появления паттернов в таких визуализациях. Как сказано выше, линии в диагональных, горизонтальных и вертикальных направлениях, похоже, содержат подсказку. Некоторые из этих линий, не являющихся простыми числами, можно объяснить обычными квадратными многочленами, исключающими возможность появления простых чисел — например, одна из диагональных линий, соответствующая уравнению y = x², очевидно, исключает простые чила. С другой стороны, известно, что некоторые квадратные многочлены, называемые формулами простых чисел (о них мы поговорим ниже), создают высокую плотность простых чисел, например, многочлен генерации простых чисел Эйлера: x² — x — 41; это ещё одна линия, отражающаяся как паттерн в спирали (хотя на показанной выше схеме сложно найти разрывы).
Визуальное сравнение указывает на наличие паттернов, а логический анализ подтверждает существование ожидаемых паттернов. Разумеется, мы ещё далеки от универсальной формулы для нахождения всех простых чисел, но скатерть Улама без сомнений прекрасна, и как символ нашего знания, и как шедевр природного искусства.
Спираль Сакса
Как и во многих областях математики, после появления оригинальной идеи идущая по следам армия коллег-математиков начала делать попытки внести свой вклад в новую тему. Логично, что скатерть Улама вдохновила поколения математиков, стремившихся развить его потрясающую находку. В 1994 году инженер по разработке ПО Роберт Сакс решил использовать свои навыки программиста для визуализации простых чисел различными способами.
Почти как и в случае со скатертью Улама, Сакс решил структурировать свою схему при помощи другой спиральной плоскости. Аналогично показанной выше квадратной спирали, спиральные плоскости отказываются при задании точек от традиционной декартовой числовой системы, потому что являются системой однополярного позиционирования. Просто зная число, можно узнать его расположение в спирали, его позицию относительно всех других чисел в спирали, а также расстояние от него до предыдущего и следующего квадрата числа. Однако вместо квадратной спирали Сакс попытался найти паттерны при помощи целых чисел, наложенных на архимедову спираль со следующими полярными координатами:
Полярные координаты спирали Архимеда/Сакса
При такой методике архимедова спираль центрирована относительно нуля, а квадраты всех натуральных чисел (1,4,9,16,25) расположены на пересечениях спирали и полярной оси (расположенной к востоку от точки начала координат).
Структура спирали Архимеда/Сакса
Подготовив эту схему, мы будем заполнять точки между квадратами вдоль спирали (против часовой стрелки), нанося их на равном расстоянии друг от друга. А в конце, как и в примере со скатертью Улама, мы выделим простые числа, содержащиеся в получившейся спирали.
Числовая спираль Сакса, впервые опубликованная онлайн в 2003 году, привлекательна и визуально, и интеллектуально. Кроме того, как мы вскоре убедимся, она даёт нам более глубокое понимание паттернов простых чисел, чем хорошо известная скатерть Улама, потому что она объединяет разорванные линии псевдоспирали Улама:
Архимедова спираль с отмеченными простыми числами, она же спираль Сакса.
Получившийся график снова демонстрирует заметные паттерны. Почти сразу становится понятно, что есть чистая белая линия, проходящая из центра и растянувшаяся горизонтально на восток. Обратившись к нашей схеме, мы можем убедиться, что это просто линия, содержащая все квадраты целых чисел (r = n^(.5)). Второе наблюдение: паттерн пометок, в отличие от прямых линий скатерти Улама, здесь больше напоминает кривые линии. Оказывается, эти кривые, также известные как кривые произведений, возвращают нас к многочленам, объясняющим паттерны, возникающие в предыдущей спирали. Но прежде чем мы обратимся к ним, ради единства снова сравним спираль Сакса со спиралью случайных значений:
Многочлены и кривые произведений
Работа Роберта Сакса, последовавшая за этим открытием, целиком была сосредоточена на этих кривых произведений, начинающихся в центре спирали или рядом с ним, и под разными углами пересекающихся с витками спирали. Кривые почти прямы, но более типично для них то, что они выполняют частичные, полные или многократные повороты по часовой стрелке (против движения самой спирали) вокруг точки начала координат перед тем, как выпрямиться на определённом смещении от оси «восток-запад». Один из самых поразительных аспектов числовой спирали Сакса заключается в преобладании таких кривых произведений в западном полушарии (в противоположной от квадратов чисел стороне).
Сакс описал кривые произведений как представляющие «произведения множителей с постоянной разностью между ними». Другими словами, каждую кривую можно представить квадратным уравнением (многочленом второй степени), что опять-таки не является простым совпадением, учитывая превалирование квадрата натурального числа в спирали Сакса. Возможно, эти кривые произведений могут привести нас к выводу, что спираль Сакса значительно полезнее в нашем пути к пониманию простых чисел, чем скатерть Улама. Хотя скатерть Улама указала нам на паттерны и возможное существование уравнений, спираль Сакса даёт точки опоры в поиске формул простых чисел — их кривизна и целостность постоянны, а значит, их гораздо проще будет обнаружить. Например, показанная ниже спираль Сакса содержит помеченные линии и относящуюся к ним формулу простых чисел, записанную в стандартном виде. Как я и обещал, знаменитая формула Эйлера для генерации простых чисел снова нам встретилась (последняя запись: n² + n +41):
Благодаря этой числовой спирали Сакс смог сделать потрясающее заявление о том, чем является простое число: положительным целым, лежащим только на одной кривой произведений. Поскольку спираль может раскручиваться бесконечно, сами кривые произведений тоже можно считать бесконечными; теоретически, эти кривые произведений, возможно, могут предсказывать расположение достаточно больших чисел — по крайней мере, такие числа стоят более внимательного изучения.
В целом, спираль Сакса без сомнений подтолкнула нас к более глубокому пониманию простых чисел, предложив более удобные формулы простых чисел.
Значение всего этого
Итак, мы проанализировали и скатерть Улама, и спираль Сакса. Благодаря этим примерам расширилось наше понимание природы, лежащей в основе простых чисел. В частности, спираль Сакса познакомила нас с кривыми произведений, которые по сути являются множеством квадратных уравнений, известных как формулы простых чисел. Оба графика, и Улама, и Сакса, оказались неожиданными и эстетичными, они стимулируют наше любопытство и проливают свет на одну из сложных для всего мира задач.
Какой же урок можно извлечь из всего этого?
Никогда нельзя отказываться от пересмотра кажущихся неразрешимыми проблем, даже если вы занимаетесь этим из чистого любопытства и скуки; открытия может делать каждый и часто они возникают как результат совершенно необычных процессов. Изменив точку зрения на знаменитую задачу благодаря визуализации, Станислав Улам на один шаг приблизил нас к пониманию простых чисел: кто знает, на какие ещё неожиданные открытия мы наткнёмся?
