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

Определение 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 можно записать в следующем виде

(3)

где 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, но это противоречит тому, что
.

Которое имеет только 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. Деление простых чисел.

Единица простое число? Нет, единица не является простым числом.

0 простое число? Нет, ноль не является простым числом.

2 простое число? Да, 2 простое число. 2 является единственным четным простым числом.

3 простое число? Да, 3 простое число.

5 простое число? Да, 5 простое число.

7 простое число? Да, 7 простое число.

9 простое число? Нет, 9 не является простым числом. Ведь 9 делится на себя, на единицу и на три.

11 простое число? Да, 11 простое число.

13 простое число? Да, 13 простое число.

15 простое число? Нет, 15 не является простым числом. Ведь 15 делится на себя, на единицу, на три, на пять.

17 простое число? Да, 17 простое число.

19 простое число? Да, 19 простое число.

20 простое число? Нет, 20 не является простым числом. Ведь 20 делится на себя, на единицу, на два, на четыре, на пять, на десять.

777 простое число? Нет, 777 не является простым числом. Ведь 777 делится на себя, на единицу, на 3, на 7, на 37.

997 простое число? Да, 997 простое число.

Простым числом является натуральное число, которое делится только на себя и на единицу.