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

  • автор:

Что является простым числом. Простые числа

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

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

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

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

Узнайте о подводных камнях малой теоремы Ферма. Все числа, для которых не выполняются условия теста, являются составными, однако остальные числа лишь вероятно относятся к простым. Если вы хотите избежать неверных результатов, поищите n в списке «чисел Кармайкла» (составных чисел, которые удовлетворяют данному тесту) и «псевдопростых чисел Ферма» (эти числа соответствуют условиям теста лишь при некоторых значениях a ).

Если удобно, используйте тест Миллера-Рабина. Хотя данный метод довольно громоздок при вычислениях вручную, он часто используется в компьютерных программах. Он обеспечивает приемлемую скорость и дает меньше ошибок, чем метод Ферма. Составное число не будет принято за простое, если провести расчеты для более ¼ значений a . Если вы случайным способом выберете различные значения a и для всех них тест даст положительный результат, можно с достаточно высокой долей уверенности считать, что n является простым числом.

Для больших чисел используйте модульную арифметику. Если у вас под рукой нет калькулятора с функцией mod или калькулятор не рассчитан на операции с такими большими числами, используйте свойства степеней и модульную арифметику, чтобы облегчить вычисления. Ниже приведен пример для 3 50 <\displaystyle 3^<50>> mod 50:

  • Перепишите выражение в более удобном виде: mod 50. При расчетах вручную могут понадобиться дальнейшие упрощения.
  • (3 25 ∗ 3 25) <\displaystyle (3^<25>*3^<25>)> mod 50 = mod 50 mod 50) mod 50. Здесь мы учли свойство модульного умножения.
  • 3 25 <\displaystyle 3^<25>> mod 50 = 43.
  • (3 25 <\displaystyle (3^<25>> mod 50 ∗ 3 25 <\displaystyle *3^<25>> mod 50) mod 50 = (43 ∗ 43) <\displaystyle (43*43)>mod 50.
  • = 1849 <\displaystyle =1849>mod 50.
  • = 49 <\displaystyle =49>.

Простое число — это натуральное (целое положительное) число , которое делится без остатка только на два натуральных числа: на и на само себя. Иными словами, простое число имеет ровно два натуральных делителя: и само число .

В силу определения, множество всех делителей простого числа является двухэлементным, т.е. представляет собой множество .

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

Последовательность простых чисел выглядит так:

Основная теорема арифметики

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

Разложение натурального числа title=»Rendered by QuickLaTeX.com» height=»13″ width=»42″ style=»vertical-align: -1px;»> в произведение простых чисел называют каноническим :

где — простое число, и . Например, каноническое разложение натурального числа выглядит так: .

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

Свойства простых чисел
Решето Эратосфена

Одним из наиболее известных алгоритмов поиска и распознавания простых чисел является решето Эратосфена . Так этот алгоритм был назван в честь греческого математика Эратосфена Киренского, которого считают автором алгоритма.

Для нахождения всех простых чисел, меньших заданного числа , следуя методу Эратосфена, нужно выполнить следующие шаги:

Шаг 1. Выписать подряд все натуральные числа от двух до , т.е. .
Шаг 2. Присвоить переменной значение , то есть значение равное наименьшему простому числу.
Шаг 3. Вычеркнуть в списке все числа от до кратные , то есть числа: .
Шаг 4. Найти первое незачёркнутое число в списке, большее , и присвоить переменной значение этого числа.
Шаг 5. Повторить шаги 3 и 4 до достижения числа .

Процесс применения алгоритма будет выглядеть следующим образом:

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

Гипотеза Гольдбаха

Обложка книги «Дядюшка Петрос и гипотеза Гольдбаха»

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

  • Верно ли, что каждое чётное число, большее двух, может быть представлено в виде суммы двух простых чисел (бинарная гипотеза Гольдбаха)?
  • Верно ли, что каждое нечётное число, большее 5, может быть представлено в виде суммы трёх простых чисел (тернарная гипотеза Гольдбаха)?

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

Гипотеза Гольдбаха получила широкую известность за пределами математического сообщества в 2000-м году благодаря рекламному маркетинговому трюку издательских компаний Bloomsbury USA (США) и Faber and Faber (Великобритания). Указанные издательства, выпустив книгу «Uncle Petros and Goldbach’s Conjecture» («Дядюшка Петрос и гипотеза Гольдбаха»), пообещали выплатить в течение 2-х лет с момента издания книги приз 1 миллион долларов США тому, кто докажет гипотезу Гольдбаха. Иногда упомянутый приз от издательств путают с премиями за решение «Задач тысячелетия» (Millennium Prize Problems). Не стоит заблужаться, гипотеза Гольдбаха не отнесена «Институтом Клэя» к «задачам тысячелетия», хотя и является при этом тесно связанной с гипотезой Римана — одной из «задач тысячелетия».

Книга «Простые числа. Долгая дорога к бесконечности»

Обложка книги «Мир математики. Простые числа. Долгая дорога к бесконечности»

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

Дополнительно процитирую начало второй главы этой книги: «Простые числа представляют из себя одну из важных тем, которые возвращают нас к самым истокам математики, а затем по пути возрастающей сложности приводят на передний край современной науки. Таким образом, было бы очень полезно проследить увлекательную и сложную историю теории простых чисел: как именно она развивалась, как именно были собраны факты и истины, которые в настоящее время считаются общепринятыми. В этой главе мы увидим, как целые поколения математиков тщательно изучали натуральные числа в поисках правила, предсказывающего появление простых чисел, — правила, которое в процессе поиска становилось все более и более ускользающим. Мы также подробно рассмотрим исторический контекст: в каких условиях математики работали и в какой степени в их работе применялись мистические и полурелигиозные практики, которые совсем не похожи на научные методы, используемые в наше время. Тем не менее медленно и с трудом, но была подготовлена почва для новых воззрений, вдохновлявших Ферма и Эйлера в XVII и XVIII в.в.»

  • Перевод

Свойства простых чисел впервые начали изучать математики Древней Греции. Математики пифагорейской школы (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 «Начал» Эвклид доказал, что простых чисел бесконечное количество. Это, кстати, один из первых примеров использования доказательства от противного. Также он доказывает Основную теорему арифметики – каждое целое число можно представить единственным образом в виде произведения простых чисел.

Также он показал, что если число 2 n -1 является простым, то число 2 n-1 * (2 n -1) будет совершенным. Другой математик, Эйлер, в 1747 году сумел показать, что все чётные совершенные числа можно записать в таком виде. По сей день неизвестно, существуют ли нечётные совершенные числа.

В году 200 году до н.э. грек Эратосфен придумал алгоритм для поиска простых чисел под названием «Решето Эратосфена».

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

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

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

Это утверждение доказывает половину того, что было известно как «китайская гипотеза», и датируется 2000 годами ранее: целое n является простым тогда и только тогда, если 2 n -2 делится на n. Вторая часть гипотезы оказалась ложной – к примеру, 2 341 — 2 делится на 341, хотя число 341 составное: 341 = 31 × 11.

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

Ферма много переписывался со своими современниками, в особенности с монахом по имени Марен Мерсенн. В одном из писем он высказал гипотезу о том, что числа вида 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 19 , было доказано Катальди в 1588 году, и в течение 200 лет было наибольшим известным простым числом, пока Эйлер не доказал, что M 31 также простое. Этот рекорд продержался ещё сто лет, а затем Люкас показал, что M 127 — простое (а это уже число из 39 цифр), и после него исследования продолжились уже с появлением компьютеров.

В 1952 была доказана простота чисел M 521 , M 607 , M 1279 , M 2203 и M 2281 .

К 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, как

π(n) = n/(log(n) — 1.08366)

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

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

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

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

  • гипотеза о простых числах-близнецах – о бесконечном количестве пар простых чисел, отличающихся друг от друга на 2
  • гипотеза Гольдбаха: любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел
  • бесконечно ли количество простых чисел вида n 2 + 1 ?
  • всегда ли можно найти простое число между n 2 and (n + 1) 2 ? (факт, что между n и 2n всегда есть простое число, было доказан Чебышёвым)
  • бесконечно ли число простых чисел Ферма? есть ли вообще простые числа Ферма после 4-го?
  • существует ли арифметическая прогрессия из последовательных простых чисел для любой заданной длины? например, для длины 4: 251, 257, 263, 269. Максимальная из найденных длина равна 26 .
  • бесконечно ли число наборов из трёх последовательных простых чисел в арифметической прогрессии?
  • n 2 — n + 41 – простое число для 0 ≤ n ≤ 40. Бесконечно ли количество таких простых чисел? Тот же вопрос для формулы n 2 — 79 n + 1601. Эти числа простые для 0 ≤ n ≤ 79.
  • бесконечно ли количество простых чисел вида n# + 1? (n# — результат перемножения всех простых чисел, меньших n)
  • бесконечно ли количество простых чисел вида n# -1 ?
  • бесконечно ли количество простых чисел вида n! + 1?
  • бесконечно ли количество простых чисел вида n! – 1?
  • если p – простое, всегда ли 2 p -1 не содержит среди множителей квадратов простых чисел
  • содержит ли последовательность Фибоначчи бесконечное количество простых чисел?

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

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

Наибольшее праймориальное простое число (число вида n# ± 1) – это 1098133# + 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 тысяч долларов США.

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

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

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

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

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

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

Простое число — это натуральное число имеющие 2 делителя (делится без остатка): единицу и само это число. При этом единица не является ни простым, ни составным числом. К примеру: 2, 3, 5, 7, 11 и т.д — простые числа.

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

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

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 151
157 163 167 173 179 181 191 193 197 199 211 223
227 229 233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349 353 359
367 373 379 383 389 397 401 409 419 421 431 433
439 443 449 457 461 463 467 479 487 491 499

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

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

Пример: определить 489 простое число или нет?

  1. 1 способ. Путём перебора ищем простой делитель. 489 на 2 без остатка не делится. Проверяем 3. На 3 делится, получается 163. Значит число не простое.
  2. 2 способ. Зная признаки делимости, можно легко понять, что 489 делится на 3.

Взаимно простые числа

Взаимно простые числа — это числа, которые не имеют общих делителей, кроме единицы. Подробнее про взаимно простые числа смотрите тут

Определить является ли число простым

Известно, что натуральные числа, исключая 1, делятся на простые и составные. Елиница (1) ни к простым, ни к составным числам не относится, т. к. имеет лишь один делитель — 1. Натуральное число (большее 0), у которого имеется лишь два разных делителя: оно само и 1, является простым числом. Возьмем числа 2, 3, 5, 19, 1979. Эти числа делятся нацело только на себя и на 1, следовательно, мы имеем дело с простыми числами. Остальные числа считаются составными. Например, 4, 10, 144. Простых чисел, в то же время как и составных, бесконечно много. Выдающийся древнегреческий математик Евклид, проживавший в третьем веке до н. э. дает такое определение простым числам: «Простое число есть измеряемое только единицей . ». В «Началах» Евклид приводит доказательство бесконечного множества простых чисел. Допустим, что у простых чисел имеется конечное число. Если их перемножить и прибавить единицу, то получим число, которое мы не сможем поделить без остатка на любое из этого набора простых чисел. В остатке всегда остается 1. Отсюда выходит, что должно быть простое число, не вошедшее в этот набор, на которое делится полученное число, что является противоречием. Факт бесконечности простых чисел был доказан и другими математиками в разные времена. Из известных науке простых чисел наибольшее — число Мерсенна, равное 2 в степени 132049 — 1. Вопрос о том, как простые числа распределены в натуральном ряду, очень сложный. Есть участки в натуральном ряду, где они расположены гуще и даже очень близко друг к другу. Возьмем к примеру, 2 и 3, 191 и 193. Такие пары простых чисел называют близнецами.

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

Добавить комментарий

Ваш адрес email не будет опубликован.