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

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

Нет. известных терминов	51
Предполагаемый нет. условий	Бесконечный[1]
Первые триместры	2, 3, 5, 13, 89, 233
Самый большой известный термин	F3340367
OEIS индекс	A001605 Индексы простых чисел Фибоначчи

А Простое число Фибоначчи это Число Фибоначчи то есть основной, тип целая последовательность простых чисел.

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

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

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

Нерешенная проблема в математике: Есть ли бесконечное количество простых чисел Фибоначчи? (больше нерешенных задач по математике)

Неизвестно, есть ли бесконечно много простых чисел Фибоначчи. При индексации начиная с F₁ = F₂ = 1, первые 34 - F_п для п значения (последовательность 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.

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

п = 130021, 148091, 201107, 397379, 433781, 590041, 593689, 604711, 931517, 1049897, 1285607, 1636007, 1803059, 1968721, 2904353, 3244369, 3340367.^[2]

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

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

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 году.^[4] Наибольшее известное вероятное простое число Фибоначчи - это F_3340367. Его обнаружил Анри Лифшиц в 2018 году.^[2]Ник Маккиннон доказал, что единственные числа Фибоначчи, которые также являются членами множества простые числа-близнецы 3, 5 и 13.^[5]

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

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

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

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

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

За п ≥ 3, F_п разделяет F_м если только п разделяет м.^[7]

Если мы предположим, что м это простое число п, и п меньше чем п, то ясно, что F_п, не может иметь общих делителей с предыдущими числами Фибоначчи.

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

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

• F_нк кратно F_k для всех значений n и k от 1 до.^[8] Можно с уверенностью сказать, что F_нк будет иметь "по крайней мере" такое же количество различных простых множителей, что и F_k. Все F_п не будет факторов F_k, но "хотя бы" одно новое характеристическое простое число из Теорема Кармайкла.

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

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

Если k = 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п	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
πп	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_п состоит в том, чтобы разделить простые множители всех предыдущих чисел Фибоначчи F_k для которого k | п.^[9]

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

Если п и q оба простые числа, то все множители F_pq характерны, кроме F_п и F_q.

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

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

${\displaystyle \pi _{pq}\geqslant {\begin{cases}\pi _{p}+\pi _{q}+1&p\neq q\\\pi _{p}+1&p=q\end{cases}}}$

Количество различных простых множителей чисел Фибоначчи с простым индексом напрямую связано с функцией подсчета. (последовательность 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
πп	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

Ранг Явления

Для прайма п, наименьший индекс ты > 0 такой, что F_ты делится на п называется ранг явления (иногда называют Точка входа Фибоначчи) из п и обозначен а(п). Ранг явления а(п) определена для каждого простого п.^[10] Ранг явления делит Период Пизано π (п) и позволяет определить все числа Фибоначчи, кратные п.^[11]

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

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

Особенно

${\displaystyle p^{2}\mid F_{a(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{cases}1&p\equiv \pm 1{\bmod {5}}\\-1&p\equiv \pm 2{\bmod {5}}\end{cases}}}$

Известно, что для п ≠ 2, 5, а(п) является делителем:^[12]

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

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

п	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 )

Если и только если прайм п находится в этой последовательности, то ${\displaystyle F_{p}}$ является простым числом Фибоначчи, и тогда и только тогда, когда 2п находится в этой последовательности, то ${\displaystyle L_{p}}$ это Лукас Прайм (куда ${\displaystyle L_{n}}$ это Последовательность Лукаса ), и тогда и только тогда, когда 2^п находится в этой последовательности, то ${\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 )

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

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

Рекомендации

1. http://mathworld.wolfram.com/FibonacciPrime.html
2. PRP Top Records, Искать: F (n). Проверено 5 апреля 2018.
3. Sloane's OEIS: A005478, OEIS: A001605
4. Крис Колдуэлл, База данных Prime: U (104911) от Prime Pages. Статус: число Фибоначчи, Доказательство простоты эллиптической кривой. Проверено 5 апреля 2018.
5. Н. Маккиннон, Проблема 10844, Амери. Математика. Ежемесячно 109, (2002), стр. 78
6. Пауло Рибенбойм, Мои номера, мои друзья, Springer-Verlag 2000
7. Уэллс 1986, стр.65.
8. Математическая магия чисел Фибоначчи Факторы чисел Фибоначчи
9. Джарден - Повторяющиеся последовательности, Том 1, Ежеквартальный журнал Фибоначчи, Брат У. Альфред
10. (последовательность A001602 в OEIS )
11. Джон Винсон (1963). "Отношение периода по модулю м в ранг Явления м в последовательности Фибоначчи " (PDF). Ежеквартальный отчет Фибоначчи. 1: 37–45.
12. Стивен Вайда. Числа Фибоначчи и Люка и золотое сечение: теория и приложения. Дуврские книги по математике.

внешняя ссылка

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