Теоремы о простых числах
Теорема о существовании бесконечного числа простых чисел
Простых чисел бесконечно много.
Теорема о расходимости ряда [math]\sum_<>^<>1/n[/math]
Ряд [math]\sum_<>^<>1/n[/math] расходится.
Заметим для некоторого [math]k[/math] : [math]\sum_
^<><(1 + \frac
+ \frac + \cdots)> \ge \sum_ \frac[/math] . Теперь, пользуясь выражением [math] \ln(1+x) \approx x + o(x) [/math] и логарифмируя, выводим: [math] \sum_
<\ln(1 + \frac
+ \frac + \cdots)> \approx \sum_
< (\frac
+ \frac + \cdots)> \le \frac [/math] — расходится.
Теорема о расходимости ряда [math]\sum_<>^<>1/p[/math]
Ряд [math]\sum_<>^<>1/p[/math] , где [math]p[/math] — простое, расходится.
Работая в условиях предыдущей теоремы, продолжаем: [math] \ln(1+x) \le x[/math] , тогда [math] \sum_<>^<> <\ln(1 + \frac
+ \cdots)> \le \sum_<>^<> <( \frac
+ \frac + \cdots)>[/math] .
Как доказать что число простое
Натуральное число, большее 1 , называется простым, если оно ни на что не делится, кроме себя и 1 .
Другими словами, n > 1 – простое, если при его делении на любое число кроме 1 и n есть остаток.
Например, 5 это простое число, оно не может быть разделено без остатка на 2 , 3 и 4 .
Напишите код, который выводит все простые числа из интервала от 2 до n .
Для n = 10 результат должен быть 2,3,5,7 .
P.S. Код также должен легко модифицироваться для любых других интервалов.
Существует множество алгоритмов решения этой задачи.
Давайте воспользуемся вложенными циклами:
Для всех i от 1 до 10
Решение с использованием метки:
Как доказать что число простое
Наиболее наивный подход к поиску простых чисел заключается в следующем. Будем брать по очереди натуральные числа n , начиная с двойки, и проверять их на простоту. Проверка на простоту заключается в следующем: перебирая числа k из диапазона от 2 до n − 1 , будем делить n на k с остатком. Если при каком-то k обнаружится нулевой остаток, значит, n делится на k нацело, и число n составное. Если же при делении обнаруживались только ненулевые остатки, значит, число простое; в этом случае выводим его на экран. Ясно, что, получив нулевой остаток (тем самым обнаружив, что n составное), следует отказаться от дальнейших проб на делимость.
Заметим, что все простые числа, за исключением двойки, нечётные. Если обработать особо случай n = 2 , то все последующие числа n можно перебирать с шагом 2 . Это даст приблизительно двукратное увеличение производительности программы.
Оптимизированный перебор делителей
Ещё одно улучшение возникает благодаря следующему утверждению: наименьший делитель составного числа n не превосходит n . Докажем это утверждение от противного. Пускай число k является наименьшим делителем n , причём k > n . Тогда n = k l , где l ∈ ℕ , причём l ⩽ n , то есть l также является делителем числа n , кроме того, меньшим, чем k , а это противоречит предположению. Всё это означает, что, перебирая потенциальные делители, можно оборвать перебор, когда k достигнет n : если до этого момента делителей не найдено, то их нет вообще. Кстати, при проверке на простоту числа 11 это наблюдение позволяет сократить перебор более чем в три раза, а для числа 1111111111111111111 — более чем в 1054092553 раза (оба числа — простые).
Перебор с запоминанием найденных простых чисел
Существенно сократить перебор возможных делителей можно, пожертвовав памятью во время исполнения программы. В основе этой оптимизации лежит следующее утверждение: наименьший собственный делитель k составного числа n (то есть отличный от единицы и от самого n ) является простым. Докажите самостоятельно.
Поскольку при проверке числа n на простоту важен именно наименьший собственный делитель, делители следует искать среди простых чисел, перебирая их по порядку. Но где взять их список? Ответ прост: поскольку наша программа будет искать все простые числа по порядку, кроме вывода на экран будем добавлять их в список найденных простых. Для очередного n будем перебирать потенциальные делители только из этого списка, по-прежнему, вплоть до n .
Издержкой этого подхода является необходимость держать в памяти растущий список найденных простых чисел. Однако объём требуемой для этого памяти будет невелик по сравнению с громадным выигрышем в быстродействии. Следующая таблица даёт представление об экономии при переборе и о затратах памяти:
| n | количество k ⩽ n | количество простых k ⩽ n |
|---|---|---|
| 10 | 3 | 1 |
| 100 | 10 | 4 |
| 1000 | 31 | 10 |
| 10000 | 100 | 25 |
| 100000 | 316 | 65 |
| 1000000 | 1000 | 168 |
Решето Эратосфена
Другой алгоритм поиска простых чисел приписывают древнегреческому учёному Эратосфену Киренскому (Έρατοσθένης).
Обратите внимание: количество зачёркиваний у составного числа — это количество простых делителей (без учёта кратности).
Колёсный метод
Трюк, упомянутый в разделе «Наивный перебор», позволяет вдвое сократить список кандидатов в простые числа — заведомо составными будут все чётные числа кроме двойки. Посмотрим, нельзя ли подобным образом учесть ещё несколько первых простых чисел, чтобы дополнительно уменьшить число кандидатов.
Чисел, делящихся на 2 — половина, а делящихся на 3 — треть. Значит, доля чисел, делящихся хотя бы на одно из этих чисел, равна 1 2 + 1 3 − 1 2 ⋅ 1 3 = 2 3 (вычитается доля чисел, делящихся и на 2 , и на 3 , иначе такие числа будут учтены дважды). Для интересной операции, которую мы только что выполнили над дробями 1 2 и 1 3 , введём обозначение: x ⊕ y = x + y − x y .
Очевидно, операция ⊕ коммутативна: x ⊕ y = y ⊕ x . Кроме того, как нетрудно проверить, она ассоциативна: x ⊕ y ⊕ z = x ⊕ y ⊕ z .
Теперь ясно, что учёт следующего простого числа, пятёрки, увеличивает долю заведомо составных чисел (делящихся на 2 , 3 , 5 ) до 1 2 ⊕ 1 3 ⊕ 1 5 = 11 15 . Учёт семёрки даст 1 2 ⊕ 1 3 ⊕ 1 5 ⊕ 1 7 = 11 15 ⊕ 1 7 = 27 35 . Интересно выяснить, какую выгоду можно получить, учитывая следующие простые числа, и каковы будут издержки.
Мы вычислили «суммы» обратных величин для первых k простых чисел и свели результаты в таблицу:
| k | 1 2 ⊕ 1 3 ⊕ 1 5 ⊕ … ⊕ 1 p k |
|---|---|
| 1 | 0,5000… |
| 2 | 0,6667… |
| 3 | 0,7333… |
| 4 | 0,7714… |
| 5 | 0,7922… |
| 6 | 0,8082… |
| 7 | 0,8195… |
| 8 | 0,8290… |
| 9 | 0,8364… |
| 10 | 0,8421… |
Числа в правой колонке таблицы растут, но всё медленней.
Список чисел от 1 до P k , взаимно простых с P k , назовём колесом, а сами такие числа — спицами в колесе. Теперь мы знаем, что любое из простых чисел либо одно из p 1 , p 2 , … , p k , либо содержится среди чисел вида s + n P k , где s — спица. Все остальные натуральные числа, кроме единицы, заведомо составные, и их доля, как показывает таблица, довольно велика даже для небольших k .
Для проверки числа N на простоту следует прежде всего поискать N среди чисел p 1 , p 2 , … , p k . Если поиск не увенчался успехом, проверяем по очереди, не делится ли N на одно из p i . Если делится, число N — составное. Если же нет, ищем делители N среди спиц колеса s (пропустив, естественно, единицу), затем среди чисел вида s + P k , затем среди чисел вида s + 2 P k , затем — s + 3 P k , и так продолжаем до тех пор, пока квадрат очередного делителя не превысит N .
Построим колёса для первого одного простого числа, первых двух и первых трёх:
| k | колесо |
|---|---|
| 1 | 1 |
| 2 | 1 , 5 |
| 3 | 1 , 7 , 11 , 13 , 17 , 19 , 23 , 29 |
| 4 | 1 , 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 , 121 , 127 , 131 , 137 , 139 , 143 , 149 , 151 , 157 , 163 , 167 , 169 , 173 , 179 , 181 , 187 , 191 , 193 , 197 , 199 , 209 |
Возьмём для примера колесо, построенное для двух первых простых чисел — 2 и 3 . Проверяя на простоту число N при помощи такого колеса, убедившись, что N не двойка и не тройка, пытаемся делить это число сначала на 2 , 3 , а затем — на 5 , 7 , 11 , 13 , 17 , 19 , 23 , 25 , 29 , … , то есть на числа из арифметических прогрессий 1 + 6 t и 5 + 6 t , t = 0 1 2 3 … . При N = 661 имеет смысл остановиться на числе 25 , поскольку квадрат следующего в списке, 29 , уже больше 661 . Теперь можно заключить, что число 661 — простое.
Удобно изображать список возможных делителей в виде таблицы шириной P k (в нашем примере это 2 ⋅ 3 = 6 ): 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 … Серые числа заведомо составные. Среди цветных чисел также могут встретиться, хоть и редко, составные числа (синие) — мы помним, что колёсный метод исключает не все составные числа из рассмотрения.
Для проверки того же числа 661 на колесе, построенном для трёх первых простых чисел, нужно проверить его делимость сначала на 2 , 3 , 5 , затем — на 7 , 11 , 13 , 17 , 19 , 23 .
Есть соблазн использовать для построения колеса как можно больше первых простых чисел. Но не стоит этого делать. Выигрыш с добавлением очередного простого числа будет всё меньше и меньше, а количество спиц в k -ом колесе будет расти всё быстрее и быстрее. Можно показать, что количество спиц в k -ом колесе равно p 1 − 1 p 2 − 1 p 3 − 1 ⋅ … ⋅ p k − 1 . Эта последовательность выглядит так: 1 , 2 , 8 , 48 , 480 , 5760 , 92160 , 1658880 , … . Слишком большие колёса только замедлят выполнение программы, к тому же создание списка спиц потребует массу времени. Наши эксперименты показали, что оптимальное количество простых, используемых для построения колеса, равно четырём.
Ах, да. Почему метод называется колёсным? Возьмём колесо со спицами, пронумерованными от 1 до P k , и удалим спицы с номерами, не взаимно простыми с P k . Если прокатить такое колесо по прямой, отмечая следы концов уцелевших спиц, на прямой останутся отметки, принадлежащие арифметическим прогрессиям вида s + P k t . Первые три колеса показаны на рисунке 14.1. «Колёса для проверки чисел на простоту». Следующее колесо уже в семь раз больше самого крупного из показанных, и мы решили воздержаться от его рисования.
Как доказать что число простое
Определение. Число р О N , р № 1, называется простым, если р имеет в точности два положительных делителя: 1 и р . Остальные натуральные числа (кроме 1) принято называть составными. Число 1 — на особом положении, по договору, оно ни простое, ни составное.
Как это часто бывает в математике, да и в других науках, прилагательным «простой» называется объект только первоначально казавшийся простым. Простые числа, как выяснилось в процессе накопления научных знаний, появляются в различных областях математики и являются одним из самых загадочных и тяжелых для изучения монстров. Любопытного читателя, любителя ужастиков и лихо закрученных сюжетов, я отсылаю здесь к изумительному рассказу математика из Боннского университета Дон Цагира «Первые пятьдесят миллионов простых чисел», опубликованному в книжке «Живые числа», М.: Мир, 1985 г.
Отметим некоторые несложные наблюдения, связанные с простыми числами.
Наблюдение 1. Наименьший делитель любого числа а О N , отличный от 1, есть число простое.
Доказательство. Пусть с | а , с № 1 и с — наименьшее с этим свойством. Если существует с 1 такое, что с 1 | с , то с 1 Ј с и с 1 | а , следовательно, с 1 = с или с 1 = 1.
Наблюдение 2. Наименьший отличный от 1 делитель составного числа а О N не превосходит Ц a .
Доказательство. с | а , с № 1, с — наименьший, следовательно
а = са 1 , а 1 | а , а 1 і с , значит аа 1 і с 2 а 1 , а і с 2 и с Ј Ц a .
Следующее наблюдение, отдавая дань уважения его автору — Евклиду, назовем теоремой.
Теорема (Евклид). Простых чисел бесконечно много.
Доказательство. От противного. Ну пусть р 1 , р 2 . р n — все простые, какие только есть. Рассмотрим число а = р 1 р 2 . р n + 1. Его наименьший отличный от 1 делитель с , будучи простым, не может совпадать ни с одним из р 1 , р 2 . р n , так как иначе с | 1. Не перестаю удивляться изобретательности ума людей тысячелетней древности!
Для составления таблицы простых чисел древний грек Эратосфен придумал процедуру, которая получила название «решето Эратосфена»:
2, 3, 4 , 5, 6 , 7, 8 , 9 , 10 , 11, 12 , 13, 14 , 15 , 16 , 17.
Идем по натуральному ряду слева направо. Подчеркиваем первое неподчеркнутое и невычеркнутое число, а из дальнейшего ряда вычеркиваем кратные только что подчеркнутому. И так много раз. Легко понять, что подчеркнутые числа — простые. Если вспомнить наблюдение 2, то становится понятно, что когда вычеркнуты все кратные простых, меньших р , то оставшиеся невычеркнутые, меньшие р 2 — простые. Это значит, что составление таблицы всех простых чисел меньших N закончено сразу, как только вычеркнуты все кратные простых, меньших Ц a .
Для чисел, растущих закономерно, например для квадратов или степеней двойки, было бы, конечно, нелепо разыскивать экземпляр, превосходящий все известные. Для простых же чисел, напротив, прилагаются громадные усилия, чтобы именно это и сделать. Чудаки люди! Например, в 1876 году француз Люка доказал, что число 2 127 — простое, и 75 лет оно оставалось наибольшим из известных простых чисел, что не покажется удивительным, если на него взглянуть:
2 127 -1 = 170141183460469231731687303715884105727.
В настоящее время составлены таблицы всех простых чисел, не превосходящих 50 миллионов, далее известны только отдельные их представители. Читателей всегда привлекает гигантизм, поэтому укажу здесь два самых больших известных на сегодняшний момент простых числа: 2 44497 — 1 и 2 86243 — 1. Последнее число записано пока в книгу рекордов Гиннеса, в нем 25962 десятичных знака. Найдено оно было, конечно, в рекламных целях — демонстрация фирмой IBM возможностей очередного суперкомпьютера, которому для проверки этого числа на простоту с помощью специальных изощренных тестов (пригодных только для чисел вида 2 n- 1) потребовалась неделя работы и куча денег. И это трата денег происходит в то время, когда у нас в России более трети населения живет за чертой бедности, а половина детей в Уганде не умеют ни читать, ни писать, а только сидят и гундят!
Самой важной и общеизвестной в этом пункте является следующая теорема (искушенные алгебраисты скажут, что она утверждает факториальность кольца Z , а я воздержусь от каких-либо комментариев в адрес этой теоремы, ибо про столь важную персону математического мира надо либо долго говорить, либо почтенно молчать). Эта теорема носит название «Основной теоремы арифметики».
Теорема. Всякое целое число, отличное от — 1, 0 и 1, единственным образом (с точностью до порядка сомножителей) разложимо в произведение простых чисел.
Доказательство. Будем доказывать утверждение теоремы только для натуральных чисел, ибо знак минус перед числом умеют ставить все умеющие ставить знак минус.
Пусть а > 1, р 1 — его наименьший простой делитель. Значит,
а = р 1 а 1 . Если, далее, а 1 > 1, то пусть р 2 — его наименьший простой делитель и а 1 = р 2 а 2 , т.е. а = р 1 р 2 а 2 , и так далее, пока а n не станет равным единице. Это обязательно произойдет, так как а > а 1 > а 2 . а натуральные числа с естественным порядком удовлетворяют условию обрыва убывающих цепей (во как выразился!). Имеем, таким образом,
a = p 1 p 2 . p n , и возможность разложения доказана.
Покажем единственность. Ну пусть a = q 1 q 2 . q n — другое разложение, т.е. p 1 p 2 . p n = q 1 q 2 . q s . В последнем равенстве правая часть делится на q 1 , следовательно, левая часть делится на q 1 . Покажем, что если произведение p 1 p 2 . p n делится на q 1 , то один из сомножителей р k обязан делиться на q 1 .
Действительно, если q 1 | p 1 , то все доказано. Пусть q 1 не делит p 1 . Так как q 1 — простое число, то ( q 1 , p 1 ) = 1. Значит найдутся такие
u , v О Z , что up 1 + vq 1 = 1. Умножим последнее равенство на p 2 . p n , получим: p 2 . p n = p 1 ( p 2 . p n ) u + q 1 ( p 2 . p n ) v . Оба слагаемых справа делятся на q 1 , следовательно, p 2 . p n делится на q 1 . Далее рассуждайте по индукции сами.
Теперь пусть, например, q 1 | p 1 . Значит q 1 = p 1 , так как p 1 — простое. Из равенства p 1 p 2 . p n = q 1 q 2 . q s банальным сокращением моментально получим равенство p 2 . p n = q 2 . q s . Снова рассуждая по индукции, видим, что n = s , и каждый сомножитель левой части равенства p 1 p 2 . p n = q 1 q 2 . q n обязательно присутствует в правой и наоборот.
Сразу отмечу без доказательства два достаточно очевидных следствия из этой теоремы.
Следствие 1. Всякое рациональное число однозначно представимо в виде
| p | a 1 1 | p | a 2 2 | . p | a k k | , |
где a 1 , a 2 . a k О Z .
Следствие 2. Если
| a = p | a 1 1 | p | a 2 2 | . p | a n n | , | b = p | b 1 1 | p | b 2 2 | . p | b n n |
— целые числа, то наибольший общий делитель a и b равен
| p | g 1 1 | p | g 2 2 | . p | g n n | , |
а наименьшее общее кратное a и b равно
| p | d 1 1 | p | d 2 2 | . p | d n n | , |
где g i = min < a i , b i >, a d i = max < a i , b i >.
Можно очень долго анализировать, какие такие глубинные причины вызывают к жизни «основную теорему» арифметики, однако такой анализ, боюсь, уведет нас слишком далеко за пределы основных понятий арифметики. Отмечу только, что для справедливости обсуждаемой теоремы просто необходима аддитивная структура кольца целых чисел. Поясню необходимость наличия сложения плохим примером.
Плохой пример. Пусть S = — множество вот таких вот целых чисел. Легко проверить, что S замкнуто относительно умножения:
(4 k 1 + 1)·(4 k 2 + 1) = 16 k 1 k 2 + 4 k 2 + 4 k 1 + 1 = 4·(4 k 1 k 2 + k 1 + k 2 ) + 1 О S ,
однако это множество не замкнуто относительно сложения. «Квазипростые» числа из S — суть далее неразложимые в произведение чисел из S : 5, 9, 13, 17, 21, 49. Индуктивным рассуждением, подобным рассуждению в первой части доказательства основной теоремы арифметики, легко убедиться, что всякое число из S разложимо в произведение «квазипростых». Однако единственность такого разложения отсутствует: 441 = 21·21 = 9·49, при этом 9 не делит 21, и 49 не делит 21. Вот какой плохой пример.
1 . Простое число — это число, имеющее в точности два различных положительных делителя (единицу и себя). Найдите все натуральные числа, имеющие в точности
а) три различных положительных делителя;
б) четыре различных положительных делителя;
в) k штук различных положительных делителей ( k > 4).
2 . Опоссум Порфирий в зоопарке раскладывает на простые множители число 81 057 226 635 000. Помогите ему, не то он обидится.
3 . Методом Эратосфена составьте таблицу простых чисел, меньших 100.
4 . Докажите, что среди членов каждой из арифметических прогрессий:
б) 5, 11, 17, 23, 29.
в) 11, 21, 31, 41, 51.
имеется бесконечно много простых чисел. *
5 . Докажите, что в натуральном ряде имеются сколь угодно длинные промежутки вида < n , n +1, n +2, …, n + k >, не содержащие простых чисел.
6 . Докажите, что не существует такого многочлена f ( x ) = a 0 x n + a 1 x n -1 +…+ a n -1 x + a n с целыми коэффициентами, что все числа f (0), f (1), f (2), f (3), … являются простыми. **
* Оказывается, справедлив такой общий факт: Если первый член и разность арифметической прогрессии взаимно просты, то среди ее членов содержится бесконечно много простых чисел. Более того, ряд, составленный из обратных величин к этим простым числам, расходится. Это классическое утверждение называется теоремой Дирихле и доказывается весьма сложно. В 1950 году датский математик А. Сельберг придумал чрезвычайно сложное и хитроумное элементарное (не использующее аппарат высшей математики) доказательство теоремы Дирихле, однако жить лучше от этого не стало и даже сильно одаренному школьнику доказательство теоремы Дирихле вряд ли объяснишь.
** Абсолютно несложное доказательство этого факта впервые придумал Л. Эйлер. Он же напридумывал массу многочленов f ( x ), значения которых при многих последовательных натуральных x являются про-стыми числами. Два примера:
а) f ( x ) = x 2 + x +41, при x = 0, 1, 2, . , 39.
б) f ( x ) = x 2 -79 x +1601, при x = 0, 1, 2, . , 79.
Если же рассматривать многочлены от нескольких переменных, то, как следует из результатов Ю. В. Матиясевича о диофантовости рекурсивных множеств (опубликовано в 1970 году), существуют многочлены, множество положительных значений которых в точности является множеством всех простых чисел. Преследуя чисто спортивный интерес, укажу здесь один такой многочлен от 26 переменных:
F ( a , b , c , d , e , f , g , h , i , j , k , l , m , n , o , p , q , r , s , t , u , v , w , x , y , z ) =
= < k + 2> — ( a 2 y 2 — y 2 + 1 — x 2 ) 2 -(< e 4 + 2 e 3 > < a + 1>2 — o 2 ) 2 —
— (16 < k + 1>3 < k + 2> < n + 1>2 + 1 — f 2 ) 2 —
— (<( a + u 4 - u 2 a ) 2 - 1> < n + 4 dy >2 + 1 — < x + cu >2 ) 2 — ( ai + k + 1 — l — i ) 2 —
— (< gk + 2 g + k + 1> < h + j >+ h — z ) 2 — (16 r 2 y 4 < a 2 - 1>+ 1 — u 2 ) 2 —
— ( p — m + l < a - n - 1>+ b ) 2 —
— ( z — pm + pla — p 2 l + t ) 2 —
— ( q — x + y < a - p - 1>+ s ) 2 —
— ( a 2 l 2 — l 2 + 1 — m 2 ) 2 — ( n + l + v — y ) 2 >