Простые числа Ферма
Числа Ферма — числа вида 
. Изучение чисел такого вида начал Ферма, который выдвинул гипотезу, что все они простые. Однако, эта гипотеза была опровергнута Эйлером в 1732 году, нашедшим разложение числа F5 на простые делители:
Последовательность чисел Ферма начинается так (последовательность A000215 в OEIS):
Свойства
и поэтому 2 n + 1 не является простым.
Ссылки
Полезное
Смотреть что такое «Простые числа Ферма» в других словарях:
Простые числа — Простое число это натуральное число, которое имеет ровно 2 различных делителя (только 1 и самого себя). Все остальные числа, не равные единице, называются составными. Таким образом, все натуральные числа, за исключением единицы, разбиваются на… … Википедия
Ферма, Пьер — Пьер де Ферма Pierre de Fermat Дата рождения … Википедия
Простые множители — Простое число это натуральное число, которое имеет ровно 2 различных делителя (только 1 и самого себя). Все остальные числа, не равные единице, называются составными. Таким образом, все натуральные числа, за исключением единицы, разбиваются на… … Википедия
Ферма Пьер — Пьер Ферма Пьер де Ферма (фр. Pierre de Fermat, 1601 1665) французский математик, один из создателей аналитической геометрии, математического анализа, теории вероятностей и теории чисел. По профессии юрист, с 1631 года советник парламента в… … Википедия
Ферма П. — Пьер Ферма Пьер де Ферма (фр. Pierre de Fermat, 1601 1665) французский математик, один из создателей аналитической геометрии, математического анализа, теории вероятностей и теории чисел. По профессии юрист, с 1631 года советник парламента в… … Википедия
Ферма малая теорема — Малая теорема Ферма классическая теорема теории чисел, которая утверждает что Если p простое число и целое a не делится на p, то a p 1 ≡ 1 (mod p) (или a p 1 1 делится на p). Иная формулировка: Для любого простого … Википедия
Простые числа: история и факты
Свойства простых чисел впервые начали изучать математики Древней Греции. Математики пифагорейской школы (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 «Начал» Эвклид доказал, что простых чисел бесконечное количество. Это, кстати, один из первых примеров использования доказательства от противного. Также он доказывает Основную теорему арифметики – каждое целое число можно представить единственным образом в виде произведения простых чисел.
А затем случился большой перерыв в истории исследования простых чисел, связанный со Средними веками.
Следующие открытия были сделаны уже в начале 17-го века математиком Ферма. Он доказал гипотезу Альбера Жирара, что любое простое число вида 4n+1 можно записать уникальным образом в виде суммы двух квадратов, и также сформулировал теорему о том, что любое число можно представить в виде суммы четырёх квадратов.
Он разработал новый метод факторизации больших чисел, и продемонстрировал его на числе 2027651281 = 44021 × 46061. Также он доказал Малую теорему Ферма: если p – простое число, то для любого целого a будет верно a p = a modulo p.
Малая теорема Ферма послужила основой множества других результатов в теории чисел и методов проверки чисел на принадлежность к простым – многие из которых используются и по сей день.
Ферма много переписывался со своими современниками, в особенности с монахом по имени Марен Мерсенн. В одном из писем он высказал гипотезу о том, что числа вида 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 году.
Многие годы числа такого вида давали математикам наибольшие известные простые числа. Что число M19, было доказано Катальди в 1588 году, и в течение 200 лет было наибольшим известным простым числом, пока Эйлер не доказал, что M31 также простое. Этот рекорд продержался ещё сто лет, а затем Люкас показал, что M127 — простое (а это уже число из 39 цифр), и после него исследования продолжились уже с появлением компьютеров.
В 1952 была доказана простота чисел M521, M607, M1279, M2203 и M2281.
К 2005 году найдено 42 простых чисел Мерсенна. Наибольшее из них, M25964951, состоит из 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, как
А Гаусс – как логарифмический интеграл
с промежутком интегрирования от 2 до n.
Утверждение о плотности простых чисел 1/log(n) известно как Теорема о распределении простых чисел. Её пытались доказать в течение всего 19 века, а прогресса достигли Чебышёв и Риман. Они связали её с гипотезой Римана – по сию пору не доказанной гипотезой о распределении нулей дзета-функции Римана. Плотность простых чисел была одновременно доказана Адамаром и Валле-Пуссеном в 1896 году.
В теории простых чисел есть ещё множество нерешённых вопросов, некоторым из которых уже многие сотни лет:
Текущие рекорды среди простых чисел
Самое большое простое число, вычисленное проектом GIMPS [Great Internet Mersenne Prime Search], можно посмотреть в таблице на официальной странице проекта.
www.mersenne.org/primes
Самые большие близнецы среди простых чисел – это 2003663613 × 2 195000 ± 1. Они состоят из 58711 цифр, и были найдены в 2007 году.
Самое большое факториальное простое число (вида n! ± 1) – это 147855! — 1. Оно состоит из 142891 цифр и было найдено в 2002.
Наибольшее праймориальное простое число (число вида n# ± 1) – это 1098133# + 1.
Какой математик впервые доказал что среди чисел ферма не все числа являются простыми
Простые числа разбросаны в натуральном ряду очень прихотливым образом, и не удивительно, что издревле математики стремились найти «формулу для простых чисел». Такими формулами можно называть формулы, обладающие разными свойствами, и здесь очень важно понять, что нам требуется на самом деле.
Самая простая формула для простых чисел выглядит, так:
Формулы, кажущиеся очень простыми, на деле могут оказаться не лучше Именно к таким примерам мы сейчас и переходим.
Теорема Е. М. Райта
В 1947 году В. X. Миллс опубликовал следующий результат:
Существует вещественное число λ такое, что при любом число
Впоследствии появился ещё ряд формул такого же типа. Однако все это были результаты, формулировка которых выглядит заманчивой и многообещающей, но доказательство разочаровывает. Тому, кто хочет понять, почему это так, мы предлагаем разобраться в доказательстве следующей теоремы Е. М. Райта:
где берётся n возведений в степень, через a обратную функцию,
Попробуем выбрать число μ так, чтобы при
Согласно определению целой части числа эквивалентно неравенству
Прологарифмировав его n раз по получим ещё одно двойное неравенство,
| log 2 n q n ≤ μ 2 n ( q n + 1). | (6) |
Проверьте сами, что из (4) следует
Таким образом, последовательность
строго возрастает и ограничена сверху; следовательно, она имеет предел. мы и возьмём в качестве докажите, что так выбранное μ удовлетворяет даже более сильному, неравенству
| log 2 n q n 2 n ( q n + 1), | (7) |
и, следовательно, равенство (5) справедливо. Теорема Райта доказана.
Основным недостатком формул (2) и (3) является то, что они (точнее, их доказательства) не дают никакого способа находить новые простые числа, ибо чтобы вычислить простое число по нужно числа знать с достаточной точностью. Таким образом, в некотором смысле являются всего лишь замаскированными (и ухудшенными) вариантами Кроме того, вид на самом деле почти ничего не говорит именно о множестве простых чисел. Из доказательства теоремы Райта видно, что формулы, аналогичные можно указать для любого «достаточно густого» множества.
Недостатки формул (2) и (3) порождены тем, что в них входят вещественные числа задаваемые неким косвенным образом. В дальнейшем мы будем рассматривать лишь формулы, в которые входят только целочисленные коэффициенты. Такие формулы обладают важным преимуществом: они могут быть (в принципе) выписаны явно.
Простые числа Мерсенна и Ферма
Формулы Миллса, Райта и другие подобные формулы остались изолированными фактами, не приведшими к новым результатам. Однако в других случаях возможность представить некоторые простые числа в том или ином специальном виде имеет неожиданные и глубокие следствия.
Рассмотрим сейчас две формулы, имеющие совсем простой вид:
| p = 2 n 1, | (8) |
| p = 2 n + 1. | (9) |
Очевидно, что формула (8) не всегда даёт простые числа; например, если n составное число, то p делится на и на Но и при получающееся по число может оказаться составным:
2 11 1 = 2047 = 23 · 89.
Простые числа, получающиеся по формуле (8), называются числами Мерсенна в честь Марена Мерсенна, который ещё в 1664 году указал все простые не превосходящие 257, для которых, по его мнению, даёт простые числа. Однако Мерсенн не дал доказательства; впоследствии выяснилось, что его предсказание было частично ошибочным.
Интерес к числам Мерсенна вызван их связью с так называемыми совершенными числами числами, равными сумме всех своих делителей, отличных, конечно, от самого числа. Ещё Евклид доказал (докажите и вы), что если простое имеет вид, указанный в то число является совершенным. Например,
простые числа, и соответственно
| 6 = | (3 · 4)/2 = 1 + 2 + 3, |
| 28 = | (7 · 8)/2 = 1 + 2 + 4 + 7 + 14 |
Скатерть Улама
Формулы (8) и (9) содержат возведение в степень. А нельзя ли для задания бесконечно многих простых чисел обойтись лишь сложением, вычитанием и умножением? Поищем ответ на этот вопрос.
Начнём с рассмотрения многочленов от одной переменной с натуральными коэффициентами; посмотрим, какие многочлены будут своими значениями иметь простые числа и в каком количестве.
Французский математик Лежандр (живший в XVIII веке) высказал гипотезу, что взаимно просты, то в арифметической прогрессии с первым и встречается бесконечно много простых чисел. Эта гипотеза была доказана лишь в немецким математиком Леженом Дирихле.
Перейдём теперь к квадратным многочленам. Среди них есть «рекордсмены», например, многочлен его изучал ещё Леонард Эйлер. Этот многочлен принимает простые значения при При его значение составное.
Доказано, что никакой многочлен (отличный, разумеется, от константы) не может иметь в качестве значений только простые числа, но до сих пор не известно, существует ли многочлен (кроме линейного), среди значений которого встречается бесконечно много простых чисел.
| 197 | 196 | 195 | 194 | 193 | 192 | 191 | 190 | 189 | 188 | 187 | 186 | 185 | 184 | 183 |
| 198 | 145 | 144 | 143 | 142 | 141 | 140 | 139 | 138 | 137 | 136 | 135 | 134 | 133 | 182 |
| 199 | 146 | 101 | 100 | 99 | 98 | 97 | 96 | 95 | 94 | 93 | 92 | 91 | 132 | 181 |
| 200 | 147 | 102 | 65 | 64 | 63 | 62 | 61 | 60 | 59 | 58 | 57 | 90 | 131 | 180 |
| 201 | 148 | 103 | 66 | 37 | 36 | 35 | 34 | 33 | 32 | 31 | 56 | 89 | 130 | 179 |
| 202 | 149 | 104 | 67 | 38 | 17 | 16 | 15 | 14 | 13 | 30 | 55 | 88 | 129 | 178 |
| 203 | 150 | 105 | 68 | 39 | 18 | 5 | 4 | 3 | 12 | 29 | 54 | 87 | 128 | 177 |
| 204 | 151 | 106 | 69 | 40 | 19 | 6 | 1 | 2 | 11 | 28 | 53 | 86 | 127 | 176 |
| 205 | 152 | 107 | 70 | 41 | 20 | 7 | 8 | 9 | 10 | 27 | 52 | 85 | 126 | 175 |
| 206 | 153 | 108 | 71 | 42 | 21 | 22 | 23 | 24 | 25 | 26 | 51 | 84 | 125 | 174 |
| 207 | 154 | 109 | 72 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 83 | 124 | 173 |
| 208 | 155 | 110 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 123 | 172 |
| 209 | 156 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 171 |
| 210 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 |
| 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |
Ещё более удивительным оказалось то, что закономерность эта наблюдалась и тогда, когда спираль была продолжена (с помощью компьютера) до больших чисел на рис. 2 светлыми точками отмечены простые числа на спирали из первых 10 000 чисел. Узор, изображённый на рис. 2, получил название « скатерть Улама ».
Чтобы отмеченная закономерность проявилась, не обязательно начинать спираль с единицы. Например, значения многочлена выстраиваются по диагоналям у спирали, начинающейся с (рис. 3).
| 57 | 56 | 55 | 54 | 53 |
| 58 | 45 | 44 | 43 | 52 |
| 59 | 46 | 41 | 42 | 51 |
| 60 | 47 | 48 | 49 | 50 |
| 61 | 62 | 63 | 64 | 65 |
Возможно, что читатели «Кванта», проявив изобретательность и должное терпение, смогут найти новые красивые «геометрические» закономерности расположения простых чисел среди множества всех чисел.
Феномен со стремлением простых чисел располагаться в цепочки вдоль диагоналей был обнаружен сравнительно недавно и ещё не получил математического объяснения.
О представлении простых чисел с помощью многочленов от многих переменных мы скажем в конце статьи.
Экспоненциальный многочлен
Экспоненциальные многочлены отличаются от обычных тем, что в них показателями степени могут быть не только конкретные натуральные числа, но и линейные многочлены от переменных с натуральными коэффициентами, то есть многочлены вида
Простейшими примерами экспоненциальных многочленов от являются правые части
В дальнейшем мы всегда будем предполагать, что все встречающиеся у нас переменные принимают целые положительные значения.
В 1952 году американский математик Джулия Робинсон 6 опубликовала следующий замечательный результат:
В результате получается такая «формула для простых чисел»:
Доказательство Джулии Робинсон совершенно элементарно. Ниже излагаются его основные идеи; доведение же доказательства до формальной строгости мы оставляем читателям: все промежуточные результаты сформулированы в виде пяти лемм, и нужно доказать. Как мы увидим, из этих лемм следует не только существование экспоненциального но и его явный вид.
Что мы должны сделать?
Чтобы доказать теорему Джулии Робинсон, мы, очевидно, должны указать экспоненциальный такой, что разрешимо в натуральных числах относительно переменных тогда и только тогда, когда выполнено следующее условие:
Приведём ещё несколько примеров условий на набор переменных
Если мы потребуем, чтобы набор чисел (11) удовлетворял системе уравнений вида
Мы не станем точно определять, условия какого вида являются для нас допустимыми. Приведённое описание примеров условий достаточно для оправдания того способа действий, которым мы в дальнейшем будем пользоваться.
Примером эквивалентных условий относительно могут служить неравенство
Ясно, что каждое из этих условий имеет решение тогда и только тогда, когда принадлежит множеству чисел, не являющихся целыми степенями числа 2.
В этой терминологии наша цель формулируется так: найти экспоненциальный многочлен такой, что условие (10) эквивалентно условию (11) относительно параметра p.
Однако требование, чтобы параметр p стоял только в левой части является, как мы сейчас увидим, излишне жёстким.
эквивалентно условию (11).
Нам достаточно даже найти не уравнение, а хотя бы систему экспоненциально диофантовых уравнений
эквивалентную условию (11)
то система (14) эквивалентна уравнению (12).
Именно поиском системы экспоненциально диофантовых уравнений, эквивалентной мы и будем заниматься.
Что такое простое число?
«Странный вопрос, удивится читатель. Каждый знает, что простое число это число, большее единицы, которое делится только на единицу и на себя». Конечно, это так, но с таким определением работать нелегко ведь оно предполагает, что проверка простоты числа состоит в переборе бесконечного числа потенциальных делителей всех натуральных чисел, и самого числа. Лучше сказать так: является простым, если не делится ни на какое число, и отличное Для наших же целей больше подходит следующее определение: является простым, если и для любого 8
В этом определении нет ограничения и, что более важно, оно позволяет переменное число условий свести в одно условие:
Сделанное замечание позволяет нам написать первую систему условий, эквивалентную относительно
Первое из этих условий имеет искомый вид экспоненциально диофантова (более того, диофантова) уравнения, а третье легко приводится к такому же виду за счёт введения двух новых неизвестных:
| x 1 · s x 2 · p = 1. | (18) |
Так как уравнение (18) экспоненциально диофантово, то нам осталось лишь найти систему экспоненциально диофантовых уравнений, эквивалентную относительно параметров r и s условию (16).
Как вычислить факториал?
Многочлен, стоящий в числителе, имеет довольно сложную структуру. Попытаемся заменить его более простым а именно, При имеем:
Итак, нам осталось «избавиться» от биномиального коэффициента.
Биномиальные коэффициенты
и, таким образом, если
Здесь все условия уже имеют необходимый нам вид.
Дальнейшие шаги
Формула (10) не содержит явно номера задаваемого ею простого числа. Описанный выше способ построения экспоненциального не даёт прямого пути для включения номера простого числа в Используя существенно более сложную технику, Мартин Дейвис, Хилэри Патнам и Джулия Робинсон в 1961 году доказали одну очень сильную теорему, которая имеет такое следствие.
Существует экспоненциальный многочлен такой, что при каждом фиксированном значении и произвольных значениях остальных переменных, принимает ровно одно положительное значение, и этим значением является простое число.
В 1970 году автору этой статьи удалось, используя другие результаты Джулии Робинсон, построить такое диофантово уравнение:
которое разрешимо тогда и только тогда, когда параметры связаны соотношением Этот результат позволяет опустить в формулировке предыдущей теоремы слово «экспоненциальный», то есть позволяет построить многочлен, задающий простые числа. Об этом, однако, мы поговорим в другой раз. Те же читатели, кого заинтересовала подобная тематика и кого не страшат трудности, могут попробовать самостоятельно разобраться в статье автора «Диофантовы множества», опубликованной в журнале «Успехи математических наук», т. XXVII, № 5, 1972 год.
Темы для размышлений
Докажите, что в арифметических прогрессиях и бесконечно много простых чисел.
Каково множество тех многочленов, значения которых лежат вдоль диагонали, если спираль
Теорема Вильсона утверждает, что если p простое число, то делится Как можно использовать этот результат, чтобы уменьшить число неизвестных в экспоненциальном задающем простые числа?
Постройте экспоненциальный многочлен такой, что
если q простое число, то существуют числа такие, что
если q простое число и то простое число, следующее
если q не является простым числом, то всегда
Этот экспоненциальный многочлен даёт « формулу для следующего простого числа ».
Примечания
| 1. |
| 2. |
