Простое число Фибоначчи - Fibonacci prime

Простое число Фибоначчи

Количество известных терминов	51
Предполагаемый нет. условий	Бесконечный
Первые триместры	2 , 3 , 5 , 13 , 89 , 233
Самый большой известный термин	F 3340367
Индекс OEIS

Фибоначчи простой является числом Фибоначчей , что это простой , типа целого числа последовательности штриха .

Первые простые числа Фибоначчи (последовательность A005478 в OEIS ):

2 , 3 , 5 , 13 , 89 , 233 , 1597, 28657, 514229, 433494437, 2971215073, ....

Известные простые числа Фибоначчи

Неизвестно, существует ли бесконечно много простых чисел Фибоначчи. При индексировании, начинающемся с F ₁ = F ₂ = 1 , первые 34 - это F _n для значений n (последовательность A001605 в OEIS ):

п = 3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47, 83, 131, 137, 359, 431, 433, 449, 509, 569, 571, 2971, 4723, 5387, 9311, 9677, 14431, 25561, 30757, 35999, 37511, 50833, 81839, 104911.

В дополнение к этим доказанным простым числам Фибоначчи были найдены вероятные простые числа для

n = 130021, 148091, 201107, 397379, 433781, 590041, 593689, 604711, 931517, 1049897, 1285607, 1636007, 1803059, 1968721, 2904353, 3244369, 3340367.

За исключением случая n = 4, все простые числа Фибоначчи имеют простой индекс, потому что если a делит b , то также делит (но не каждый простой индекс приводит к простому числу Фибоначчи). ${\ displaystyle F_ {a}}$${\ displaystyle F_ {b}}$

F _p является простым для 8 из первых 10 простых чисел p ; Исключение составляют F ₂ = 1 и F ₁₉ = 4181 = 37 × 113. Однако простые числа Фибоначчи, по-видимому, становятся реже по мере увеличения индекса. F _p является простым только для 26 из 1229 простых чисел p, меньших 10 000. Количество простых множителей в числах Фибоначчи с простым индексом:

0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 3, 2, 1, 1, 2, 2, 2, 3, 2, 2, 2, 1, 2, 4, 2, 3, 2, 2, 2, 2, 1, 1, 3, 4, 2, 4, 4, 2, 2, 3, 3, 2, 2, 4, 2, 4, 4, 2, 5, 3, 4, 3, 2, 3, 3, 4, 2, 2, 3, 4, 2, 4, 4, 4, 3, 2, 3, 5, 4, 2, 1, ... (последовательность A080345 в OEIS )

По состоянию на март 2017 года, самый большой известный определенный Фибоначчи премьер является F ₁₀₄₉₁₁ , с 21925 цифр. Это простое число было доказано Мэтью Стейном и Бук де Уотер в 2015 году. Наибольшее известное вероятное простое число Фибоначчи - F _3340367 . Его нашел Анри Лифшиц в 2018 году. Ник Маккиннон доказал, что единственными числами Фибоначчи, которые также являются простыми двойными числами, являются 3, 5 и 13.

Делимость чисел Фибоначчи

Штрихом делит тогда и только тогда , когда р является конгруэнтны до ± 1 по модулю 5, и р делит тогда и только тогда , когда оно сравнимо с ± 2 по модулю 5. (Для р = 5, F ₅ = 5 так 5 делит F ₅ ) ${\ displaystyle p}$${\ displaystyle F_ {p-1}}$ ${\ displaystyle F_ {p + 1}}$

Числа Фибоначчи с простым индексом p не имеют общих делителей больше 1 с предыдущими числами Фибоначчи из-за идентичности:

${\ displaystyle \ gcd (F_ {n}, F_ {m}) = F _ {\ gcd (n, m)},}$

откуда следует бесконечность простых чисел, поскольку делится хотя бы на одно простое число для всех . ${\ displaystyle F_ {p}}$${\ displaystyle p> 2}$

Для п  ^ 3 , Р _п делит Р _т тогда и только тогда , когда п делит т .

Если мы предположим, что m - простое число p , а n меньше p , то ясно, что F _p не может иметь общих делителей с предыдущими числами Фибоначчи.

${\ displaystyle \ gcd (F_ {p}, F_ {n}) = F _ {\ gcd (p, n)} = F_ {1} = 1.}$

Это означает, что F _p всегда будет иметь характеристические факторы или сам будет основным характеристическим фактором. Количество различных простых множителей каждого числа Фибоначчи можно описать простыми словами.

• F _{nk делится} на F _k для всех значений n и k, таких что n ≥ 1 и k ≥ 1. Можно с уверенностью сказать, что F _nk будет иметь «по крайней мере» такое же количество различных простых множителей, что и F _k . У всех F _{p не} будет факторов F _k , но будет «по крайней мере» одно новое характеристическое простое число из теоремы Кармайкла .

• Теорема Кармайкла применима ко всем числам Фибоначчи, за исключением четырех особых случаев: и если мы посмотрим на простые множители числа Фибоначчи, будет по крайней мере один из них, который никогда раньше не появлялся как множитель в каком-либо более раннем числе Фибоначчи. Пусть π _n - количество различных простых делителей F _n . (последовательность A022307 в OEIS )${\ Displaystyle F_ {1} = F_ {2} = 1, F_ {6} = 8}$${\ displaystyle F_ {12} = 144.}$

Если k | п тогда за исключением${\ displaystyle \ pi _ {n} \ geqslant \ pi _ {k} +1}$${\ displaystyle \ pi _ {6} = \ pi _ {3} = 1.}$

Если к = 1, а п является нечетным простое число, то 1 | р и${\ displaystyle \ pi _ {p} \ geqslant \ pi _ {1} + 1 = 1.}$

п	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21 год	22	23	24	25
F n	0	1	1	2	3	5	8	13	21 год	34	55	89	144	233	377	610	987	1597	2584	4181	6765	10946	17711	28657	46368	75025
π n	0	0	0	1	1	1	1	1	2	2	2	1	2	1	2	3	3	1	3	2	4	3	2	1	4	2

Первым шагом в нахождении характеристического частного любого F _n является разделение простых множителей всех предыдущих чисел Фибоначчи F _k, для которых k | п .

Оставшиеся точные частные - это простые множители, которые еще не появились.

Если p и q - простые числа, то все множители F _pq являются характеристическими, за исключением множителей F _p и F _q .

${\ displaystyle {\ begin {align} \ gcd (F_ {pq}, F_ {q}) & = F _ {\ gcd (pq, q)} = F_ {q} \\\ gcd (F_ {pq}, F_ {p}) & = F _ {\ gcd (pq, p)} = F_ {p} \ end {align}}}$

Следовательно:

${\ displaystyle \ pi _ {pq} \ geqslant {\ begin {case} \ pi _ {p} + \ pi _ {q} + 1 & p \ neq q \\\ pi _ {p} + 1 & p = q \ end { случаи}}}$

Количество различных простых множителей чисел Фибоначчи с простым индексом имеет прямое отношение к функции счета. (последовательность A080345 в OEIS )

п	2	3	5	7	11	13	17	19	23	29	31 год	37	41 год	43 год	47	53	59	61	67	71	73	79	83	89	97
π p	0	1	1	1	1	1	1	2	1	1	2	3	2	1	1	2	2	2	3	2	2	2	1	2	4

Ранг Явления

Для простого числа p наименьший индекс u > 0, такой что F _u делится на p , называется рангом появления (иногда называемым точкой входа Фибоначчи ) p и обозначается a ( p ). Ранг появления a ( p ) определяется для каждого простого числа p . Ранг явления делит период Пизано π ( p ) и позволяет определить все числа Фибоначчи, делящиеся на p .

Для делимости чисел Фибоначчи на степени простого числа и${\ Displaystyle п \ geqslant 3, п \ geqslant 2}$${\ displaystyle k \ geqslant 0}$

${\ displaystyle p ^ {n} \ mid F_ {a (p) kp ^ {n-1}}.}$

Особенно

${\ displaystyle p ^ {2} \ mid F_ {a (p) p}.}$

Простые числа Стена-Солнце-Солнце

Простое число p ≠ 2, 5 называется простым числом Фибоначчи – Вифериха или простым числом Стена – Солнце – Солнце, если где где ${\ displaystyle p ^ {2} \ mid F_ {q},}$

${\ displaystyle q = p- \ left ({\ frac {p} {5}} \ right)}$

и является символом Лежандра : ${\ displaystyle \ left ({\ tfrac {p} {5}} \ right)}$

${\ displaystyle \ left ({\ frac {p} {5}} \ right) = {\ begin {case} 1 & p \ Equiv \ pm 1 {\ bmod {5}} \\ - 1 & p \ Equiv \ pm 2 {\ bmod {5}} \ end {case}}}$

Известно, что при p ≠ 2, 5 a ( p ) является делителем:

${\ displaystyle p- \ left ({\ frac {p} {5}} \ right) = {\ begin {case} p-1 & p \ Equiv \ pm 1 {\ bmod {5}} \\ p + 1 & p \ Equiv \ pm 2 {\ bmod {5}} \ end {case}}}$

Для каждого простого числа p , которое не является простым числом Стена-Солнце-Солнце, как показано в таблице ниже: ${\ Displaystyle а (р ^ {2}) = па (р)}$

п	2	3	5	7	11	13	17	19	23	29	31 год	37	41 год	43 год	47	53	59	61
а ( р )	3	4	5	8	10	7	9	18	24	14	30	19	20	44 год	16	27	58	15
а ( п 2 )	6	12	25	56	110	91	153	342	552	406	930	703	820	1892 г.	752	1431	3422	915

Существование простых чисел Стена-Солнце-Солнце является предположительным .

Примитивная часть Фибоначчи

Примитивная часть чисел Фибоначчи

1, 1, 2, 3, 5, 4, 13, 7, 17, 11, 89, 6, 233, 29, 61, 47, 1597, 19, 4181, 41, 421, 199, 28657, 46, 15005, 521, 5777, 281, 514229, 31, 1346269, 2207, 19801, 3571, 141961, 321, 24157817, 9349, 135721, 2161, 165580141, 211, 433494437, 13201, 109441, ... (последовательность A061446 в OEIS )

Произведение примитивных простых множителей чисел Фибоначчи равно

1, 1, 2, 3, 5, 1, 13, 7, 17, 11, 89, 1, 233, 29, 61, 47, 1597, 19, 4181, 41, 421, 199, 28657, 23, 3001, 521, 5777, 281, 514229, 31, 1346269, 2207, 19801, 3571, 141961, 107, 24157817, 9349, 135721, 2161, 165580141, 211, 433494437, 13201, 109441, 64079, 2971215073, 1103, 598364773, 1525251 ... (последовательность A178763 в OEIS )

Первый случай более чем одного примитивного простого множителя равен 4181 = 37 × 113 для . ${\ displaystyle F_ {19}}$

В некоторых случаях примитивная часть имеет непримитивный простой фактор. Соотношение между двумя вышеуказанными последовательностями составляет

1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 13, 1, 1, .... (последовательность A178764 в OEIS )

В натуральных чисел п , для которых имеет ровно один примитивный простой фактор являются ${\ displaystyle F_ {n}}$

3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 43, 45, 47, 48, 51, 52, 54, 56, 60, 62, 63, 65, 66, 72, 74, 75, 76, 82, 83, 93, 94, 98, 105, 106, 108, 111, 112, 119, 121, 122, 123, 124, 125, 131, 132, 135, 136, 137, 140, 142, 144, 145, ... (последовательность A152012 в OEIS )

Для простого p , p находится в этой последовательности тогда и только тогда, когда является простым числом Фибоначчи, а 2 p находится в этой последовательности тогда и только тогда, когда является простым числом Люка (где - th число Люка ). Более того, 2 ⁿ находится в этой последовательности тогда и только тогда, когда является простым числом Люка. ${\ displaystyle F_ {p}}$${\ displaystyle L_ {p}}$${\ displaystyle L_ {p}}$${\ displaystyle p}$${\ displaystyle L_ {2 ^ {n-1}}}$

Количество примитивных простых множителей равно ${\ displaystyle F_ {n}}$

0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 1, 2, 1, 1, 3, 2, 3, 2, 2, 1, 2, 1, 1, 1, 2, 2, 2, 2, 3, 1, 1, 2, 2, 2, 2, 3, 2, 2, 2, 2, 1, 1, 3, 2, 4, 1, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 2, 2, 2, 2, 3, 1, 2, 1, 1, 1, 1, 1, 2, 2, 2, ... (последовательность A086597 в OEIS )

Наименее примитивные простые множители : ${\ displaystyle F_ {n}}$

1, 1, 2, 3, 5, 1, 13, 7, 17, 11, 89, 1, 233, 29, 61, 47, 1597, 19, 37, 41, 421, 199, 28657, 23, 3001, 521, 53, 281, 514229, 31, 557, 2207, 19801, 3571, 141961, 107, 73, 9349, 135721, 2161, 2789, 211, 433494437, 43, 109441, 139, 2971215073, 1103, 97, 101, ... (последовательность A001578 в OEIS )

Предполагается, что все простые множители примитивны, когда является простым числом. ${\ displaystyle F_ {n}}$${\ displaystyle n}$

Смотрите также

• Число Лукаса

использованная литература

внешние ссылки

• Вайсштейн, Эрик В. «Прайм Фибоначчи» . MathWorld .
• Р. Нотт Простые числа Фибоначчи
• Колдуэлл, Крис. Число Фибоначчи , простые Фибоначчи , и запись Фибоначчи простых чисел в самых Prime Страницы
• Факторизация первых 300 чисел Фибоначчи
• Факторизация чисел Фибоначчи и Лукаса
• Небольшая параллельная программа на Haskell для поиска вероятных простых чисел Фибоначчи на haskell.org