Для чего нужны простые и составные числа

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

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

Источник

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

Простые и составные числа: Freepick

Математика по-разному называет числа и делит их на определенные группы. На уроках услышите о простых и составных числах. Чем обосновано такое деление и как научиться различать эти категории чисел? Помогут разобраться в этом вопросе примеры.

Простые числа и их особенности

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

Познакомимся с первой группой чисел. Простое число — это любое число, которое можно разделить само на себя и на единицу. Яркий и простой для запоминания пример — число 13. Легко заключить, что разделить его получится:

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

Числа в математике: Freepick

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

Такие операции можно выполнять до числа 100 и далее.

Но в книге о простых числах выдающегося математика Л. Г. Шнирельмана указано, что существует бесконечное множество простых чисел. Как быть и можно ли ускорить процесс их нахождения?

Математики нашли решение этой задачи. Быстро отобрать простые числа можно с помощью решета Эратосфена:

На уроках часто пользуются уже готовыми таблицами, но важно помнить о том, каким образом в них оказываются те или иные числа. Кроме простых, выделяют также группу взаимно простых чисел, у которых есть только один общий делитель — единица (например, 14 и 25).

Что такое составные числа

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

Рассмотрим это на примере:

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

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

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

Математические расчеты: Freepick

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

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

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

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

Уникальная подборка новостей от нашего шеф-редактора

Источник

Простые числа: история и факты

Свойства простых чисел впервые начали изучать математики Древней Греции. Математики пифагорейской школы (500 — 300 до н.э.) в первую очередь интересовались мистическими и нумерологическими свойствами простых чисел. Они первыми пришли к идеям о совершенных и дружественных числах.

У совершенного числа сумма его собственных делителей равна ему самому. Например, собственные делители числа 6: 1, 2 и 3. 1 + 2 + 3 = 6. У числа 28 делители — это 1, 2, 4, 7 и 14. При этом, 1 + 2 + 4 + 7 + 14 = 28.

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

Ко времени появления работы Евклида «Начала» в 300 году до н.э. уже было доказано несколько важных фактов касательно простых чисел. В книге IX «Начал» Эвклид доказал, что простых чисел бесконечное количество. Это, кстати, один из первых примеров использования доказательства от противного. Также он доказывает Основную теорему арифметики – каждое целое число можно представить единственным образом в виде произведения простых чисел.

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

Следующие открытия были сделаны уже в начале 17-го века математиком Ферма. Он доказал гипотезу Альбера Жирара, что любое простое число вида 4n+1 можно записать уникальным образом в виде суммы двух квадратов, и также сформулировал теорему о том, что любое число можно представить в виде суммы четырёх квадратов.

Он разработал новый метод факторизации больших чисел, и продемонстрировал его на числе 2027651281 = 44021 × 46061. Также он доказал Малую теорему Ферма: если p – простое число, то для любого целого a будет верно a p = a modulo p.

Малая теорема Ферма послужила основой множества других результатов в теории чисел и методов проверки чисел на принадлежность к простым – многие из которых используются и по сей день.

Ферма много переписывался со своими современниками, в особенности с монахом по имени Марен Мерсенн. В одном из писем он высказал гипотезу о том, что числа вида 2 n +1 всегда будут простыми, если n является степенью двойки. Он проверил это для n = 1, 2, 4, 8 и 16, и был уверен, что в случае, когда n не является степенью двойки, число не обязательно получалось простым. Эти числа называются числами Ферма, и лишь через 100 лет Эйлер показал, что следующее число, 2 32 + 1 = 4294967297 делится на 641, и следовательно, не является простым.

Числа вида 2 n — 1 также служили предметом исследований, поскольку легко показать, что если n – составное, то и само число тоже составное. Эти числа называют числами Мерсенна, поскольку он активно их изучал.

Но не все числа вида 2 n — 1, где n – простое, являются простыми. К примеру, 2 11 — 1 = 2047 = 23 * 89. Впервые это обнаружили в 1536 году.

Многие годы числа такого вида давали математикам наибольшие известные простые числа. Что число M₁₉, было доказано Катальди в 1588 году, и в течение 200 лет было наибольшим известным простым числом, пока Эйлер не доказал, что M₃₁ также простое. Этот рекорд продержался ещё сто лет, а затем Люкас показал, что M₁₂₇ — простое (а это уже число из 39 цифр), и после него исследования продолжились уже с появлением компьютеров.

В 1952 была доказана простота чисел M₅₂₁, M₆₀₇, M₁₂₇₉, M₂₂₀₃ и M₂₂₈₁.

К 2005 году найдено 42 простых чисел Мерсенна. Наибольшее из них, M_25964951, состоит из 7816230 цифр.

Работа Эйлера оказала огромное влияние на теорию чисел, в том числе и простых. Он расширил Малую теорему Ферма и ввёл φ-функцию. Факторизовал 5-е число Ферма 2 32 +1, нашёл 60 пар дружественных чисел, и сформулировал (но не смог доказать) квадратичный закон взаимности.

Он первым ввёл методы математического анализа и разработал аналитическую теорию чисел. Он доказал, что не только гармонический ряд ∑ (1/n), но и ряд вида

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

получаемый суммой величин, обратных к простым числам, также расходится. Сумма n членов гармонического ряда растёт примерно как log(n), а второй ряд расходится медленнее, как log[ log(n) ]. Это значит, что, например, сумма обратных величин ко всем найденным на сегодняшний день простым числам даст всего 4, хотя ряд всё равно расходится.

На первый взгляд кажется, что простые числа распределены среди целых довольно случайно. К примеру, среди 100 чисел, идущих прямо перед 10000000, встречается 9 простых, а среди 100 чисел, идущих сразу после этого значения – всего 2. Но на больших отрезках простые числа распределены достаточно равномерно. Лежандр и Гаусс занимались вопросами их распределения. Гаусс как-то рассказывал другу, что в любые свободные 15 минут он всегда подсчитывает количество простых в очередной 1000 чисел. К концу жизни он сосчитал все простые числа в промежутке до 3 миллионов. Лежандр и Гаусс одинаково вычислили, что для больших n плотность простых чисел составляет 1/log(n). Лежандр оценил количество простых чисел в промежутке от 1 до n, как

А Гаусс – как логарифмический интеграл

с промежутком интегрирования от 2 до n.

Утверждение о плотности простых чисел 1/log(n) известно как Теорема о распределении простых чисел. Её пытались доказать в течение всего 19 века, а прогресса достигли Чебышёв и Риман. Они связали её с гипотезой Римана – по сию пору не доказанной гипотезой о распределении нулей дзета-функции Римана. Плотность простых чисел была одновременно доказана Адамаром и Валле-Пуссеном в 1896 году.

В теории простых чисел есть ещё множество нерешённых вопросов, некоторым из которых уже многие сотни лет:

Текущие рекорды среди простых чисел

Самое большое простое число, вычисленное проектом GIMPS [Great Internet Mersenne Prime Search], можно посмотреть в таблице на официальной странице проекта.
www.mersenne.org/primes

Самые большие близнецы среди простых чисел – это 2003663613 × 2 195000 ± 1. Они состоят из 58711 цифр, и были найдены в 2007 году.

Самое большое факториальное простое число (вида n! ± 1) – это 147855! — 1. Оно состоит из 142891 цифр и было найдено в 2002.

Наибольшее праймориальное простое число (число вида n# ± 1) – это 1098133# + 1.

Источник

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

Основные определения

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

Простое число — это натуральное число больше 1, у которого есть всего два делителя: единица и само число.

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

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

Число 2 — первое наименьшее простое, единственное четное, простое число. Все остальные — нечетные.

Число 4 — первое наименьшее составное число.

В математике есть первые простые и составные числа, но последних таких чисел не существует.

А еще не существует простых чисел, которые оканчиваются на 4, 6, 8 или 0. В числе простых есть только одно число, которое заканчивается на 2 — и это само число 2. Из оканчивающихся на 5 — число 5. Все остальные оканчиваются на 1, 3, 7 или 9, за исключением 21, 27, 33 и 39.

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

Курсы подготовки к ОГЭ по математике от Skysmart придадут уверенности в себе и помогут освежить знания перед экзаменом.

Источник

Простые и составные числа, определения, примеры, таблица простых чисел, решето Эратосфена

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ: 11723 является составным числом.

Источник