В математике число Ферма , названное в честь Пьера де Ферма , который их первым изучил, является положительным целым числом вида
Названный в честь | Пьер де Ферма |
---|---|
Количество известных терминов | 5 |
Предполагаемый нет. условий | 5 |
подпоследовательности из | Числа Ферма |
Первые триместры | 3 , 5 , 17 , 257 , 65537 |
Самый большой известный термин | 65537 |
Индекс OEIS | A019434 |
где n - неотрицательное целое число. Первые несколько чисел Ферма:
- 3 , 5 , 17 , 257 , 65537 , 4294967297, 18446744073709551617, ... (последовательность A000215 в OEIS ).
Если 2 k + 1 простое число и k > 0, то k должно быть степенью двойки, поэтому 2 k + 1 является числом Ферма; такие простые числа называются простыми числами Ферма . По состоянию на 2021 год единственными известными простыми числами Ферма являются F 0 = 3, F 1 = 5, F 2 = 17, F 3 = 257 и F 4 = 65537 (последовательность A019434 в OEIS ); эвристика подсказывает, что их больше нет.
Основные свойства
Числа Ферма удовлетворяют следующим рекуррентным соотношениям :
для n ≥ 1,
при n ≥ 2. Каждое из этих соотношений можно доказать с помощью математической индукции . Из второго уравнения мы можем вывести теорему Гольдбаха (названную в честь Кристиана Гольдбаха ): никакие два числа Ферма не имеют общего целочисленного множителя больше 1 . Чтобы убедиться в этом, предположим, что 0 ≤ i < j и F i и F j имеют общий делитель a > 1. Тогда a делит оба
и F j ; следовательно, a делит их разность на 2. Так как a > 1, это вынуждает a = 2. Противоречие , потому что каждое число Ферма явно нечетное. В качестве следствия мы получаем еще одно доказательство бесконечности простых чисел: для каждого F n выбираем простой множитель p n ; тогда последовательность { p n } представляет собой бесконечную последовательность различных простых чисел.
Другие свойства
- Нет Ферма премьер может быть выражена как разность два р - й степеней, где р представляет собой нечетное простое число.
- За исключением F 0 и F 1 , последняя цифра числа Ферма - 7.
- Сумма обратных величин всех чисел Ферма (последовательность A051158 в OEIS ) является иррациональной . ( Соломон В. Голомб , 1963)
Простота чисел Ферма
Числа Ферма и простые числа Ферма были впервые изучены Пьером де Ферма, который предположил, что все числа Ферма простые. Действительно, легко показать , что первые пять чисел Ферма F 0 , ..., F 4 простые. Гипотеза Ферма была опровергнута Леонардом Эйлером в 1732 году, когда он показал, что
Эйлер доказал, что каждый множитель F n должен иметь вид k 2 n +1 + 1 (позже улучшенный до k 2 n +2 + 1 Люка ).
То, что 641 является фактором F 5, можно вывести из равенств 641 = 2 7 × 5 + 1 и 641 = 2 4 + 5 4 . Из первого равенства следует, что 2 7 × 5 −1 (mod 641) и, следовательно, (в четвертой степени), что 2 28 × 5 4 ≡ 1 (mod 641). С другой стороны, из второго равенства следует, что 5 4 ≡ −2 4 (mod 641). Из этих сравнений следует, что 2 32 ≡ −1 (mod 641).
Ферма, вероятно, знал о форме факторов, позже доказанных Эйлером, поэтому кажется любопытным, что он не смог выполнить прямые вычисления, чтобы найти фактор. [1] Одно из распространенных объяснений состоит в том, что Ферма допустил вычислительную ошибку.
Других известных простых чисел Ферма F n с n > 4 не существует, но мало что известно о числах Ферма для больших n . [2] Фактически, каждая из следующих проблем является открытой:
- Является ли F п композит для всех п > 4?
- Бесконечно много простых чисел Ферма? ( Эйзенштейн, 1844 г.) [3]
- Бесконечно много составных чисел Ферма?
- Существует ли число Ферма, не свободное от квадратов ?
По состоянию на 2014 г.[Обновить], известно, что F n составное для 5 ≤ n ≤ 32 , хотя из них полные факторизации F n известны только для 0 ≤ n ≤ 11 , и нет известных простых множителей для n = 20 и n = 24. . [4] Наибольшее известное составное число Ферма - F 18233954 , а его простой множитель 7 × 2 18233956 + 1 , мегапростое число , было обнаружено в октябре 2020 года.
Эвристические аргументы
Эвристика предполагает, что F 4 - последнее простое число Ферма.
Теорема простого числа , подразумевает , что случайное число в подходящем интервале вокруг N является простым с вероятностью 1 / Ln N . Если использовать эвристику, согласно которой число Ферма является простым с той же вероятностью, что и случайное целое число его размера, и что F 5 , ..., F 32 являются составными, то ожидаемое количество простых чисел Ферма, превышающих F 4 (или эквивалентно , за пределами F 32 ) должно быть
Это число можно интерпретировать как верхнюю границу вероятности того, что существует простое число Ферма, превышающее F 4 .
Этот аргумент не является строгим доказательством. Во-первых, предполагается, что числа Ферма ведут себя «случайным образом», но множители чисел Ферма обладают особыми свойствами. Боклан и Конвей опубликовали более точный анализ, предполагающий, что вероятность того, что существует еще одно простое число Ферма, меньше одного на миллиард. [5]
Эквивалентные условия первобытности
Позволять - n- е число Ферма. Тест Пепина утверждает, что при n > 0
- прост тогда и только тогда, когда
Выражение можно оценить по модулю путем повторного возведения в квадрат . Это делает тест быстрым алгоритмом с полиномиальным временем . Но числа Ферма растут так быстро, что лишь небольшую часть из них можно проверить в разумные сроки и в разумных пределах.
Есть несколько тестов для чисел вида k 2 m + 1, таких как множители чисел Ферма, на простоту.
- Теорема Прота (1878 г.). Позволять знак равно + со странным < . Если есть целое число такой, что
- тогда простое. И наоборот, если вышеуказанное сравнение не выполняется, и, кроме того,
- (См. Символ Якоби )
- тогда составной.
Если N = F n > 3, то указанный выше символ Якоби всегда равен −1 для a = 3, и этот частный случай теоремы Прота известен как тест Пепена . Хотя тест Пепина и теорема Прота были реализованы на компьютерах для доказательства составности некоторых чисел Ферма, ни один из тестов не дает конкретного нетривиального фактора. Фактически, нет никаких конкретных простых множителей для n = 20 и 24.
Факторизация чисел Ферма
Из-за размера чисел Ферма сложно разложить на множители или даже проверить простоту. Тест Пепена дает необходимое и достаточное условие простоты чисел Ферма и может быть реализован на современных компьютерах. Метод эллиптических кривых - это быстрый метод поиска малых простых делителей чисел. Проект распределенных вычислений Fermatsearch обнаружил некоторые факторы чисел Ферма. Программа proth.exe Ива Галло использовалась для нахождения множителей больших чисел Ферма. Эдуард Лукас , улучшив вышеупомянутый результат Эйлера, доказал в 1878 году, что каждый множитель числа Ферма, с n не менее 2, имеет вид(см. число Прота ), где k - натуральное число. Само по себе это позволяет легко доказать простоту известных простых чисел Ферма.
Факторизации первых двенадцати чисел Ферма:
F 0 знак равно 2 1 + 1 знак равно 3 простое F 1 знак равно 2 2 + 1 знак равно 5 простое F 2 знак равно 2 4 + 1 знак равно 17 - простое число П 3 знак равно 2 8 + 1 знак равно 257 - простое П 4 знак равно 2 16 + 1 знак равно 65 537 - это наибольшее известное простое число Ферма. П 5 знак равно 2 32 + 1 знак равно 4 294 967 297 знак равно 641 × 6 700 417 (1732 с полным факторингом [6] ) П 6 знак равно 2 64 + 1 знак равно 18,446,744,073,709,551,617 (20 цифр) знак равно 274,177 × 67,280,421,310,721 (14 цифр) (с учетом 1855 г.) П 7 знак равно 2 128 + 1 знак равно 340 282 366 920 938 463 463 374 607 431 768 211 457 (39 цифр) знак равно 59 649 589 127 497 217 (17 цифр) × 5 704 689 200 685 129 054 721 (22 цифры) (с учетом 1970) П 8 знак равно 2 256 + 1 знак равно 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,937
(78 цифр)знак равно 1,238,926,361,552,897 (16 цифр) ×
93,461,639,715,357,977,769,163,558,199,606,896,584,051,237,541,638,188,580,280,321 (62 цифры) (с учетом 1980)П 9 знак равно 2 512 + 1 знак равно 13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,592,393,377,723,561,443,721,764,0
30,073,546,976,801,874,298,166,903,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,6
49006084097 (155 цифр)знак равно 2,424,833 × 7,455,602,825,647,884,208,337,395,736,200,454,918,783,366,342,657 (49 цифр) ×
741,640,062,627,530,801,524,787,141,901,937,474,059,940,781,097,519,023,905,821,316,144,415,00,711,709,692
цифрП 10 знак равно 2 1024 + 1 знак равно 179,769,313,486,231,590,772,930 ... 304,835,356,329,624,224,137,217 (309 цифр) знак равно 45,592,577 × 6,487,031,809 × 4,659,775,785,220,018,543,264,560,743,076,778,192,897 (40 цифр) ×
130,439,874,405,488,189,727,484 ... 806,217,820,753,127,014,424,577 (252 цифры) (с учетом 1995)П 11 знак равно 2 2048 + 1 знак равно 32,317,006,071,311,007,300,714,8 ... 193,555,853,611,059,596,230,657 (617 цифр) знак равно 319,489 × 974849 × 167,988,556,341,760,475,137 (21 цифра) × 3,560,841,906,445,833,920,513 (22 цифры) ×
173,462,447,179,147,555,430,258 ...
По состоянию на 2018 год[Обновить], только F 0 - F 11 были полностью разложены на множители . [4] Проект распределенных вычислений Fermat Search занимается поиском новых множителей чисел Ферма. [7] Набор всех коэффициентов Ферма - A050922 (или, отсортированный, A023394 ) в OEIS .
Следующие факторы чисел Ферма были известны до 1950 года (с тех пор цифровые компьютеры помогли найти больше факторов):
Год | Finder | Число Ферма | Фактор |
---|---|---|---|
1732 г. | Эйлер | ||
1732 г. | Эйлер | (полностью учтено) | |
1855 г. | Clausen | ||
1855 г. | Clausen | (полностью учтено) | |
1877 г. | Первушин | ||
1878 г. | Первушин | ||
1886 г. | Зилхофф | ||
1899 г. | Каннингем | ||
1899 г. | Каннингем | ||
1903 г. | Западный | ||
1903 г. | Западный | ||
1903 г. | Западный | ||
1903 г. | Западный | ||
1903 г. | Каллен | ||
1906 г. | Morehead | ||
1925 г. | Крайчик |
По состоянию на январь 2021 г.[Обновить], Известно 356 простых множителей чисел Ферма, а 312 чисел Ферма - составные. [4] Каждый год обнаруживается несколько новых факторов Ферма. [8]
Псевдопримеры и числа Ферма
Подобно составным числам формы 2 p - 1, каждое составное число Ферма является сильным псевдопростым числом по основанию 2. Это связано с тем, что все сильные псевдопростые числа по основанию 2 также являются псевдопростыми числами Ферма, т.е.
для всех чисел Ферма.
В 1904 году Чиполла показал, что произведение по крайней мере двух различных простых или составных чисел Ферма будет псевдопростом Ферма по основанию 2 тогда и только тогда, когда . [9]
Другие теоремы о числах Ферма
Лемма. - Если n - целое положительное число,
Теорема - Если нечетное простое число, то это степень двойки.
Если является положительным целым числом, но не степенью двойки, оно должно иметь нечетный простой множитель , и мы можем написать где .
По предыдущей лемме для натурального числа ,
где означает «равномерно делит». Подстановка, а также и используя это странно,
и поэтому
Так как , следует, что не простое. Следовательно, по контрасту должно быть степенью 2.
Теорема - число Ферма простое число , не может быть простым Wieferich .
Мы показываем, если является простым числом Ферма (и, следовательно, по сказанному выше, m является степенью двойки), то сравнение не держит.
С мы можем написать . Если данное сравнение выполнено, то, и поэтому
Следовательно , и поэтому . Это ведет к, что невозможно, так как .
Теорема ( Эдуар Lucas ) - Любой простой делитель р из имеет форму всякий раз, когда n > 1.
Пусть G p обозначает группу ненулевых целых чисел по модулю p при умножении , которая имеет порядок p −1. Обратите внимание, что 2 (строго говоря, его образ по модулю p ) имеет мультипликативный порядок, равныйв G p (поскольку это квадрат который -1 по модулю Р п ), так что, по Лагранжа теоремы , р - 1 делится наи p имеет виддля некоторого целого k , как знал Эйлер . Эдуард Лукас пошел еще дальше. Поскольку n > 1, указанное выше простое число p сравнимо с 1 по модулю 8. Следовательно (как было известно Карлу Фридриху Гауссу ), 2 является квадратичным вычетом по модулю p , то есть существует целое число a такое, чтоТогда образ a имеет порядокв группе G p и (снова используя теорему Лагранжа) p - 1 делится наи p имеет виддля некоторого целого числа s .
Фактически, непосредственно видно, что 2 - квадратичный вычет по модулю p , поскольку
Поскольку нечетная степень 2 является квадратичным вычетом по модулю p , то же самое и само 2.
Связь с конструируемыми полигонами
Карл Фридрих Гаусс разработал теорию гауссовских периодов в своих Disquisitiones Arithmeticae и сформулировал достаточное условие конструктивности правильных многоугольников. Гаусс заявил, что это условие также необходимо , но не опубликовал доказательства. Пьер Ванцель дал полное доказательство необходимости в 1837 году. Результат известен как теорема Гаусса – Ванцеля :
- П односторонняя правильный многоугольник может быть построен с циркулем и линейкой тогда и только тогда , когда п является произведением мощности 2 -х и различных простых чисел Ферма: Другими словами, если и только если п имеет вид п = 2 к р 1 p 2 ... p s , где k, s - неотрицательные целые числа, а p i - различные простые числа Ферма.
Положительное целое число n имеет указанную выше форму тогда и только тогда, когда его значение φ ( n ) является степенью двойки.
Применения чисел Ферма
Генерация псевдослучайных чисел
Простые числа Ферма особенно полезны при генерации псевдослучайных последовательностей чисел в диапазоне 1 ... N , где N - степень числа 2. Наиболее распространенный метод - взять любое начальное значение от 1 до P - 1, где P является простым числом Ферма. Теперь умножьте это на число A , которое больше квадратного корня из P и является первообразным корнем по модулю P (т. Е. Не является квадратичным вычетом ). Затем возьмите результат по модулю P . Результат - новое значение для ГСЧ.
- (см. линейный конгруэнтный генератор , RANDU )
Это полезно в информатике, поскольку большинство структур данных имеют элементы с 2- кратными возможными значениями. Например, байт имеет 256 (2 8 ) возможных значений (0–255). Следовательно, для заполнения байта или байтов случайными значениями можно использовать генератор случайных чисел, который выдает значения 1–256, причем байт принимает выходное значение -1. По этой причине очень большие простые числа Ферма представляют особый интерес для шифрования данных. Этот метод выдает только псевдослучайные значения, так как после P - 1 повторений последовательность повторяется. Неправильно выбранный множитель может привести к тому, что последовательность будет повторяться раньше, чем P - 1.
Другие интересные факты
Число Ферма не может быть идеальным числом или частью пары дружественных чисел . ( Лука 2000 )
Серия обратных всех простых делителей чисел Ферма сходится . ( Кржижек, Лука и Сомер 2002 )
Если n n + 1 простое число, существует такое целое число m , что n = 2 2 m . В этом случае выполняется равенство n n + 1 = F (2 m + m ) . [10] [11]
Пусть наибольший простой делитель числа Ферма F n равен P ( F n ). Потом,
- ( Грычук, Лука и Войтович 2001 )
Обобщенные числа Ферма
Числа формы с a , b любыми взаимно простыми целыми числами, a > b > 0, называются обобщенными числами Ферма . Нечетное простое число p является обобщенным числом Ферма тогда и только тогда, когда p конгруэнтно 1 (mod 4) . (Здесь мы рассматриваем только случай n > 0, поэтому 3 = не контрпример.)
Пример вероятного простого числа этой формы - 124 65536 + 57 65536 (найдено Валерием Курышевым). [12]
По аналогии с обычными числами Ферма принято записывать обобщенные числа Ферма в виде как F n ( a ). В этой записи, например, число 100 000 001 будет записано как F 3 (10). В дальнейшем мы ограничимся простыми числами этого вида:такие простые числа называются «основанием простых чисел Ферма a ». Конечно, эти простые числа существуют только если это даже .
Если нам требуется n > 0, то четвертая проблема Ландау спрашивает, существует ли бесконечно много обобщенных простых чисел Ферма F n ( a ).
Обобщенные простые числа Ферма
Из-за простоты доказательства их простоты обобщенные простые числа Ферма в последние годы стали предметом исследований в области теории чисел. Многие из самых больших известных сегодня простых чисел являются обобщенными простыми числами Ферма.
Обобщенные числа Ферма могут быть простыми только для четных a , потому что если a нечетное, то каждое обобщенное число Ферма делится на 2. Наименьшее простое число с участием является , или 30 32 + 1. Кроме того, мы можем определить «полуобобщенное число Ферма» для нечетной базы, а полуобобщенное число Ферма для базы a (для нечетного a ) равно, и также следует ожидать, что будет только конечное число полуобобщенных простых чисел Ферма для каждой нечетной базы.
(В списке обобщенные числа Ферма () , Чтобы даже являются, для нечетного a они. Если a - совершенная степень с нечетным показателем (последовательность A070265 в OEIS ), то все обобщенные числа Ферма могут быть алгебраически разложены на множители , поэтому они не могут быть простыми)
(Для наименьшего числа такой, что является простым, см. OEIS : A253242 )
числа такой, что премьер | числа такой, что премьер | числа такой, что премьер | числа такой, что премьер | ||||
---|---|---|---|---|---|---|---|
2 | 0, 1, 2, 3, 4, ... | 18 | 0, ... | 34 | 2, ... | 50 | ... |
3 | 0, 1, 2, 4, 5, 6, ... | 19 | 1, ... | 35 год | 1, 2, 6, ... | 51 | 1, 3, 6, ... |
4 | 0, 1, 2, 3, ... | 20 | 1, 2, ... | 36 | 0, 1, ... | 52 | 0, ... |
5 | 0, 1, 2, ... | 21 год | 0, 2, 5, ... | 37 | 0, ... | 53 | 3, ... |
6 | 0, 1, 2, ... | 22 | 0, ... | 38 | ... | 54 | 1, 2, 5, ... |
7 | 2, ... | 23 | 2, ... | 39 | 1, 2, ... | 55 | ... |
8 | (никто) | 24 | 1, 2, ... | 40 | 0, 1, ... | 56 | 1, 2, ... |
9 | 0, 1, 3, 4, 5, ... | 25 | 0, 1, ... | 41 год | 4, ... | 57 | 0, 2, ... |
10 | 0, 1, ... | 26 год | 1, ... | 42 | 0, ... | 58 | 0, ... |
11 | 1, 2, ... | 27 | (никто) | 43 год | 3, ... | 59 | 1, ... |
12 | 0, ... | 28 год | 0, 2, ... | 44 год | 4, ... | 60 | 0, ... |
13 | 0, 2, 3, ... | 29 | 1, 2, 4, ... | 45 | 0, 1, ... | 61 | 0, 1, 2, ... |
14 | 1, ... | 30 | 0, 5, ... | 46 | 0, 2, 9, ... | 62 | ... |
15 | 1, ... | 31 год | ... | 47 | 3, ... | 63 | ... |
16 | 0, 1, 2, ... | 32 | (никто) | 48 | 2, ... | 64 | (никто) |
17 | 2, ... | 33 | 0, 3, ... | 49 | 1, ... | 65 | 1, 2, 5, ... |
б | известная обобщенная (половина) база простых чисел Ферма b |
2 | 3, 5, 17, 257, 65537 |
3 | 2, 5, 41, 21523361, 926510094425921, 1716841910146256242328924544641 |
4 | 5, 17, 257, 65537 |
5 | 3, 13, 313 |
6 | 7, 37, 1297 |
7 | 1201 |
8 | (невозможно) |
9 | 5, 41, 21523361, 926510094425921, 1716841910146256242328924544641 |
10 | 11, 101 |
11 | 61, 7321 |
12 | 13 |
13 | 7, 14281, 407865361 |
14 | 197 |
15 | 113 |
16 | 17, 257, 65537 |
17 | 41761 |
18 | 19 |
19 | 181 |
20 | 401, 160001 |
21 год | 11, 97241, 1023263388750334684164671319051311082339521 |
22 | 23 |
23 | 139921 |
24 | 577, 331777 |
25 | 13, 313 |
26 год | 677 |
27 | (невозможно) |
28 год | 29, 614657 |
29 | 421, 353641, 125123236840173674393761 |
30 | 31, 185302018885184100000000000000000000000000000001 |
31 год | |
32 | (невозможно) |
33 | 17, 703204309121 |
34 | 1336337 |
35 год | 613, 750313, 330616742651687834074918381127337110499579842147487712949050636668246738736343104392290115356445313 |
36 | 37, 1297 |
37 | 19 |
38 | |
39 | 761, 1156721 |
40 | 41, 1601 |
41 год | 31879515457326527173216321 |
42 | 43 год |
43 год | 5844100138801 |
44 год | 197352587024076973231046657 |
45 | 23, 1013 |
46 | 47, 4477457, 46 512 +1 (852 цифры: 214787904487 ... 289480994817) |
47 | 11905643330881 |
48 | 5308417 |
49 | 1201 |
50 |
(См. [13] [14] для получения дополнительной информации (четные основания до 1000), также см. [15] для нечетных оснований)
(Для наименьшего простого числа вида (для нечетных ), см. также OEIS : A111635 )
числа такой, что премьер | ||
---|---|---|
2 | 1 | 0, 1, 2, 3, 4, ... |
3 | 1 | 0, 1, 2, 4, 5, 6, ... |
3 | 2 | 0, 1, 2, ... |
4 | 1 | 0, 1, 2, 3, ... |
4 | 3 | 0, 2, 4, ... |
5 | 1 | 0, 1, 2, ... |
5 | 2 | 0, 1, 2, ... |
5 | 3 | 1, 2, 3, ... |
5 | 4 | 1, 2, ... |
6 | 1 | 0, 1, 2, ... |
6 | 5 | 0, 1, 3, 4, ... |
7 | 1 | 2, ... |
7 | 2 | 1, 2, ... |
7 | 3 | 0, 1, 8, ... |
7 | 4 | 0, 2, ... |
7 | 5 | 1, 4, ... |
7 | 6 | 0, 2, 4, ... |
8 | 1 | (никто) |
8 | 3 | 0, 1, 2, ... |
8 | 5 | 0, 1, 2, ... |
8 | 7 | 1, 4, ... |
9 | 1 | 0, 1, 3, 4, 5, ... |
9 | 2 | 0, 2, ... |
9 | 4 | 0, 1, ... |
9 | 5 | 0, 1, 2, ... |
9 | 7 | 2, ... |
9 | 8 | 0, 2, 5, ... |
10 | 1 | 0, 1, ... |
10 | 3 | 0, 1, 3, ... |
10 | 7 | 0, 1, 2, ... |
10 | 9 | 0, 1, 2, ... |
11 | 1 | 1, 2, ... |
11 | 2 | 0, 2, ... |
11 | 3 | 0, 3, ... |
11 | 4 | 1, 2, ... |
11 | 5 | 1, ... |
11 | 6 | 0, 1, 2, ... |
11 | 7 | 2, 4, 5, ... |
11 | 8 | 0, 6, ... |
11 | 9 | 1, 2, ... |
11 | 10 | 5, ... |
12 | 1 | 0, ... |
12 | 5 | 0, 4, ... |
12 | 7 | 0, 1, 3, ... |
12 | 11 | 0, ... |
13 | 1 | 0, 2, 3, ... |
13 | 2 | 1, 3, 9, ... |
13 | 3 | 1, 2, ... |
13 | 4 | 0, 2, ... |
13 | 5 | 1, 2, 4, ... |
13 | 6 | 0, 6, ... |
13 | 7 | 1, ... |
13 | 8 | 1, 3, 4, ... |
13 | 9 | 0, 3, ... |
13 | 10 | 0, 1, 2, 4, ... |
13 | 11 | 2, ... |
13 | 12 | 1, 2, 5, ... |
14 | 1 | 1, ... |
14 | 3 | 0, 3, ... |
14 | 5 | 0, 2, 4, 8, ... |
14 | 9 | 0, 1, 8, ... |
14 | 11 | 1, ... |
14 | 13 | 2, ... |
15 | 1 | 1, ... |
15 | 2 | 0, 1, ... |
15 | 4 | 0, 1, ... |
15 | 7 | 0, 1, 2, ... |
15 | 8 | 0, 2, 3, ... |
15 | 11 | 0, 1, 2, ... |
15 | 13 | 1, 4, ... |
15 | 14 | 0, 1, 2, 4, ... |
16 | 1 | 0, 1, 2, ... |
16 | 3 | 0, 2, 8, ... |
16 | 5 | 1, 2, ... |
16 | 7 | 0, 6, ... |
16 | 9 | 1, 3, ... |
16 | 11 | 2, 4, ... |
16 | 13 | 0, 3, ... |
16 | 15 | 0, ... |
(Для самых маленьких даже основывают таким образом, чтоявляется простым, см. OEIS : A056993 )
основывает таким образом, чтопростое (только рассмотреть даже а ) | Последовательность OEIS | |
---|---|---|
0 | 2, 4, 6, 10, 12, 16, 18, 22, 28, 30, 36, 40, 42, 46, 52, 58, 60, 66, 70, 72, 78, 82, 88, 96, 100, 102, 106, 108, 112, 126, 130, 136, 138, 148, 150, ... | A006093 |
1 | 2, 4, 6, 10, 14, 16, 20, 24, 26, 36, 40, 54, 56, 66, 74, 84, 90, 94, 110, 116, 120, 124, 126, 130, 134, 146, 150, 156, 160, 170, 176, 180, 184, ... | A005574 |
2 | 2, 4, 6, 16, 20, 24, 28, 34, 46, 48, 54, 56, 74, 80, 82, 88, 90, 106, 118, 132, 140, 142, 154, 160, 164, 174, 180, 194, 198, 204, 210, 220, 228, ... | A000068 |
3 | 2, 4, 118, 132, 140, 152, 208, 240, 242, 288, 290, 306, 378, 392, 426, 434, 442, 508, 510, 540, 542, 562, 596, 610, 664, 680, 682, 732, 782, ... | A006314 |
4 | 2, 44, 74, 76, 94, 156, 158, 176, 188, 198, 248, 288, 306, 318, 330, 348, 370, 382, 396, 452, 456, 470, 474, 476, 478, 560, 568, 598, 642, ... | A006313 |
5 | 30, 54, 96, 112, 114, 132, 156, 332, 342, 360, 376, 428, 430, 432, 448, 562, 588, 726, 738, 804, 850, 884, 1068, 1142, 1198, 1306, 1540, 1568, ... | A006315 |
6 | 102, 162, 274, 300, 412, 562, 592, 728, 1084, 1094, 1108, 1120, 1200, 1558, 1566, 1630, 1804, 1876, 2094, 2162, 2164, 2238, 2336, 2388, .. . | A006316 |
7 | 120, 190, 234, 506, 532, 548, 960, 1738, 1786, 2884, 3000, 3420, 3476, 3658, 4258, 5788, 6080, 6562, 6750, 7692, 8296, 9108, 9356, 9582, .. . | A056994 |
8 | 278, 614, 892, 898, 1348, 1494, 1574, 1938, 2116, 2122, 2278, 2762, 3434, 4094, 4204, 4728, 5712, 5744, 6066, 6508, 6930, 7022, 7332, ... | A056995 |
9 | 46, 1036, 1318, 1342, 2472, 2926, 3154, 3878, 4386, 4464, 4474, 4482, 4616, 4688, 5374, 5698, 5716, 5770, 6268, 6386, 6682, 7388, 7992, ... | A057465 |
10 | 824, 1476, 1632, 2462, 2484, 2520, 3064, 3402, 3820, 4026, 6640, 7026, 7158, 9070, 12202, 12548, 12994, 13042, 15358, 17646, 17670, ... | A057002 |
11 | 150, 2558, 4650, 4772, 11272, 13236, 15048, 23302, 26946, 29504, 31614, 33308, 35054, 36702, 37062, 39020, 39056, 43738, 44174, 45654, ... | A088361 |
12 | 1534, 7316, 17582, 18224, 28234, 34954, 41336, 48824, 51558, 51914, 57394, 61686, 62060, 89762, 96632, 98242, 100540, 101578, 109696, ... | A088362 |
13 | 30406, 71852, 85654, 111850, 126308, 134492, 144642, 147942, 150152, 165894, 176206, 180924, 201170, 212724, 222764, 225174, 241600, ... | A226528 |
14 | 67234, 101830, 114024, 133858, 162192, 165306, 210714, 216968, 229310, 232798, 422666, 426690, 449732, 462470, 468144, 498904, 506664, ... | A226529 |
15 | 70906, 167176, 204462, 249830, 321164, 330716, 332554, 429370, 499310, 524552, 553602, 743788, 825324, 831648, 855124, 999236, 1041870, ... | A226530 |
16 | 48594, 108368, 141146, 189590, 255694, 291726, 292550, 357868, 440846, 544118, 549868, 671600, 843832, 857678, 1024390, 1057476, 1087540, ... | A251597 |
17 | 62722, 130816, 228188, 386892, 572186, 689186, 909548, 1063730, 1176694, 1361244, 1372930, 1560730, 1660830, 1717162, 1722230, 1766192, ... | A253854 |
18 | 24518, 40734, 145310, 361658, 525094, 676754, 773620, 1415198, 1488256, 1615588, 1828858, 2042774, 2514168, 2611294, 2676404, 3060772, ... | A244150 |
19 | 75898, 341112, 356926, 475856, 1880370, 2061748, 2312092, ... | A243959 |
20 | 919444, 1059094, ... | A321323 |
Наименьшее основание b такое, что b 2 n + 1 простое, - это
- 2, 2, 2, 2, 2, 30, 102, 120, 278, 46, 824, 150, 1534, 30406, 67234, 70906, 48594, 62722, 24518, 75898, 919444, ... (последовательность A056993 в OEIS )
Наименьшие k такие, что (2 n ) k + 1 простое число, равны
- 1, 1, 1, 0, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 0, 4, 1, ... (следующий член неизвестен) (последовательность A079706 в OEIS ) (также см OEIS : A228101 и OEIS : A084712 )
Более сложную теорию можно использовать для предсказания количества оснований, для которых будет простым для фиксированного . Можно примерно ожидать, что количество обобщенных простых чисел Ферма уменьшится вдвое по мере того, как увеличивается на 1.
Наибольшие известные обобщенные простые числа Ферма
Ниже приводится список из 5 самых больших известных обобщенных простых чисел Ферма. [16] Все они мегаприминированы . Вся топ-5 открыта участниками проекта PrimeGrid .
Классифицировать | Прайм-ранг [17] | простое число | Обобщенные обозначения Ферма | Количество цифр | Дата нахождения | исх. |
---|---|---|---|---|---|---|
1 | 14 | 1059094 1048576 + 1 | Ф 20 (1059094) | 6 317 602 | Ноя 2018 | [18] |
2 | 15 | 919444 1048576 + 1 | Ф 20 (919444) | 6 253 210 | Сентябрь 2017 | [19] |
3 | 31 год | 3214654 524288 + 1 | Ф 19 (3214654) | 3 411 613 | Декабрь 2019 | [20] |
4 | 32 | 2985036 524288 + 1 | Ф 19 (2985036) | 3 394 739 | Сентябрь 2019 | [21] |
5 | 33 | 2877652 524288 + 1 | Ф 19 (2877652) | 3 386 397 | Июн 2019 | [22] |
На Prime Pages можно найти 100 лучших обобщенных простых чисел Ферма .
Смотрите также
- Конструируемый многоугольник : какие правильные многоугольники можно построить, частично зависит от простых чисел Ферма.
- Двойная экспоненциальная функция
- Теорема Лукаса
- Мерсенн прайм
- Pierpont Prime
- Тест на первичность
- Теорема прота
- Псевдопремия
- Число Серпинского
- Последовательность Сильвестра
Заметки
- ^ Křížek, Luca & Somer 2001 , стр. 38, замечание 4.15
- ^ Крис Колдуэлл, «Prime Links ++: специальные формы». Архивировано 24 декабря 2013 г. в Wayback Machine на Prime Pages .
- ^ Ribenboim 1996 , стр. 88.
- ^ a b c Келлер, Уилфрид (18 января 2021 г.), « Основные факторы чисел Ферма» , ProthSearch.com , получено 19 января 2021 г.
- ^ Boklan, Kent D .; Конвей, Джон Х. (2017). «Ожидайте не более одной миллиардной доли нового Fermat Prime!». 39 (1): 3–5. arXiv : 1605.01371 . Цитировать журнал требует
|journal=
( помощь ) - ^ Сандифер, Эд. «Как это сделал Эйлер» (PDF) . MAA Online . Математическая ассоциация Америки . Проверено 13 июня 2020 .
- ^ ":: FERMATSEARCH. ORG :: Домашняя страница" . www.fermatsearch.org . Проверено 7 апреля 2018 года .
- ^ ":: FERMATSEARCH. ORG :: Новости" . www.fermatsearch.org . Проверено 7 апреля 2018 года .
- ^ Крижек, Михал; Лука, Флориан; Сомер, Лоуренс (14 марта 2013 г.). 17 лекций о числах Ферма: от теории чисел к геометрии . Springer Science & Business Media. ISBN 9780387218502. Проверено 7 апреля 2018 г. - через Google Книги.
- ^ Йеппе Стиг Нильсен, «S (n) = n ^ n + 1» .
- ^ Вайсштейн, Эрик В. "Число Серпинского первого рода" . MathWorld .
- ^ PRP Top Records, поиск x ^ (2 ^ 16) + y ^ (2 ^ 16) , Анри и Рено Лифшицы.
- ^ «Обобщенные простые числа Ферма» . jeppesn.dk . Проверено 7 апреля 2018 года .
- ^ «Обобщенные простые числа Ферма для оснований до 1030» . noprimeleftbehind.net . Проверено 7 апреля 2018 года .
- ^ «Обобщенные простые числа Ферма в нечетных основаниях» . fermatquotient.com . Проверено 7 апреля 2018 года .
- ^ Колдуэлл, Крис К. «Двадцать лучших: обобщенный Ферма» . Основные страницы . Проверено 11 июля 2019 .
- ^ Колдуэлл, Крис К. «Вывод поиска в базе данных» . Основные страницы . Проверено 11 июля 2019 .
- ^ 1059094 1048576 + 1
- ^ 919444 1048576 + 1
- ^ 3214654 524288 + 1
- ^ 2985036 524288 + 1
- ^ 2877652 524288 + 1
Рекомендации
- Голомб, SW (1 января 1963 г.), «О сумме обратных чисел Ферма и связанных с ними иррациональностей», Canadian Journal of Mathematics , 15 : 475–478, doi : 10.4153 / CJM-1963-051-0
- Grytczuk, A .; Лука, F. & Wójtowicz, M. (2001), "Еще одно замечание о самых простых делителей чисел Ферма", Юго - Восточной Азии Бюллетень математики , 25 (1): 111-115, DOI : 10.1007 / s10012-001-0111 -4 , S2CID 122332537
- Гай, Ричард К. (2004), Нерешенные проблемы теории чисел , Проблемные книги по математике, 1 (3-е изд.), Нью-Йорк: Springer Verlag , стр. A3, A12, B21, ISBN 978-0-387-20860-2
- Кржижек, Михал; Лука, Флориан и Сомер, Лоуренс (2001), 17 лекций по числам Ферма: от теории чисел к геометрии , книги CMS по математике, 10 , Нью-Йорк: Springer, ISBN 978-0-387-95332-8 - Эта книга содержит обширный список литературы.
- Кржижек, Михал; Лука, Флориан и Somer, Лоуренс (2002), «О сходимости рядов обратных простых чисел , связанных с числами Ферма» (PDF) , Журнал теории чисел , 97 (1): 95-112, DOI : 10,1006 / jnth .2002.2782
- Лука, Флориан (2000), "Номер антиобщественное Ферма" , American Mathematical Monthly , 107 (2): 171-173, DOI : 10,2307 / 2589441 , JSTOR 2589441
- Рибенбойм, Пауло (1996), Новая книга рекордов простых чисел (3-е изд.), Нью-Йорк: Springer, ISBN 978-0-387-94457-9
- Робинсон, Рафаэль М. (1954), "Мерсенна и Ферма Числа", Труды Американского математического общества , 5 (5): 842-846, DOI : 10,2307 / 2031878 , JSTOR 2031878
- Ябута, М. (2001), "Простое доказательство теоремы Кармайкла о примитивных делителях" (PDF) , Fibonacci Quarterly , 39 : 439–443
Внешние ссылки
- Крис Колдуэлл, The Prime Glossary: Число Ферма на Prime Pages .
- Луиджи Морелли, История чисел Ферма
- Джон Косгрейв, Объединение чисел Мерсенна и Ферма
- Уилфрид Келлер, Основные факторы чисел Ферма
- Вайсштейн, Эрик В. «Число Ферма» . MathWorld .
- Вайсштейн, Эрик В. «Ферма Прайм» . MathWorld .
- Вайсштейн, Эрик В. «Ферма Псевдопрайм» . MathWorld .
- Вайсштейн, Эрик В. «Обобщенное число Ферма» . MathWorld .
- Ив Галло, Обобщенный поиск простых чисел Ферма
- Марк С. Манассе, Полная факторизация девятого числа Ферма (исходное объявление)
- Пейтон Хейслетт, Крупнейшее известное обобщенное объявление Fermat Prime