Число Ферма

В математике число Ферма , названное в честь Пьера де Ферма , который их первым изучил, представляет собой положительное целое число вида

${\displaystyle F_{n}=2^{2^{n}}+1,}$

где n - неотрицательное целое число. Первые несколько чисел Ферма:

3 , 5 , 17 , 257 , 65537 , 4294967297, 18446744073709551617,… (последовательность A000215 в OEIS ).

Если 2 ^k  + 1 простое число и k > 0, то k должно быть степенью двойки, поэтому 2 ^k  + 1 является числом Ферма; такие простые числа называются простыми числами Ферма . По состоянию на 2021 год единственными известными простыми числами Ферма являются F ₀ = 3, F ₁ = 5, F ₂ = 17, F ₃ = 257 и F ₄ = 65537 (последовательность A019434 в OEIS ); эвристика подсказывает, что их больше нет.

Основные свойства [ править ]

Числа Ферма удовлетворяют следующим рекуррентным соотношениям :

${\displaystyle F_{n}=(F_{n-1}-1)^{2}+1}$

${\displaystyle F_{n}=F_{0}\cdots F_{n-1}+2}$

для n ≥ 1,

${\displaystyle F_{n}=F_{n-1}+2^{2^{n-1}}F_{0}\cdots F_{n-2}}$

${\displaystyle F_{n}=F_{n-1}^{2}-2(F_{n-2}-1)^{2}}$

для n ≥ 2. Каждое из этих соотношений доказывается математической индукцией . Из второго уравнения мы можем вывести теорему Гольдбаха (названную в честь Кристиана Гольдбаха ): никакие два числа Ферма не имеют общего целочисленного множителя больше 1 . Чтобы убедиться в этом, предположим, что 0 ≤ i < j и F _i и F _j имеют общий делитель a > 1. Тогда a делит оба

${\displaystyle F_{0}\cdots F_{j-1}}$

и F _j ; следовательно, a делит их разность на 2. Поскольку a > 1, это вынуждает a = 2. Противоречие , потому что каждое число Ферма явно нечетное. В качестве следствия мы получаем еще одно доказательство бесконечности простых чисел: для каждого F _n выбираем простой множитель p _n ; тогда последовательность { p _n } представляет собой бесконечную последовательность различных простых чисел.

Другие свойства [ править ]

• Нет Ферма премьер может быть выражена как разность два р - й степеней, где р представляет собой нечетное простое число.
• За исключением F ₀ и F ₁ , последняя цифра числа Ферма - 7.
• Сумма обратных величин всех чисел Ферма (последовательность A051158 в OEIS ) является иррациональной . ( Соломон В. Голомб , 1963)

Простота чисел Ферма [ править ]

Числа Ферма и простые числа Ферма были впервые изучены Пьером де Ферма, который предположил, что все числа Ферма простые. Действительно, легко показать , что первые пять чисел Ферма F ₀ , ..., F ₄ простые. Гипотеза Ферма была опровергнута Леонардом Эйлером в 1732 году, когда он показал, что

${\displaystyle F_{5}=2^{2^{5}}+1=2^{32}+1=4294967297=641\times 6700417.}$

Эйлер доказал, что каждый множитель F _n должен иметь вид k  2 ^{n +1}  + 1 (позже улучшенный до k  2 ^{n +2}  + 1 Люкасом ).

То, что 641 является фактором F _5, можно вывести из равенств 641 = 2 ⁷  × 5 + 1 и 641 = 2 ⁴  + 5 ⁴ . Из первого равенства следует, что 2 ⁷  × 5 −1 (mod 641) и, следовательно, (в четвертой степени), что 2 ²⁸  × 5 ⁴  ≡ 1 (mod 641). С другой стороны, из второго равенства следует, что 5 ⁴  ≡ −2 ⁴  (mod 641). Из этих сравнений следует, что 2 ³²  ≡ −1 (mod 641).

Ферма, вероятно, знал о форме факторов, позже доказанных Эйлером, поэтому кажется любопытным, что он не смог выполнить прямые вычисления, чтобы найти фактор. ^[1] Одно из распространенных объяснений состоит в том, что Ферма допустил вычислительную ошибку.

Других известных простых чисел Ферма F _n с n  > 4 не существует, но мало что известно о числах Ферма для больших n . ^[2] Фактически, каждая из следующих проблем является открытой:

• Является ли F _п композит для всех п  > 4?
• Бесконечно много простых чисел Ферма? ( Эйзенштейн 1844) ^[3]
• Бесконечно много составных чисел Ферма?
• Существует ли число Ферма, не свободное от квадратов ?

По состоянию на 2014 ^[update]год известно, что F _n является составным для 5 ≤ n ≤ 32 , хотя из них полные факторизации F _n известны только для 0 ≤ n ≤ 11 , и нет известных простых множителей для n  = 20 и п  = 24 . ^[4] Наибольшее известное составное число Ферма - F _18233954 , а его простой множитель 7 × 2 ^18233956 + 1 , мегапростое число , было обнаружено в октябре 2020 года.

Эвристические аргументы [ править ]

Эвристика предполагает, что F ₄ - последнее простое число Ферма.

Теорема простого числа , подразумевает , что случайное число в подходящем интервале вокруг N является простым с вероятностью 1  /  Ln N . Если использовать эвристику, согласно которой число Ферма является простым с той же вероятностью, что и случайное целое число его размера, и что F ₅ , ..., F ₃₂ являются составными, то ожидаемое количество простых чисел Ферма, превышающих F ₄ (или эквивалентно , за пределами F ₃₂ ) должно быть

${\displaystyle \sum _{n\geq 33}{\frac {1}{\ln F_{n}}}<{\frac {1}{\ln 2}}\sum _{n\geq 33}{\frac {1}{\log _{2}(2^{2^{n}})}}={\frac {1}{\ln 2}}2^{-32}<3.36\times 10^{-10}.}$

Это число можно интерпретировать как верхнюю границу вероятности того, что существует простое число Ферма, превышающее F ₄ .

Этот аргумент не является строгим доказательством. Во-первых, предполагается, что числа Ферма ведут себя «случайным образом», но множители чисел Ферма обладают особыми свойствами. Боклан и Конвей опубликовали более точный анализ, предполагающий, что вероятность того, что существует еще одно простое число Ферма, меньше одного на миллиард. ^[5]

Эквивалентные условия первичности [ править ]

Позвольте быть n- м числом Ферма. Тест Пепена утверждает, что при n  > 0${\displaystyle F_{n}=2^{2^{n}}+1}$

${\displaystyle F_{n}}$ прост тогда и только тогда, когда ${\displaystyle 3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}.}$

Выражение может быть оценена по модулю путем повторного возведения в квадрат . Это делает тест быстрым алгоритмом с полиномиальным временем . Но числа Ферма растут так быстро, что лишь небольшую часть из них можно проверить в разумные сроки и в разумных пределах.${\displaystyle 3^{(F_{n}-1)/2}}$${\displaystyle F_{n}}$

Есть несколько тестов для чисел вида k  2 ^m  + 1, таких как множители чисел Ферма, на простоту.

Теорема Прота (1878 г.). Пусть =  + с нечетным < . Если существует такое целое число, что${\displaystyle N}$${\displaystyle k}$ ${\displaystyle 2}$^{${\displaystyle m}$}${\displaystyle 1}$${\displaystyle k}$${\displaystyle 2}$^{${\displaystyle m}$}${\displaystyle a}$

${\displaystyle a^{(N-1)/2}\equiv -1{\pmod {N}}}$

тогда простое. И наоборот, если вышеуказанное сравнение не выполняется, и вдобавок${\displaystyle N}$

${\displaystyle \left({\frac {a}{N}}\right)=-1}$(См. Символ Якоби )

тогда составной.${\displaystyle N}$

Если N  =  F _n > 3, то указанный выше символ Якоби всегда равен −1 для a = 3, и этот частный случай теоремы Прота известен как тест Пепена . Хотя тест Пепина и теорема Прота были реализованы на компьютерах, чтобы доказать составность некоторых чисел Ферма, ни один из тестов не дает конкретного нетривиального фактора. Фактически, для n  = 20 и 24 не известны конкретные простые множители .

Факторизация чисел Ферма [ править ]

Из-за размера чисел Ферма сложно разложить на множители или даже проверить простоту. Тест Пепена дает необходимое и достаточное условие простоты чисел Ферма и может быть реализован на современных компьютерах. Метод эллиптических кривых - это быстрый метод поиска малых простых делителей чисел. Проект распределенных вычислений Fermatsearch обнаружил некоторые факторы чисел Ферма. Программа proth.exe Ива Галло использовалась для нахождения множителей больших чисел Ферма. Эдуард Лукас , улучшая упомянутый выше результат Эйлера, доказал в 1878 году, что каждый множитель числа Ферма , при n не менее 2, имеет вид (см. Число Прота ), где k${\displaystyle F_{n}}$${\displaystyle k\times 2^{n+2}+1}$положительное целое число. Само по себе это позволяет легко доказать простоту известных простых чисел Ферма.

Факторизации первых двенадцати чисел Ферма:

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 ... 491,382,441,723,306,598,834,177 (564 цифры) (полностью учтены данные 1988 г.)

По состоянию на 2018 год ^[update]только F ₀ - F ₁₁ были полностью учтены . ^[4] Проект распределенных вычислений Fermat Search занимается поиском новых множителей чисел Ферма. ^[7] Набор всех коэффициентов Ферма - A050922 (или, отсортированный, A023394 ) в OEIS .

Следующие факторы чисел Ферма были известны до 1950 года (с тех пор цифровые компьютеры помогли найти больше факторов):

Год	Finder	Число Ферма	Фактор
1732 г.	Эйлер	${\displaystyle F_{5}}$	${\displaystyle 5\cdot 2^{7}+1}$
1732 г.	Эйлер	${\displaystyle F_{5}}$ (полностью учтено)	${\displaystyle 52347\cdot 2^{7}+1}$
1855 г.	Clausen	${\displaystyle F_{6}}$	${\displaystyle 1071\cdot 2^{8}+1}$
1855 г.	Clausen	${\displaystyle F_{6}}$ (полностью учтено)	${\displaystyle 262814145745\cdot 2^{8}+1}$
1877 г.	Первушин	${\displaystyle F_{12}}$	${\displaystyle 7\cdot 2^{14}+1}$
1878 г.	Первушин	${\displaystyle F_{23}}$	${\displaystyle 5\cdot 2^{25}+1}$
1886 г.	Зилхофф	${\displaystyle F_{36}}$	${\displaystyle 5\cdot 2^{39}+1}$
1899 г.	Каннингем	${\displaystyle F_{11}}$	${\displaystyle 39\cdot 2^{13}+1}$
1899 г.	Каннингем	${\displaystyle F_{11}}$	${\displaystyle 119\cdot 2^{13}+1}$
1903 г.	Западный	${\displaystyle F_{9}}$	${\displaystyle 37\cdot 2^{16}+1}$
1903 г.	Западный	${\displaystyle F_{12}}$	${\displaystyle 397\cdot 2^{16}+1}$
1903 г.	Западный	${\displaystyle F_{12}}$	${\displaystyle 973\cdot 2^{16}+1}$
1903 г.	Западный	${\displaystyle F_{18}}$	${\displaystyle 13\cdot 2^{20}+1}$
1903 г.	Каллен	${\displaystyle F_{38}}$	${\displaystyle 3\cdot 2^{41}+1}$
1906 г.	Morehead	${\displaystyle F_{73}}$	${\displaystyle 5\cdot 2^{75}+1}$
1925 г.	Крайчик	${\displaystyle F_{15}}$	${\displaystyle 579\cdot 2^{21}+1}$

По состоянию на январь 2021 ^[update]года известно 356 простых множителей чисел Ферма, а 312 чисел Ферма - составные. ^[4] Каждый год обнаруживается несколько новых факторов Ферма. ^[8]

Псевдопримеры и числа Ферма [ править ]

Подобно составным числам формы 2 ^p  - 1, каждое составное число Ферма является сильным псевдопростым числом по основанию 2. Это связано с тем, что все сильные псевдопростые числа по основанию 2 также являются псевдопростыми числами Ферма, т.е.

${\displaystyle 2^{F_{n}-1}\equiv 1{\pmod {F_{n}}}}$

для всех чисел Ферма.

В 1904 году Чиполла показал, что произведение по крайней мере двух различных простых или составных чисел Ферма будет псевдопростом Ферма с основанием 2 тогда и только тогда, когда . ^[9]${\displaystyle F_{a}F_{b}\dots F_{s},}$ ${\displaystyle a>b>\dots >s>1}$${\displaystyle 2^{s}>a}$

Другие теоремы о числах Ферма [ править ]

Связь с конструируемыми полигонами [ править ]

Карл Фридрих Гаусс разработал теорию гауссовских периодов в своих Disquisitiones Arithmeticae и сформулировал достаточное условие конструктивности правильных многоугольников. Гаусс заявил, что это условие также необходимо , но не опубликовал доказательства. Пьер Ванцель дал полное доказательство необходимости в 1837 году. Результат известен как теорема Гаусса – Ванцеля :

П односторонняя правильный многоугольник может быть построен с циркулем и линейкой тогда и только тогда , когда п является произведением мощности 2 -х и различных простых чисел Ферма: Другими словами, если и только если п имеет вид п = 2 ^к р ₁ p ₂ … p _s , где k - неотрицательное целое число, а p _i - различные простые числа Ферма.

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

Применение чисел Ферма [ править ]

Генерация псевдослучайных чисел [ править ]

Простые числа Ферма особенно полезны при генерации псевдослучайных последовательностей чисел в диапазоне 1… N , где N - степень числа 2. Наиболее распространенный метод - взять любое начальное значение от 1 до P - 1, где P - это Ферма прайм. Теперь умножьте это на число A , которое больше квадратного корня из P и является первообразным корнем по модулю P (т. Е. Это не квадратичный вычет ). Затем возьмите результат по модулю P . Результат - новое значение для ГСЧ.

${\displaystyle V_{j+1}=\left(A\times V_{j}\right){\bmod {P}}}$(см. линейный конгруэнтный генератор , RANDU )

Это полезно в информатике, поскольку большинство структур данных имеют элементы с 2- ^{кратными} возможными значениями. Например, байт имеет 256 (2 ⁸ ) возможных значений (0–255). Следовательно, чтобы заполнить байт или байты случайными значениями, можно использовать генератор случайных чисел, который выдает значения 1–256, причем байт принимает выходное значение -1. По этой причине очень большие простые числа Ферма представляют особый интерес для шифрования данных. Этот метод выдает только псевдослучайные значения, так как после P - 1 повторений последовательность повторяется. Неправильно выбранный множитель может привести к тому, что последовательность будет повторяться раньше, чем P - 1.

Другие интересные факты [ править ]

Число Ферма не может быть идеальным числом или частью пары дружественных чисел . ( Лука 2000 )

Серия обратных всех простых делителей чисел Ферма сходится . ( Кржижек, Лука и Сомер 2002 )

Если n ⁿ  + 1 простое число, существует такое целое число m , что n = 2 ^{2 m} . В этом случае выполняется равенство n ⁿ  + 1 = F _{(2 ^m + m )} . ^{[10] [11]}

Пусть наибольший простой делитель числа Ферма F _n равен P ( F _n ). Потом,

${\displaystyle P(F_{n})\geq 2^{n+2}(4n+9)+1.}$( Grytczuk, Luca & Wójtowicz 2001 )

Обобщенные числа Ферма [ править ]

Числа вида с a , b любыми взаимно простыми целыми числами, a > b > 0, называются обобщенными числами Ферма . Нечетное простое число p является обобщенным числом Ферма тогда и только тогда, когда p конгруэнтно 1 (mod 4) . (Здесь мы рассматриваем только случай n > 0, поэтому 3 = не является контрпримером.)${\displaystyle a^{2^{\overset {n}{}}}\!\!+b^{2^{\overset {n}{}}}}$${\displaystyle 2^{2^{0}}\!+1}$

Пример вероятного простого числа этой формы - 124 ⁶⁵⁵³⁶ + 57 ⁶⁵⁵³⁶ (найдено Валерием Курышевым). ^[12]

По аналогии с обычными числами Ферма, он является общим для записи обобщенных чисел Ферма вида как F _п ( ). Например, в этой записи число 100 000 001 будет записано как F ₃ (10). В дальнейшем мы ограничимся простыми числами этой формы , такие простые числа называются «простые числа Ферма с основанием a ». Конечно, эти простые числа существуют только если это даже .${\displaystyle a^{2^{\overset {n}{}}}\!\!+1}$${\displaystyle a^{2^{\overset {n}{}}}\!\!+1}$

Если мы требуем n > 0, то четвертая проблема Ландау спрашивает, существует ли бесконечно много обобщенных простых чисел Ферма F _n ( a ).

Обобщенные простые числа Ферма [ править ]

Из-за простоты доказательства их простоты обобщенные простые числа Ферма в последние годы стали предметом исследований в области теории чисел. Многие из наибольших известных сегодня простых чисел являются обобщенными простыми числами Ферма.

Обобщенные числа Ферма могут быть простыми только для четных a , потому что если a нечетное, то каждое обобщенное число Ферма делится на 2. Наименьшее простое число с is , или 30 ³²  + 1. Кроме того, мы можем определить «полуобобщенные числа Ферма». «для нечетного основания будет полуобобщенное число Ферма для основания a (для нечетного a ) , и также следует ожидать, что будет только конечное число полуобобщенных простых чисел Ферма для каждого нечетного основания.${\displaystyle F_{n}(a)}$${\displaystyle n>4}$${\displaystyle F_{5}(30)}$${\displaystyle {\frac {a^{2^{n}}\!+1}{2}}}$

(В списке, обобщенные числа Ферма ( ) к еще являются для нечетных а они . Если является идеальной мощностью с нечетным показателем (последовательность A070265 в OEIS ), то все обобщенное число Ферма может быть алгебраическим факторизованы, поэтому они не могут быть простыми)${\displaystyle F_{n}(a)}$${\displaystyle a^{2^{n}}\!+1}$${\displaystyle {\frac {a^{2^{n}}\!\!+1}{2}}}$

(Для наименьшего числа , которое является простым, см. OEIS :  A253242 )${\displaystyle n}$${\displaystyle F_{n}(a)}$

${\displaystyle a}$	числа такие, что простые${\displaystyle n}$ ${\displaystyle F_{n}(a)}$	${\displaystyle a}$	числа такие, что простые${\displaystyle n}$ ${\displaystyle F_{n}(a)}$	${\displaystyle a}$	числа такие, что простые${\displaystyle n}$ ${\displaystyle F_{n}(a)}$	${\displaystyle a}$	числа такие, что простые${\displaystyle n}$ ${\displaystyle F_{n}(a)}$
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, ...

(См. ^{[13] [14]} для получения дополнительной информации (четные основания до 1000), также см. ^[15] для нечетных оснований)

(Для наименьшего простого числа формы (для нечетного ) см. Также OEIS :  A111635 )${\displaystyle F_{n}(a,b)}$${\displaystyle a+b}$

${\displaystyle a}$	${\displaystyle b}$	числа такие, что простые${\displaystyle n}$ ${\displaystyle {\frac {a^{2^{n}}+b^{2^{n}}}{\gcd(a+b,2)}}(=F_{n}(a,b))}$
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, ...

(Для наименьшего четного основания a, такого как простое число, см. OEIS :  A056993 )${\displaystyle F_{n}(a)}$

${\displaystyle n}$	БАЗ таким образом, что является первичным (рассматривать только даже )${\displaystyle F_{n}(a)}$	Последовательность 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.${\displaystyle F_{n}(a)}$${\displaystyle n}$${\displaystyle n}$

Наибольшие известные обобщенные простые числа Ферма [ править ]

Ниже приводится список из 5 самых больших известных обобщенных простых чисел Ферма. ^{[16] Все} они мегапримеры . Вся топ-5 открыта участниками проекта PrimeGrid .

На основных страницах можно найти 100 лучших обобщенных простых чисел Ферма .

См. Также [ править ]

• Конструируемый многоугольник : какие правильные многоугольники можно построить, частично зависит от простых чисел Ферма.
• Двойная экспоненциальная функция
• Теорема Лукаса
• Мерсенн прайм
• Pierpont Prime
• Тест на первичность
• Теорема прота
• Псевдопремия
• Число Серпинского
• Последовательность Сильвестра

Примечания [ править ]

Ссылки [ править ]

• Голомб, 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