Число Ферма

редактировать

Простое число Ферма
Названо в честь	Пьера де Ферма
№ известных терминов	5
Предполагаемое количество терминов	5
Подпоследовательность of	Числа Ферма
Первые термины	3, 5, 17, 257, 65537
Наибольший известный термин	65537
OEIS index	A019434

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

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

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

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

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

Если 2 + 1 простое число и k>0, можно показать, что k должно быть степенью двойки (если k = ab, где 1 ≤ a, b ≤ k и b равно нечетное, то 2 + 1 = (2) + 1 ≡ (−1) + 1 = 0 (mod 2 + 1). Полное доказательство см. в ниже.) Другими словами, каждое простое число формы 2 + 1 (кроме 2 = 2 + 1) является числом Ферма, и такие простые числа называются простыми числами Ферма . По состоянию на 2019 год единственными известными простыми числами Ферма являются F 0, F 1, F 2, F 3 и F 4 (последовательность A019434 в OEIS ).

Содержание

1 Основные свойства
- 1.1 Дополнительные свойства
2 Простота чисел Ферма
- 2.1 Эвристические аргументы для плотности
- 2.2 Эквивалентные условия простоты
3 Факторизация чисел Ферма
4 Псевдопростые числа и числа Ферма
5 Другие теоремы о числах Ферма
6 Связь с конструируемыми многоугольниками
7 Применение чисел Ферма
- 7.1 Генерация псевдослучайных чисел
8 Другие интересные факты
9 Обобщенные числа Ферма
- 9.1 Обобщенные простые числа Ферма
- 9.2 Наибольшие известные обобщенные числа Простые числа Ферма
10 См. Также
11 Примечания
12 Ссылки
13 Внешние ссылки

Основные свойства

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

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

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

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

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

для n ≥ 1,

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

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

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

{\ d isplaystyle F_ {n} = F_ {n-1} ^ {2} -2 (F_ {n-2} -1) ^ {2}}

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

F 0 ⋯ F j - 1 {\ displaystyle F_ {0} \ cdots F_ {j-1}}

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

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

Дополнительные свойства

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

Простота чисел Ферма

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

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

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

Эйлер доказал, что каждый множитель F n должен иметь вид k 2 + 1 (позже улучшено до k 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).

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

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

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

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

Эвристические аргументы в пользу плотности

Существует несколько вероятностных аргументов в пользу конечности простых чисел Ферма.

Согласно теореме о простых числах, «вероятность » того, что число n является простым, составляет около 1 / ln (n). Следовательно, общее ожидаемое число простых чисел Ферма не превосходит

∑ n = 0 ∞ 1 ln ⁡ F n = 1 ln ⁡ 2 ∑ n = 0 ∞ 1 log 2 ⁡ (2 2 n + 1) < 1 ln ⁡ 2 ∑ n = 0 ∞ 2 − n = 2 ln ⁡ 2 = 2.885... {\displaystyle {\begin{aligned}\sum _{n=0}^{\infty }{\frac {1}{\ln F_{n}}}={\frac {1}{\ln 2}}\sum _{n=0}^{\infty }{\frac {1}{\log _{2}\left(2^{2^{n}}+1\right)}}\\<{\frac {1}{\ln 2}}\sum _{n=0}^{\infty }2^{-n}\\={\frac {2}{\ln 2}}\\=2.885...\end{aligned}}}

{\ displaystyle {\ begin {align} \ sum _ {n = 0} ^ {\ infty} {\ frac {1} {\ ln F_ {n}}} = {\ frac {1} { \ ln 2}} \ sum _ {n = 0} ^ {\ infty} {\ frac {1} {\ log _ {2} \ left (2 ^ {2 ^ {n}} + 1 \ right)}} \\ <{\ frac {1} {\ ln 2}} \ sum _ {n = 0} ^ {\ infty} 2 ^ {- n} \\ = {\ frac {2} {\ ln 2} } \\ = 2,885... \ end {align}}}

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

Если (более изощренно) мы рассматриваем условную вероятность того, что n является простым, с учетом того, что мы знаем, что все его простые множители превышают B, не более чем A ln (B) / ln (n), то используя теорему Эйлера что наименьший простой делитель F n превышает 2, вместо этого мы найдем

A ∑ n = 0 ∞ ln ⁡ 2 n + 1 ln ⁡ F n = A ∑ n = 0 ∞ log 2 ⁡ 2 n + 1 log 2 ⁡ (2 2 n + 1) < A ∑ n = 0 ∞ ( n + 1) 2 − n = 4 A. {\displaystyle {\begin{aligned}A\sum _{n=0}^{\infty }{\frac {\ln 2^{n+1}}{\ln F_{n}}}=A\sum _{n=0}^{\infty }{\frac {\log _{2}2^{n+1}}{\log _{2}\left(2^{2^{n}}+1\right)}}\\

{\ displaystyle {\ begin {align} A \ sum _ {n = 0} ^ {\ infty} {\ frac {\ ln 2 ^ {n + 1}} {\ ln F_ { n}}} = A \ sum _ {n = 0} ^ {\ infty} {\ frac {\ log _ {2} 2 ^ {n + 1}} {\ log _ {2} \ left (2 ^ {2 ^ {n}} + 1 \ right)}} \\ <A \ sum _ {n = 0} ^ {\ infty} (n + 1) 2 ^ {- n} \\ = 4A. \ конец {выровнен}}}

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

Пусть

F n = 2 2 n + 1 {\ displaystyle F_ {n} = 2 ^ { 2 ^ {n}} + 1}

F_ {n} = 2 ^ {{2 ^ {n}}} + 1

- n-е число Ферма. Тест Пепина утверждает, что для n>0

F n {\ displaystyle F_ {n}}

F_ {n}

является простым тогда и только тогда, когда

3 (F n - 1) / 2 ≡ - 1 ( мод F n). {\ displaystyle 3 ^ {(F_ {n} -1) / 2} \ Equiv -1 {\ pmod {F_ {n}}}.}

3 ^ {{(F_ {n} -1) / 2}} \ Equiv -1 {\ pmod {F_ {n}}}.

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

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

Теорема Прота (1878). Пусть

N {\ displaystyle N}

N

k {\ displaystyle k}

k

2 {\ displaystyle 2}

2

1 {\ displaystyle 1}

1

с нечетным

k { \ displaystyle k}

k

2 {\ displaystyle 2}

2

. Если существует целое число

a {\ displaystyle a}

a

такое, что

a (N - 1) / 2 ≡ - 1 (mod N) {\ displaystyle a ^ {(N-1) / 2} \ Equiv -1 {\ pmod {N}}}

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

, тогда

N {\ displaystyle N}

N

простое число. И наоборот, если указанное выше сравнение не выполняется и, кроме того,

(a N) = - 1 {\ displaystyle \ left ({\ frac {a} {N}} \ right) = - 1}

{\ displaystyle \ left ({\ frac {a} {N}} \ right) = - 1}

(См. символ Якоби )

, тогда

N {\ displaystyle N}

N

является составным.

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

Факторизация чисел Ферма

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

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

3 простое

5 простое

17 простое

257 простое

65 537 наибольшее известное Fermat prime

4,294,967,297

641 × 6,700,417 (с полным факторингом 1732)

18,446,744,073,709,551,617 (20 цифр)

274,177 × 67,280,421,310,721 (14 цифр) (с полным факторингом 1855) <516,338,438,4631920 (с полным факторингом 1855) <516,338,438,463,763,763,763,763,457>59,649,589,127,497,217 (17 цифр) × 5,704,689,200,685,129,054,721 (22 цифр) (полностью учтена 1970)

115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,. 639937 (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)

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,82 9,946,433,6. 49006084097 (155 цифр)

2424833 × 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.759,. 504,705,008,092,818,711,693,940,737 (99 цифр) (полностью учтена в 1990 году)

F10

179.769.313.486.231.590.772.930... 304,835,356,329,624,224,137,217 (309 цифры)

45592577 × 6487031809 × 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)

F11

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 цифры) (полностью F49 с учетом данных с 1988 по 2010 год) 11 полностью учтены. Проект распределенных вычислений Fermat Search занимается поиском новых множителей чисел Ферма. Набор всех коэффициентов Ферма: A050922 (или, отсортированный, A023394 ) в OEIS.

Возможно, что единственными простыми числами этой формы являются 3, 5, 17, 257 и 65 537. Действительно, Боклан и Джон Х. Конвей опубликовали в 2016 году очень точный анализ, предполагающий, что вероятность существования другого простого числа Ферма составляет менее одного на миллиард.

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

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

По состоянию на январь 2020 года известно 351 простой множитель чисел Ферма, а 307 чисел Ферма - составные. Каждый год обнаруживается несколько новых факторов Ферма.

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

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

2 F n - 1 ≡ 1 (mod F n) {\ displaystyle 2 ^ {F_ {n} -1} \ Equiv 1 {\ pmod {F_ {n}}}}

{\ displaystyle 2 ^ {F_ {n} -1} \ эквивалент 1 {\ pmod {F_ {n}}}}

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

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

Другие теоремы о числах Ферма

Лемма. - Если n - целое положительное число,

an - bn = (а - б) ∑ k = 0 n - 1 акбн - 1 - k. {\ displaystyle a ^ {n} -b ^ {n} = (ab) \ sum _ {k = 0} ^ {n-1} a ^ {k} b ^ {n-1-k}.}

$a ^ nb ^ n = (ab) \ sum_ {k = 0} ^ {n-1} a ^ kb ^ {n-1-k}.$

Доказательство —
$(a - b) ∑ k = 0 n - 1 akbn - 1 - k = ∑ k = 0 n - 1 ak + 1 bn - 1 - k - ∑ k = 0 n - 1 akbn - k = ан + ∑ К знак равно 1 N - 1 АКБН - К - ∑ К = 1 N - 1 АКБН - К - БН = АН - БН {\ Displaystyle {\ begin {Выровнено} (ab) \ сумма _ {к = 0} ^ {n-1} a ^ {k} b ^ {n-1-k} = \ sum _ {k = 0} ^ {n-1} a ^ {k + 1} b ^ {n-1-k } - \ sum _ {k = 0} ^ {n-1} a ^ {k} b ^ {nk} \\ = a ^ {n} + \ sum _ {k = 1} ^ {n-1} a ^ {k} b ^ {nk} - \ sum _ {k = 1} ^ {n-1} a ^ {k} b ^ {nk} -b ^ {n} \\ = a ^ {n} -b ^ {n} \ end {align}}}$ ${\ displaystyle {\ begin {align ed} (ab) \ sum _ {k = 0} ^ {n-1} a ^ {k} b ^ {n-1-k} = \ sum _ {k = 0} ^ {n-1} a ^ {k + 1} b ^ {n-1-k} - \ sum _ {k = 0} ^ {n-1} a ^ {k} b ^ {nk} \\ = a ^ {n} + \ sum _ {k = 1} ^ {n-1} a ^ {k} b ^ {nk} - \ sum _ {k = 1} ^ {n-1} a ^ {k} b ^ {nk} - b ^ {n} \\ = a ^ {n} -b ^ {n} \ end {align}}}$

Теорема - Если $2 k + 1 {\ displaystyle 2 ^ {k} +1}$ $2 ^ {k} +1$ - нечетное простое число, то $k {\ displaystyle k}$ $k$ является степенью 2.
Доказательство -
Если $k {\ displaystyle k}$ $k$ является положительным целым числом, но не степенью двойки, оно должно иметь нечетный простой множитель $s>2 {\ displaystyle s>2}$ $s>2$ , и мы можем написать $k = rs {\ displaystyle k = rs}$ $k = rs$ где $1 ≤ r < k {\displaystyle 1\leq r$ $1 \ leq r <k$ .

По предыдущей лемме для положительного целого числа $m {\ displaystyle m}$ $m$ ,
$(a - b) ∣ ( am - bm) {\ displaystyle (ab) \ mid (a ^ {m} -b ^ {m})}$ $(ab) \ mid (a ^ mb ^ m)$
где $∣ {\ displaystyle \ mid}$ $\ mid$ означает «равномерно делит ". Подстановка $a = 2 r, b = - 1 {\ displaystyle a = 2 ^ {r}, b = -1}$ ${\ displaystyle a = 2 ^ {r}, b = -1}$ и $m = s {\ displaystyle m = s}$ $m = s$ и используя это $s {\ displaystyle s}$ $s$ нечетно,
$(2 r + 1) ∣ (2 rs + 1), {\ displaystyle (2 ^ {r} +1) \ mid (2 ^ {rs} +1),}$ $(2 ^ r + 1) \ mid (2 ^ {rs} +1),$
и, следовательно,
$(2 r + 1) ∣ (2 k + 1). {\ displaystyle (2 ^ {r} +1) \ mid (2 ^ {k} +1).}$ $(2 ^ {r} +1) \ mid (2 ^ {k} +1).$
Поскольку $1 < 2 r + 1 < 2 k + 1 {\displaystyle 1<2^{r}+1<2^{k}+1}$ $1 <2 ^ {r} +1 <2 ^ {k} +1$ , следует, что $2 k + 1 {\ displaystyle 2 ^ {k } +1}$ $2 ^ {k} +1$ не является простым. Следовательно, по противопоставлению $k {\ displaystyle k}$ $k$ должно быть степенью 2.

Теорема - простое число Ферма не может быть числом Вифериха. простое число.
Доказательство -
Мы покажем, является ли $p = 2 m + 1 {\ displaystyle p = 2 ^ {m} +1}$ $p = 2 ^ m + 1$ простым числом Ферма (и, следовательно, согласно вышеизложенному, m является степенью 2), тогда сравнение $2 p - 1 ≡ 1 mod p 2 {\ displaystyle 2 ^ {p-1} \ Equiv 1 {\ bmod {p ^ {2}} }}$ ${\ displaystyl e 2 ^ {p-1} \ Equiv 1 {\ bmod {p ^ {2}}}}$ не удерживается.

Начиная с $2 мес. | p - 1 {\ displaystyle 2m | p-1}$ $2m | p-1$ мы можем написать $p - 1 = 2 m λ {\ displaystyle p-1 = 2m \ lambda}$ $p-1 = 2m \ lambda$ . Если данное сравнение выполнено, то $p 2 | 2 2 m λ - 1 {\ displaystyle p ^ {2} | 2 ^ {2m \ lambda} -1}$ $p ^ 2 | 2 ^ {2m \ lambda} -1$ , и поэтому
$0 ≡ 2 2 m λ - 1 2 m + 1 = (2 m - 1) (1 + 2 2 m + 2 4 m + ⋯ + 2 2 (λ - 1) m) ≡ - 2 λ (mod 2 m + 1). {\ Displaystyle 0 \ Equiv {\ frac {2 ^ {2m \ lambda} -1} {2 ^ {m} +1}} = (2 ^ {m} -1) \ left (1 + 2 ^ {2m} + 2 ^ {4m} + \ cdots + 2 ^ {2 (\ lambda -1) m} \ right) \ Equiv -2 \ lambda {\ pmod {2 ^ {m} +1}}.}$ ${\ displaystyle 0 \ Equiv {\ frac {2 ^ {2m \ lambda} -1} {2 ^ {m} + 1}} = (2 ^ {m} -1) \ left (1 + 2 ^ {2m} + 2 ^ {4m} + \ cdots + 2 ^ {2 (\ lambda -1) m} \ right) \ эквив -2 \ lambda {\ pmod {2 ^ {m} +1}}.}$
Следовательно $2 м + 1 | 2 λ {\ displaystyle 2 ^ {m} +1 | 2 \ lambda}$ $2 ^ m + 1 | 2 \ lambda$ , и поэтому $2 λ ≥ 2 m + 1 {\ displaystyle 2 \ lambda \ geq 2 ^ {m} + 1}$ $2 \ lambda \ geq 2 ^ m + 1$ . Это приводит к $p - 1 ≥ m (2 m + 1) {\ displaystyle p-1 \ geq m (2 ^ {m} +1)}$ $p-1 \ geq m ( 2 ^ m + 1)$ , что невозможно, поскольку $m ≥ 2 {\ displaystyle m \ geq 2}$ $m \ geq 2$ .

Теорема (Эдуард Люкас ) - любой простой делитель p числа $F n = 2 2 n + 1 {\ displaystyle F_ { n} = 2 ^ {2 ^ {n}} + 1}$ ${\ displaystyle F_ {n} = 2 ^ {2 ^ {n}} + 1}$ имеет форму $k 2 n + 2 + 1 {\ displaystyle k2 ^ {n + 2} +1}$ $k2 ^ {n + 2} +1$ всякий раз, когда n>1.
Схема доказательства -
Пусть G p обозначает группу ненулевых целых чисел по модулю p при умножении, которая имеет порядок p − 1. Обратите внимание, что 2 (строго говоря, его изображение по модулю p) имеет мультипликативный порядок, равный $2 n + 1 {\ displaystyle 2 ^ {n + 1}}$ $2 ^ { n + 1}$ в G p (поскольку $2 2 n + 1 {\ displaystyle 2 ^ {2 ^ {n + 1}}}$ ${\ displaystyle 2 ^ {2 ^ {n + 1}}}$ - это квадрат $2 2 n {\ displaystyle 2 ^ {2 ^ { n}}}$ $2 ^ {2 ^ {n}}$ который равен −1 по модулю F n), так что по теореме Лагранжа, p - 1 делится на $2 n + 1 {\ displaystyle 2 ^ {n + 1}}$ $2 ^ {n + 1}$ и p имеет вид $k 2 n + 1 + 1 {\ displaystyle k2 ^ {n + 1} +1}$ ${\ displaystyle k2 ^ {n + 1 } +1}$ для некоторого целого k, как знал Эйлер. Эдуард Лукас пошел еще дальше. Поскольку n>1, указанное выше простое число p сравнимо с 1 по модулю 8. Следовательно (как было известно Карлу Фридриху Гауссу ), 2 является квадратичным вычетом по модулю p, т. Е. существует целое число a такое, что $p | a 2–2. {\ displaystyle p | a ^ {2} -2.}$ ${\ displaystyle p | a ^ {2} -2.}$ Тогда изображение a имеет порядок $2 n + 2 {\ displaystyle 2 ^ {n + 2}}$ $2 ^ {n + 2}$ в группе G p и (снова используя теорему Лагранжа) p - 1 делится на $2 n + 2 {\ displaystyle 2 ^ {n + 2}}$ $2 ^ {n + 2}$ и p имеет вид $s 2 n + 2 + 1 {\ displaystyle s2 ^ {n + 2} +1}$ ${\ displaystyle s2 ^ {n + 2} +1}$ для некоторого целого числа s.

Фактически, можно непосредственно увидеть, что 2 является квадратичным вычетом по модулю p, поскольку
$(1 + 2 2 n - 1) 2 ≡ 2 1 + 2 n - 1 (mod p). {\ displaystyle \ left (1 + 2 ^ {2 ^ {n-1}} \ right) ^ {2} \ Equiv 2 ^ {1 + 2 ^ {n-1}} {\ pmod {p}}.}$ ${\ displaystyle \ left (1 + 2 ^ {2 ^ {n-1}} \ right) ^ {2} \ Equiv 2 ^ {1 + 2 ^ {n-1}} {\ pmod {p}}.}$
Поскольку нечетная степень 2 является квадратичным вычетом по модулю p, то же самое и сама 2.
Связь с конструируемыми многоугольниками
Количество сторон известных конструктивных многоугольников, имеющих до 1000 сторон (жирный шрифт) или количество нечетных сторон (красный)
Карл Фридрих Гаусс разработал теорию гауссовских периодов в его Disquisitiones Arithmeticae и сформулировал достаточное условие для построения правильных многоугольников. Гаусс заявил, что это условие также необходимо, но не опубликовал доказательства. Пьер Ванцель дал полное доказательство необходимости в 1837 году. Результат известен как теорема Гаусса – Ванцеля :
n-сторонний правильный многоугольник может быть построен с помощью циркуля и линейки тогда и только тогда, когда n является произведением степени двойки и различных простых чисел Ферма: другими словами, если и только если n имеет вид n = 2p 1p2…ps, где k - неотрицательное целое число, а p i - разные простые числа Ферма.
Положительное целое число n имеет вышеуказанную форму тогда и только тогда, когда его totient φ (n) является степенью 2.
Применение чисел Ферма
Генерация псевдослучайных чисел
Простые числа Ферма особенно полезны при генерации псевдослучайных последовательностей чисел в диапазоне 1… N, где N - степень двойки. распространенный метод - взять любое начальное значение от 1 до P - 1, где P - простое число Ферма. Теперь умножьте это на число A, которое больше, чем квадратный корень из P, и является примитивным корнем по модулю P (т. Е. Это не квадратный остаток ). Затем возьмите результат по модулю P. Результатом является новое значение для ГСЧ.
$V j + 1 = (A × V j) mod P {\ displaystyle V_ {j + 1} = \ left (A \ times V_ {j} \ right) {\ bmod {P}}}$ $V_ {j + 1} = \ left (A \ times V_j \ right) \ bmod P$ (см. линейный конгруэнтный генератор, RANDU )
Это полезно в информатике, поскольку большинство структур данных имеют элементы с двумя возможными значениями. Например, байт имеет 256 (2) возможных значений (0–255). Поэтому для заполнения байта или байтов случайными значениями можно использовать генератор случайных чисел, который выдает значения 1–256, при этом байт принимает выходное значение -1. Очень большие простые числа Ферма представляют особый интерес в по этой причине шифрование данных. Этот метод выдает только псевдослучайные значения, поскольку после повторений P - 1 последовательность повторяется. Неправильно выбранный множитель может привести к тому, что последовательность будет повторяться раньше, чем P - 1.
Другие интересные факты
Число Ферма не может быть совершенным числом или частью пары дружественных чисел. (Luca 2000)

Серия обратных чисел всех простых чисел делители чисел Ферма сходятся. (Křížek, Luca Somer 2002)

Если n + 1 простое число, существует целое число m такое, что n = 2. Уравнение n + 1 = F (2+ m) выполняется в этом case.

Пусть наибольший простой множитель числа Ферма F n равен P (F n). Тогда
$P (F n) ≥ 2 n + 2 (4 n + 9) + 1. {\ displaystyle P (F_ {n}) \ geq 2 ^ {n + 2} (4n + 9) +1.}$ ${\ displaystyle P (F_ {n}) \ geq 2 ^ {n + 2} (4n + 9) +1. }$ (Grytczuk, Luca Wójtowicz 2001)
Обобщенные числа Ферма
Числа вида $a 2 n + b 2 n {\ displaystyle a ^ {2 ^ {\ overset {n } {}}} \! \! + b ^ {2 ^ {\ overset {n} {}}}}$ ${\ displaystyle a ^ {2 ^ {\ overset {n} {}}} \! \! + b ^ {2 ^ {\ overset {n} {}}}}$ с a, b любыми взаимно простыми целыми числами, a>b>0, называются обобщенными числами Ферма . Нечетное простое число p является обобщенным числом Ферма тогда и только тогда, когда p конгруэнтно 1 (mod 4). (Здесь мы рассматриваем только случай n>0, поэтому 3 = $2 2 0 + 1 {\ displaystyle 2 ^ {2 ^ {0}} \! + 1}$ ${\ displaystyle 2 ^ {2 ^ {0}} \! + 1}$ не является контрпримером.)

Примером вероятного простого числа этой формы является 124 + 57 (найдено Валерием Курышевым).

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

Если нам требуется n>0, тогда четвертая задача Ландау спрашивает, существует ли бесконечно много обобщенных простых чисел Ферма F n (а).
Обобщенные простые числа Ферма
Из-за простоты доказательства их простоты обобщенные простые числа Ферма в последние годы стали предметом исследований в области теории чисел. Многие из наибольших известных сегодня простых чисел являются обобщенными простыми числами Ферма.

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

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

(Для наименьшего числа $n {\ displaystyle n}$ $n$ такого, что $F n (a) {\ displaystyle F_ {n} (a)}$ $F_n (a)$ равно простое число, см. OEIS : A253242 )
$a {\ displaystyle a}$ $a$ числа $n {\ displaystyle n}$ $n$ . такие, что. $F n (a) {\ displaystyle F_ {n} (a)}$ $F_n (a)$ является простым $a {\ displaystyle a}$ $a$ числами $n {\ displaystyle n}$ $n$ . таким, что. $F n (a) {\ displaystyle F_ {n} (a)}$ $F_n (a)$ простое число $a {\ displaystyle a}$ $a$ числа $n {\ displaystyle n }$ $n$ . такой, что. $F n (a) {\ displaystyle F_ {n} (a)}$ $F_n (a)$ является простым $a {\ displaystyle a}$ $a$ числами $n {\ displaystyle n}$ $n$ . такой, что. $F n (a) {\ displaystyle F_ {n} (a)}$ $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,...
432>(невозможно)
b известное обобщенное (половинное) простое основание Ферма 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, 33061674265168783407491838112733711049957984290738112733711049957984290248348347381127337110499579842902148348389 5356445313
36 37, 1297
37 19
38
39 761, 1156721
40 41, 1601
41 31879515457326527173216321
42 43
43 5844100138801
44 197352587024076973231046657 752>45 23, 1013
46 47, 4477457, 46 + 1 (852 цифры: 214787904487... 289480994817)
47 11905643330881
48 5308417
49 1201
50
(см. Дополнительную информацию (четные базы до 1000), также см. Нечетные базы)

(Для наименьшего простого числа формы $F n (a, b) {\ displaystyle F_ {n} (a, b)}$ $F_n (a, б)$ (для нечетного $a + b {\ displaystyle a + b}$ $a + b$ ), см. также OEIS : A111635 )
$a {\ displaystyle a}$ $a$ $b {\ displaystyle b}$ $b$ numbers $n {\displaystyle n}$ $n$ such that. $a 2 n + b 2 n gcd ( a + b, 2) ( = F n ( a, b)) { \displaystyle {\frac {a^{2^{n}}+b^{2^{n}}}{\gcd(a+b,2)}}(=F_{n}(a,b)) }$ ${\ displaystyle {\ frac {a ^ {2 ^ {n}} + b ^ {2 ^ {n }}} {\ gcd (a + b, 2)}} (= F_ {n} (a, b))}$ . is prime
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 (none)
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,...
(For the smallest even base a such that $F n ( a) {\display style F_{n}(a)}$ $F_n (a)$ is prime, see OEIS : A056993 )
$n {\displaystyle n}$ $n$ bases a such that $F n ( a) {\displaystyle F_{n}(a)}$ $F_n (a)$ is prime (only consider even a) OEIS sequence
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,... A25
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 + 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 такие, что (2n) + 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 )
Более сложная теория может использоваться для прогнозирования количества оснований, для которых $F n (a) {\ displaystyle F_ {n} (a)}$ $F_n (a)$ будет простым при фиксированном $п {\ displaystyle n}$ $n$ . Примерно можно ожидать, что количество обобщенных простых чисел Ферма уменьшится вдвое по мере увеличения $n {\ displaystyle n}$ $n$ на 1.
Наибольшие известные обобщенные простые числа Ферма
Ниже приводится список из 5 самых больших известных обобщенных простых чисел Ферма. Все они мегапиксели. Вся топ-5 открыта участниками проекта PrimeGrid.
Ранг Простой ранг Простое число Обобщенная нотация Ферма Количество цифр Дата обнаружения исх.
1 14 1059094 + 1 F20(1059094) 6,317,602 ноябрь 2018 г.
2 15 919444 + 1 F20(919444) 6,253,210 сен 2017
3 31 3214654 + 1 F19(3214654) 3,411,613 Декабрь 2019
4 32 2985036 + 1 F19(2985036) 3,394,739 сен 2019
5 33 2877652 + 1 F19(2877652) 3,386,397 июнь 2019
На Prime Pages можно найти текущие 100 лучших обобщенных простых чисел Ферма.
См. также
Конструируемый многоугольник : какие правильные многоугольники можно построить, частично зависит от простых чисел Ферма.
Двойная экспоненциальная функция
Теорема Лукаса
Простое число Мерсенна
простое число Пирпонта
Проверка на простоту
Теорема Прота
Псевдопросто
Число Серпинского
Последовательность Сильвестра
Примечания
Литература
Голомб, SW (1 января 1963 г.), «О сумме обратных величин Числа Ферма и связанные с ними иррациональности », Canadian Journal of Математика, 15 : 475–478, doi : 10.4153 / CJM-1963-051-0
Grytczuk, A.; Лука, Ф. и Войтович, М. (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, New York: Springer, ISBN 978-0-387-95332-8 - Эта книга содержит обширный список ссылок
Křížek, Michal; Лука, Флориан и Сомер, Лоуренс (2002), «О сходимости серий обратных простых чисел, относящихся к числам Ферма» (PDF), Journal of Number Theory, 97 ( 1): 95–112, doi : 10.1006 / jnth.2002.2782
Лука, Флориан (2000), «Антиобщественное число Ферма», American Mathematical Ежемесячно, 107 (2): 171–173, doi : 10.2307 / 2589441, JSTOR 2589441
Рибенбойм, Paulo (1996), The New Book of Prime Number Records (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
Внешние ссылки
Fermat prime в Encyclopædia Bri tannica
Крис Колдуэлл, Главный глоссарий: число Ферма на Prime Pages.
Луиджи Морелли, История чисел Ферма
Джон Косгрейв, Объединение Числа Мерсенна и Ферма
Уилфрид Келлер, Простые факторы чисел Ферма
Вайсштейн, Эрик У. «Число Ферма». MathWorld.
Вайсштейн, Эрик У. «Ферма Прайм». MathWorld.
Вайсштейн, Эрик У. «Ферма Псевдопрайм». MathWorld.
Вайсштейн, Эрик У. «Обобщенное число Ферма». MathWorld.
Ив Галло, Обобщенный поиск Ферма Прайм
Марк С. Манасс, Полная факторизация девятого числа Ферма (исходное объявление)
Пейтон Хейслетт, Наибольшее известное обобщенное сообщение Fermat Prime

Последняя правка сделана 2021-05-20 14:09:34

Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).

Обратная связь: support@alphapedia.ru

Соглашение

О проекте