Простое число в математике что это такое простыми словами

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

Натуральные числа, большие единицы и числа, которые не являются простыми, называют составными числами. Т.о., все натуральные числа делятся на 3 класса: единица (имеет 1 делитель), простые числа (имеют 2 делителя) и составные числа (имеют больше 2-х делителей).

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

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, …

Если представить натуральные числа как произведение простых, то это будет называться разложение на простые либо факторизация числа.

Самое большое простое число, которое известно.

Некоторые свойства простых чисел.

Допустим, p — простое, и p делит ab, тогда p делит a либо b.

Кольцо вычетов Z_n будет называться полем только в случае, если n — простое.

Характеристика всех полей — это нуль либо простое число.

Когда G — конечная группа, у которой порядок |G| делят на p, значит, у G есть элемент порядка p (теорема Коши).

Натуральное p > 1 будет простым лишь в случае, если (p-1)! + 1 можно подулить на p (теорема Вильсона).

Когда n > 1 — натуральное, значит, есть простое p: n 1 — целые взаимно простые числа, содержит нескончаемое число простых чисел (Теорема Дирихле о простых числах в арифметической прогрессии).

Любое простое число, которое большее тройки, можно представить как 6k+1 либо 6k-1, где k — натуральное число. Исходя из этого, когда разность нескольких последовательных простых чисел (при k>1) одинаковая, значит, она точно делится на шесть — к примеру: 251-257-263-269; 199-211-223; 20183-20201-20219.

Теорема Грина-Тао. Есть бесконечные арифметические прогрессии, которые состоят из простых чисел.

Ни одно простое число нельзя представить как n 2k+1 +1, где n>1, k>0. Другими словами, число, которое предшествует простому, не может быть кубом либо более высокой нечётной степенью с основанием, которое больше единицы.

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

Источник

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

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

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

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

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

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

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

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

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

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

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

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

Источник

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

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

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

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, … (последовательность A000040 в OEIS, см. также список простых чисел)

Содержание

Разложение натуральных чисел в произведение простых

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

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

Алгоритмы поиска и распознавания простых чисел

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

Однако, на практике вместо получения списка простых чисел зачастую требуется проверить, является ли данное число простым. Алгоритмы, решающие эту задачу, называются тестами простоты. Существует множество полиномиальных тестов простоты, но большинство их являются вероятностными (например, тест Миллера — Рабина) и используются для нужд криптографии. В 2002 году было доказано, что задача проверки на простоту в общем виде полиномиально разрешима, но предложенный детерминированный тест Агравала — Каяла — Саксены имеет довольно большую вычислительную сложность, что затрудняет его практическое применение.

Для некоторых классов чисел существуют специализированные эффективные тесты простоты (см. ниже).

Бесконечность множества простых чисел

Простых чисел бесконечно много. Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (книга IX, утверждение 20). Его доказательство может быть кратко воспроизведено так:

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

Математики предлагали другие доказательства. Одно из них (приведённое Эйлером) показывает, что сумма величин, обратных к первым n простым числам, неограниченно растёт с ростом n.

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

Наибольшее известное простое

Наибольшим известным простым числом по состоянию на февраль 2011 года является . Оно содержит 12 978 189 десятичных цифр и является простым числом Мерсенна (M_43112609). Его нашли 23 августа 2008 года на математическом факультете университета UCLA в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS.

Числа Мерсенна выгодно отличаются от остальных наличием эффективного теста простоты: теста Люка — Лемера. Благодаря ему простые числа Мерсенна давно удерживают рекорд как самые большие известные простые.

За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр EFF назначила [2] денежные призы соответственно в 150 000 и 250 000 долларов США. Ранее EFF уже присуждала призы за нахождение простых чисел из 1 000 000 и 10 000 000 десятичных цифр.

Простые числа специального вида

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

С использованием теста Бриллхарта-Лемера-Селфриджа (англ.) может быть проверена простота следующих чисел:

Для поиска простых чисел обозначенных типов в настоящее время используются проекты распределенных вычислений GIMPS, PrimeGrid, Ramsey@Home, Seventeen or Bust, Riesel Sieve, Wieferich@Home.

Некоторые свойства

содержащий 26 переменных и имеющий степень 25. Наименьшая степень для известных многочленов такого типа — 5 при 42 переменных; наименьшее число переменных — 10 при степени около 15905. [6] Этот результат является частным случаем доказанной Юрием Матиясевичем диофантовости любого перечислимого множества.

Открытые вопросы

До сих пор существует много открытых вопросов относительно простых чисел, наиболее известные из которых были перечислены Эдмундом Ландау на Пятом Международном математическом конгрессе [7] :

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

Приложения

Большие простые числа (порядка ) используются в криптографии с открытым ключом. Простые числа также используются в хеш-таблицах и для генерации псевдослучайных чисел (в частности, в ГПСЧ вихрь Мерсенна).

Источник

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

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

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

[простое число] х 1 = [простое число]

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

Составные числа — это числа, у которых есть делители, кроме самих себя и 1. Таким образом, все целые положительные числа, кроме 0 и 1, — либо простые, либо составные. Любое составное число можно представить в виде произведения простых сомножителей, то есть его можно разложить на множители, включающие только простые числа. Это наводит на мысль о важности простых чисел: это первичные блоки, из которых можно построить все остальные числа. Распределение простых чисел Теорема о распределении простых чисел, доказанная в XIX в., утверждает, что вероятность того, что случайным образом выбранное число n — простое, везде пропорциональна количеству цифр в нем, или логарифму n. Это означает, что чем больше число, тем меньше вероятность того, что оно будет простым.

Средний интервал между следующими друг за другом простыми числами к n приблизительно равен логарифму n, или ln(n).

Найти простое

Один из способов определения простого числа — «тест простоты». Если n — исследуемое число, то нужно попробовать разделить его на все числа больше 1 и меньше 1/2 n.

Самое большое обнаруженное простое число (на апрель 2015) содержит 17 425 170 знаков, это 2 57 885 161 – 1. Не стоит засиживаться до ночи, пытаясь выяснить следующее, если только вы не специализируетесь на этом, однако Фонд электронных рубежей (Electronic Frontier Foundation) назначил премию за первое простое число минимум в 100 миллионов знаков, а также за первое простое число минимум в пол миллиарда знаков.

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

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

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

Нарисуйте таблицу с 10 колонками и столькими рядами, сколько вам нужно, чтобы вместить числа, которые вы хотите проверить: если вы хотите проверить числа до n, нужно сделать таблицу от 1 до n. Начиная с 4, продвигайтесь по таблице и вычеркивайте все, что делится на 2. Затем вычеркните все, что делится на 3, затем — на 5, затем — на 7 и т. д., прокладывая путь сквозь простые числа. Когда вы доберетесь до делителя 1/2 n – 1, можете остановиться, так как большие числа не могут быть делителем n или меньших чисел. Числа, которые не были зачеркнуты, — простые.

Прискорбное пренебрежение

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

Есть работа

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

Составное число используется для генерации кода, который называется открытый ключ, который банк (или кто-нибудь) посылает человеку, желающему зашифровать свои данные. Если вы покупаете что-нибудь онлайн, данные вашей кредитки должны быть зашифрованы с использованием этого публичного ключа, шифрование происходит на вашем конце связи. Зашифрованные данные окажутся пустым набор слов, если будут перехвачены в процессе передачи. Когда данные вашей карты прибывают на другой конец, закрытый ключ — созданный из Р₁ и Р₂ — используется для расшифровки.

Это работает, так как очень сложно найти простые числа, из которых было получено составное, когда речь идет о больших числах. Любому хакеру понадобится 1000 лет компьютерного времени, чтобы взломать код и найти первоначальные простые числа. Именно потому, что так сложно взломать современный шифр, правительства скорее действительно предпочтут, чтобы разработчики встраивали «бэкдор» в свои системы, что позволяет им порой следить за тем, что делают люди.

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

• ← Простое число в математике что это такое пример
• Простое число в математике что это →