1 не простое число. Числа. Простые числа. Отрывок, характеризующий Простое число

Определение 1. Простое число − это натуральное число больше единицы, которое делится только на себя и на 1.

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

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

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

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

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

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

Утверждение 1. Если p - простое число и a любое целое число, то либо a делится на p , либо p и a взаимно простые числа.

Действительно. Если p простое число, то оно делится только на себя и на 1, если a не делится на p , то наибольший общий делитель a и p равен 1. Тогда p и a взаимно простые числа.

Утверждение 2. Если произведение нескольких чисел чисел a 1 , a 2 , a 3 , ... делится на простое число p , то по крайней мере одно из чисел a 1 , a 2 , a 3 , ... делится на p .

Действительно. Если бы ни одно из чисел не делилось на p , то числа a 1 , a 2 , a 3 , ... были бы взаимно простые числа по отношению p . Но из следствия 3 () следует, что их произведение a 1 , a 2 , a 3 , ... также взаимно простое по отношению к p , что противоречит условию утверждения. Следовательно по крайней мере один из чисел делится на p .

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

Доказательство. Пусть k составное число, и пусть a 1 один из его делителей отличное от 1 и самого себя. Если a 1 составное, то имеет кроме 1 и a 1 и другой делитель a 2 . Если a 2 число составное, то имеет кроме 1 и a 2 и другой делитель a 3 . Рассуждая таким образом и учитывая, что числа a 1 , a 2 , a 3 , ... убывают и этот ряд содержит конечное число членов, мы дойдем какого-то простого числа p 1 . Тогда k можно представить в виде

Допустим существует два разложения числа k :

Так как k=p 1 p 2 p 3 ... делится на простое число q 1 , то по крайней мере один из множителей, например p 1 делится на q 1 . Но p 1 простое число и делится только на 1 и на себя. Следовательно p 1 =q 1 (т.к. q 1 ≠1)

Тогда из (2) можно исключить p 1 и q 1:

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

Разложение составного числа k можно записать в следующем виде

где p 1 , p 2 , ... различные простые числа, α, β, γ ... целые положительные числа.

Разложение (3) называется каноническим разложением числа.

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

Теорема 2. Количество простых чисел бесконечно много.

Доказательство. Предположим, что существует конечное число простых чисел, и пусть наибольшее простое число равно p . Рассмотрим все числа больше p . По предположению утверждения эти числа должны быть составными и должны делится по крайней мере на один из простых чисел. Выберем число, являющиеся произведением всех этих простых чисел плюс 1:

Число z больше p так как 2p уже больше p . p не делится ни на одно из этих простых чисел, т.к. при делении на каждое из них дает остаток 1. Таким образом мы приходим к противоречию. Следовательно существует бесчисленное множество простых чисел.

Данная теорема является частным случаем более общей теоремы:

Теорема 3. Пусть задана арифметическая прогрессия

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

Справедливо и обратное. Если каждый простой множитель числа n входит по крайней мере столько же раз в число m , то m делится на n .

Утверждение 3. Пусть a 1 ,a 2 ,a 3 ,... различные простые числа входящие в m так, что

где i =0,1,...α , j =0,1,...,β , k=0,1,...,γ . Заметим, что α i принимает α +1 значений, β j принимает β +1 значений, γ k принимает γ +1 значений, ... .

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

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

Сколько делителей может иметь натуральное число? У числа 1 только один делитель. Всякое натуральное имеет два делителя: 1 и само число а . Есть числа, которые не имеют других делителей.

Определение . Натуральное число р называется простым, если оно имеет ровно два делителя: 1 и р.

Определение . Натуральное число, а называется составным, если кроме 1 и а у него есть еще, хотя бы один делитель.

Замечание . Число 1 не относится ни к составным, ни к простым.

Множество N можно разбить на три подмножества.

1 - число, имеющее один делитель.

Простые числа, имеющие ровно два делителя.

Составные числа, имеющие по меньшей мере три делителя.

Выпишем несколько первых простых чисел:

2, 3, 5, 7, 11, 13, 17 …

Бесконечно ли эта последовательность, или можно перечислить все простые числа? Ответ был известен еще Евклиду.

Теорема . (Евклида)

Множество простых чисел бесконечно.

Доказательство . “
”Пусть
- множество всех простых чисел, где - последнее (наибольшее) простое число.

Составим число
. Очевидно,
, значит, N -составное.
делится на какое-то из простых, например, на . Но тогда, по свойствам делимости, 1 делится на , что невозможно.

Рассмотрим некоторые элементарные свойства простых чисел.

1. Пусть
- наименьший делитель натурального числа а.

Тогда p -простое число.

Доказательство . Пусть d -некоторый делитель числа p .

Но p -наименьший делитель
или
p -простое.

2. Пусть
- наименьший делитель составного числа а .

Тогда

Доказательство . а- составное, значит

По условию

3. Пусть а - натуральное число, p - простое число.

Тогда а делится на p , либо а и p взаимно просты.

Доказательство . Пусть
. D - делитель простого
или

Если d =1, то а и p взаимно просты.

Если d =p , то а делится на р.

4. Пусть p -простое число, произведение аb делится на p , тогда а делится на p или b делится на р.

Доказательство . Если а не делится на p , то по свойству 3 НОД (а, p )=1.

Но тогда, по свойству 2 взаимно простых чисел, b делится на р .

Замечание 1 . Свойство 4 легко обобщать по индукции: если произведение
делится на простое p , то найдется множитель , который делится на р.

Замечание 2 . Если произведение
делится на простое p , причем все сомножители - простые числа, то хотя бы один из сомножителей равен р.

Для составления списка простых чисел, не превосходящих заданного числа N , используют алгоритм, который называют “решето Эратосфена”.

Выпишем натуральные числа от 2 до N .

Число 2 - простое. Вычеркнем из списка все числа кратные 2 (кроме 2). Первое из оставшихся-число 3, будет простым. Вычеркнем из списка все числа кратные 3 (кроме числа 3). Первое из оставшихся-число 5, будет простым. Затем вычеркнем все числа, кратные 5 (кроме числа 5) и так далее.

Алгоритм остановится, когда не вычеркнутое число станет больше, чем
. Действительно, по свойству 2, все составные числа в нашем списке имеют делитель
. Значит, они уже вычеркнуты.

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

Пример . Найти все простые числа на промежутке от 2 до 100.

Решение. Вычеркнем (выделим) числа, кратные 2 (рис. 1).

Следующее простое число
все остальные числа - простые (рис. 5).

Замечание . Если p - первое, не вычеркнутое число, то все числа меньше уже вычеркнуты.
Вычеркивать кратные числу p можно начинать с .

п. 2 Факторизация.

Составное число 495 имеет делитель 5, значит
. Второй сомножитель также число составное
. Продолжая процесс, можно исходно число разложить на множители

Определение . Факторизацией составного числа N называется разложение N на простые множители.

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

Пример . Разложить на множитель число 323.

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

Пример . Доказать, что 919 - простое число.

Так как
, то наименьший простой делитель не превосходит 29. Проверкой убедимся, что 919 не делится на простые числа .
- простое число.

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

I. Метод Ферма.

Пусть N - данное число,
. Образуем числа

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

Перебор следует вести в плоть до значения
. (В этом случае
и
). Если точный квадрат не встретился, то N - простое число.

Пример . Разложить на множители N =9271.

Имеем
, значит m=97. вычислим последовательно: .

II. Метод Эйлера.

Эйлер предложил записывать число N в виде суммы
, где d - специально подобранный множитель такой, что НОД (x , yd )=1. величина d зависит от вида числа N . Так, если N =4k +1, то d =1, если N =6k +1, то d =3 и т.д. Всего Эйлер указал 65 множителей d для разных видов N .

Если N представлено в виде
двумя способами (с одним и тем же d ), то N можно разложить на множители.

Например, пусть

Тогда , где НОД (u,v)=1.

Получаем систему:
и

решая которые, находим: .

Пример . Разложить на множители N = 2197.

Отсюда, u=2, v=3, t=10, s=24.

.

III. Ряд приемов основан на простых алгебраических тождествах. Например, теорема Софии Жермен утверждает, что
- составное число.

Это следует из того, что и при N >1 оба множителя больше 1.

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

п.3. О формулах, генерирующих простые числа.

Долгое время математики пытались найти формулу, позволяющие вычислить сколько угодно большое простое число. Наибольшую известность получила формула Мерсенна.
и числа Ферма .

Определение .
- числа Мерсенна.

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

Пусть N - простое число. Тогда, - простые числа.

Но уже
, таким образом, простота числа p не гарантирует простату
.

Простыми оказались числа Мерсенна при .

Простоту числа
(записываемого 139 цифрами) доказал в 1876 году французский математик Э. Люка.

Дальнейший поиск простых чисел Месенна продолжился с помощью вычислительной техники.

Наиболее известное (на 2011 год) простое число является 46–м числом Мерсенна. Это
. Для его записи требуется около 13 миллионов цифр.

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

Критерий Люка – Лемера.

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

На сегодняшний день неизвестно, конечно или бесконечно множество чисел Мерсена.

Определение .
- числа Ферма.

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

Ферма предположил (1650), что все числа такого вида будут простыми. Однако Эйлер показал (1739), что .

В настоящее время неизвестно, имеются ли другие простые числа Ферма при
.

С помощью чисел Ферма можно получить другое доказательство теоремы Эвклида.

Теорема (Пойа).

Любые два числа Ферма взаимно просты.

Доказательство . Пусть и
- произвольные числа Ферма.

Покажем, что
делится на . В самом деле, делится на х+1, т.е. на .

Пусть m - общий делитель и
. Тогда и так как
, значит,
. Но числа Ферма нечетные

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

Доказательство . каждое из
имеет нечетный делитель, который не делит остальные числа Ферма следовательно, есть по меньшей мере N простых нечетных чисел,
простых чисел бесконечно много.

Замечание . Простые числа Ферма неожиданно появляются в задаче о построении правильного N –угольника с помощью циркуля и линейки. Гаусс доказал, что построение возможно тогда и только тогда, когда
, где - простые числа Ферма.

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

Эйлер обратил внимание на многочлены:
, задающий простые числа при
и , принимающий простые значения при
.

Позднее была доказана следующая теорема.

Теорема (Гольдбах).

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

Доказательство . Пусть , пусть
- простое число.

Тогда по формуле Тейлора: .

Все коэффициенты
- целые числа
делится на р.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Если - простое, и делит , то делит или . Доказательство этого факта было дано Евклидом и известно как лемма Евклида . Оно используется в доказательстве основной теоремы арифметики .
• Кольцо вычетов является полем тогда и только тогда, когда - простое.
• Характеристика каждого поля - это ноль или простое число.
• Если - простое, а - натуральное, то делится на (малая теорема Ферма).
• Если - конечная группа с элементов, то содержит элемент порядка .
• Если - конечная группа, и - максимальная степень , которая делит , то имеет подгруппу порядка , называемую силовской подгруппой , более того, количество силовских подгрупп равно для некоторого целого (теоремы Силова).
• Натуральное является простым тогда и только тогда, когда делится на (теорема Вильсона).
• Если - натуральное, то существует простое , такое, что (постулат Бертрана).
• Ряд чисел, обратных к простым, расходится. Более того, при
• Любая арифметическая прогрессия вида , где - целые взаимно простые числа , содержит бесконечно много простых чисел (Теорема Дирихле о простых числах в арифметической прогрессии).
• Всякое простое число, большее 3, представимо в виде или , где - некоторое натуральное число. Отсюда, если разность между несколькими последовательными простыми числами (при k>1) одинакова, то она обязательно кратна 6 - например: 251-257-263-269; 199-211-223; 20183-20201-20219.
• Если - простое, то кратно 24 (справедливо также для всех нечётных чисел, не делящихся на 3) .
• Теорема Грина-Тао. Существуют сколь угодно длинные конечные арифметические прогрессии, состоящие из простых чисел .
• n >2, k >1. Иначе говоря, число, следующее за простым, не может быть квадратом или более высокой степенью с основанием, бо́льшим 2. Из этого следует также, что если простое число имеет вид , то k - простое (см. числа Мерсенна).
• Никакое простое число не может иметь вид , где n >1, k >0. Иначе говоря, число, предшествующее простому, не может быть кубом или более высокой нечётной степенью с основанием, бо́льшим 1 .

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

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

Распределение простых чисел p n = f (Δs n ); Δs n = p n +1 ² - p n ². Δp n = p n +1 - p n ; Δp n = 2, 4, 6, … .

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

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

Приложения

Вариации и обобщения

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

См. также

Примечания

Литература

• Гальперин Г. «Просто о простых числах» // Квант . - № 4. - С. 9-14,38.
• Нестеренко Ю. В. Алгоритмические проблемы теории чисел // Введение в криптографию / Под редакцией В. В. Ященко. - Питер, 2001. - 288 с. - ISBN 5-318-00443-1
• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии . - М .: МЦНМО , 2003. - 328 с. - ISBN 5-94057-103-4
• Черемушкин А. В. . - М .: МЦНМО , 2002. - 104 с. - ISBN 5-94057-060-7
• Кноп К. «В погоне за простотой»
• Кордемский Б. А. Математическая смекалка . - М .: ГИФМЛ, 1958. - 576 с.
• Генри С. Уоррен, мл. Глава 16. Формулы для простых чисел // Алгоритмические трюки для программистов = Hacker"s Delight. - М .: «Вильямс», 2007. - 288 с. - ISBN 0-201-91465-4
• Ю. Матиясевич. Формулы для простых чисел // Квант . - 1975. - № 5. - С. 5-13.
• Н. Карпушина. Палиндромы и «перевёртыши» среди простых чисел // Наука и жизнь . - 2010. - № 5.
• Д. Цагер. Первые 50 миллионов простых чисел // Успехи математических наук . - 1984. - Т. 39. - № 6(240). - С. 175–190.

Ссылки

• The Prime Pages (англ.) - база данных наибольших известных простых чисел
• PrimeGrid prime lists - все простые числа, найденные в рамках проекта PrimeGrid
• Геометрия простых и совершенных чисел (исп.)

Которое имеет только 2 разных натуральных делителя. Если сказать по-другому, число p тогда будет простым, когда оно больше единицы и может быть разделено лишь на единицу и на себя самого - p .

Натуральные числа, большие единицы и числа, которые не являются простыми, называют составными числами . Т.о., все натуральные числа делятся на 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, …

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

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

Самое большое известное простое число - это 2 57885161 - 1. Это число состоит из 17 425 170 десятичных цифр и называется простое число Мерсенна (M 57885161).

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

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

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

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

Когда p — простое, а a — натуральное, значит, a p -a можно поделить на p (малая теорема Ферма ).

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

Когда G — конечная группа, и p n — самая высокая степень p , делящая |G| , значит, у G есть подгруппа порядка p n , которая называется силовская подгруппа, кроме того, число силовских подгрупп соответствует pk+1 для некоего целого k (теоремы Силова).

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

Когда n > 1 — натуральное, значит, есть простое p : n < p < 2 n (постулат Бертрана ).

Ряд чисел, которые обратны к простым, расходится. Кроме того, при .

Всякая арифметическая прогрессия типа a, a + q, a + 2 q, a + 3 q, ... , где a, q > 1 — целые взаимно простые числа , содержит нескончаемое число простых чисел (Теорема Дирихле о простых числах в арифметической прогрессии ).

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

Когда p > 3 — простое число, значит, p 2 -1 делится на 24 (работает и на нечётных чисел, которые не делятся на три).

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

n k -1 , где n>2, k>1 . Другими словами, число, которое следует за простым, не может быть квадратом либо более высокой степенью с основанием, которое больше двух. Можно сделать вывод, что когда простое число представлено как 2 k -1 , значит k — простое.

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

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

Этот многочлен содержит 26 переменных, имеет 25. Самая низкая степень для известных многочленов представленного вида — пять при 42 переменных; самое маленькое количество переменных — десять при степени приблизительно 1,6·10 45 .

Действия с простыми числами.

1. Произведение простых чисел.

2. Разность простых чисел.

3. Сумма простых чисел.

4. Деление простых чисел.