okres pisański

Fabuła pierwszych 10 000 okresów pisańskich.

W teorii liczb n - ty okres Pisano , zapisany jako $π$ ( n ), jest okresem , z którym powtarza się ciąg liczb Fibonacciego wzięty modulo n . Okresy Pisano zostały nazwane na cześć Leonarda Pisano, lepiej znanego jako Fibonacciego . Istnienie funkcji okresowych w liczbach Fibonacciego zauważył Joseph Louis Lagrange w 1774 roku.

Definicja

Liczby Fibonacciego to liczby w ciągu całkowitym :

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, ... (sekwencja A000045 w OEIS )

zdefiniowany przez relację rekurencyjną

{\ Displaystyle F_ {0} = 0}

{\ Displaystyle F_ {1} = 1}

{\ Displaystyle F_ {i} = F_ {i-1} + F_ {i-2}.}

Dla dowolnej liczby całkowitej n ciąg liczb Fibonacciego F _i wzięty modulo n jest okresowy. Okres Pisano, oznaczony jako $π$ ( n ), to długość okresu tego ciągu. Na przykład sekwencja liczb Fibonacciego modulo 3 zaczyna się:

0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, ... (sekwencja A082115 w OEIS )

Ta sekwencja ma okres 8, więc $π$ (3) = 8.

Nieruchomości

Z wyjątkiem $π$ (2) = 3, okres Pisano $π$ ( n ) jest zawsze parzysty . Prostym dowodem na to może być obserwacja, że $π$ ( n ) jest równe rzędowi macierzy Fibonacciego

{\ Displaystyle \ mathbf {Q} = {\ rozpocząć {bmatrix} 1 i 1 \\ 1 i 0 \ koniec {bmatrix}}}

w ogólnej grupie liniowej GL ₂ (ℤ _n ) odwracalnych macierzy 2 na 2 w skończonym pierścieniu ℤ _n liczb całkowitych modulo n . Ponieważ Q ma wyznacznik −1, wyznacznik Q ^{$π$ ( n )} to (−1) ^{$π$ ( n )} , a ponieważ to musi być równe 1 w ℤ _n , albo n ≤ 2 albo $π$ ( n ) jest parzysta.

Jeśli m i n są względnie pierwsze , to $π$ ( mn ) jest najmniejszą wspólną wielokrotnością π ( m ) i $π$ ( n ) zgodnie z chińskim twierdzeniem $o$ resztach . Na przykład $π$ (3) = 8 i $π$ (4) = 6 implikują $π$ (12) = 24. Tak więc badanie okresów pisańskich można sprowadzić do badania okresów pisańskich o potęgach pierwszych q = p ^k , dla k ≥ 1.

Jeśli p jest liczbą pierwszą , $π$ ( p ^k ) dzieli p ^{k –1} $π$ ( p ). Nie wiadomo, czy dla każdej liczby pierwszej p i liczby całkowitej ${\ Displaystyle \ pi (p ^ {k}) = p ^ {k-1} \ pi (p)}$ k > 1. Dowolna liczba pierwsza p dostarczająca kontrprzykładu z konieczności byłaby liczbą pierwszą Ściana – Słońce – Słońce i odwrotnie, każda liczba pierwsza Ściana – Słońce – Słońce daje kontrprzykład (zbiór k = 2).

Tak więc badanie okresów Pisano można dalej sprowadzić do badania okresów Pisano liczb pierwszych. Pod tym względem dwie liczby pierwsze są anomalne. Liczba pierwsza 2 ma dziwny okres Pisano, a liczba pierwsza 5 ma okres, który jest stosunkowo znacznie większy niż okres Pisano jakiejkolwiek innej liczby pierwszej. Okresy potęg tych liczb pierwszych są następujące:

Jeśli n = 2 ^k , to $π$ ( n ) = 3·2 ^{k –1} = 3·2 ^k / 2 = 3 n / 2 .
jeśli n = 5 ^k , to $π$ ( n ) = 20·5 ^{k –1} = 20·5 ^k / 5 = 4 n .

Z tego wynika, że jeśli n = 2 · 5 ^k to $π$ ( n ) = 6 n .

Wszystkie pozostałe liczby pierwsze leżą w klasach reszt lub $±$ $równoważnik \ pm 1 {$ \ . Jeśli p jest liczbą pierwszą różną od 2 i 5, to analog modulo p ze wzoru Bineta implikuje, że $π$ ( p ) jest rzędem multiplikatywnym a pierwiastek z $x 2 - x - 1$ modulo p . $\ pmod {10}}}$ { te korzenie należą do ${\ Displaystyle \ mathbb {F} _ {p} =\mathbb {Z} /p\mathbb {Z} }$ (przez kwadratową wzajemność ). Zatem ich rząd, $π$ ( p ) jest dzielnikiem p − 1. Na przykład $π$ (11) = 11 − 1 = 10 i $π$ (29) = (29 − 1)/2 = 14.

Jeśli ${\ Displaystyle p \ równoważnik \ pm 3 {\ pmod {10}},}$ korzenie modulo p od $x 2 - x - 1$ nie należą do ${\ displaystyle \ mathbb {F} _{p}}$ (znów przez kwadratową wzajemność) i należą do ciała skończonego

{\ Displaystyle \ mathbb {F} _ {p} [x] / (x ^ {2} -x-1).}

Ponieważ automorfizm Frobeniusa wymienia ^te pierwiastki , oznaczając je przez ^{p r} i s $,$ mamy r p s , a zatem = 1. To znaczy r ^{2( p +1)} = 1, a okres Pisano, który jest rzędu r , jest ilorazem 2 ( p +1) przez nieparzysty dzielnik. Iloraz ten jest zawsze wielokrotnością 4. Pierwszymi przykładami takiego p , dla którego $π$ ( p ) jest mniejsze niż 2( p +1), są $π$ (47) = 2(47 + 1)/3 = 32, $π$ (107) = 2(107 + 1)/3 = 72 i $π$ (113) = 2(113 + 1)/3 = 76. ( Patrz tabela poniżej )

Z powyższych wyników wynika, że jeśli n = p ^k jest nieparzystą potęgą pierwszą taką, że $π$ ( n ) > n , to $π$ ( n )/4 jest liczbą całkowitą nie większą niż n . Multiplikatywna właściwość okresów pisańskich implikuje to

$π$ ( n ) ≤ 6 n , z równością wtedy i tylko wtedy, gdy n = 2 · 5 ^r , dla r ≥ 1.

Pierwszymi przykładami są $π$ (10) = 60 i $π$ (50) = 300. Jeśli n nie jest postaci 2 · 5 ^r , to $π$ ( n ) ≤ 4 n .

Stoły

Pierwsze dwanaście okresów Pisano (sekwencja A001175 w OEIS ) i ich cykle (ze spacjami przed zerami dla czytelności) to (przy użyciu szesnastkowych cyfr A i B dla odpowiednio dziesięciu i jedenastu):

N	π( n )	liczba zer w cyklu ( OEIS : A001176 )	cykl ( OEIS : A161553 )	OEIS dla cyklu
1	1	1	0	A000004
2	3	1	011	A011655
3	8	2	0112 0221	A082115
4	6	1	011231	A079343
5	20	4	01123 03314 04432 02241	A082116
6	24	2	011235213415 055431453251	A082117
7	16	2	01123516 06654261	A105870
8	12	2	011235 055271	A079344
9	24	2	011235843718 088764156281	A007887
10	60	4	011235831459437 077415617853819 099875279651673 033695493257291	A003893
11	10	1	01123582A1	A105955
12	24	2	011235819A75 055A314592B1	A089911

Pierwsze 144 okresy Pisano przedstawiono w poniższej tabeli:

π( n )	+1	+2	+3	+4	+5	+6	+7	+8	+9	+10	+11	+12
0+	1	3	8	6	20	24	16	12	24	60	10	24
12+	28	48	40	24	36	24	18	60	16	30	48	24
24+	100	84	72	48	14	120	30	48	40	36	80	24
36+	76	18	56	60	40	48	88	30	120	48	32	24
48+	112	300	72	84	108	72	20	48	72	42	58	120
60+	60	30	48	96	140	120	136	36	48	240	70	24
72+	148	228	200	18	80	168	78	120	216	120	168	48
84+	180	264	56	60	44	120	112	48	120	96	180	48
96+	196	336	120	300	50	72	208	84	80	108	72	72
108+	108	60	152	48	76	72	240	42	168	174	144	120
120+	110	60	40	30	500	48	256	192	88	420	130	120
132+	144	408	360	36	276	48	46	240	32	210	140	24

Okresy Pisano liczb Fibonacciego

Jeśli n = F (2 k ) ( k ≥ 2), to π ( n ) = 4 k ; jeśli n = F (2 k + 1) ( k ≥ 2), to π ( n ) = 8 k + 4. To znaczy, jeśli podstawą modulo jest liczba Fibonacciego (≥ 3) z parzystym indeksem, okres wynosi dwa razy indeks, a cykl ma dwa zera. Jeśli podstawą jest liczba Fibonacciego (≥ 5) z nieparzystym indeksem, okres jest czterokrotnością indeksu, a cykl ma cztery zera.

k	fa ( k )	π( fa ( k ))	pierwsza połowa cyklu (dla parzystego k ≥ 4) lub pierwsza ćwiartka cyklu (dla nieparzystego k ≥ 4) lub cały cykl (dla k ≤ 3) (z wybranymi drugimi połówkami lub drugimi ćwiartkami)
1	1	1	0
2	1	1	0
3	2	3	0, 1, 1
4	3	8	0, 1, 1, 2, (0, 2, 2, 1)
5	5	20	0, 1, 1, 2, 3, (0, 3, 3, 1, 4)
6	8	12	0, 1, 1, 2, 3, 5, (0, 5, 5, 2, 7, 1)
7	13	28	0, 1, 1, 2, 3, 5, 8, (0, 8, 8, 3, 11, 1, 12)
8	21	16	0, 1, 1, 2, 3, 5, 8, 13, (0, 13, 13, 5, 18, 2, 20, 1)
9	34	36	0, 1, 1, 2, 3, 5, 8, 13, 21, (0, 21, 21, 8, 29, 3, 32, 1, 33)
10	55	20	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, (0, 34, 34, 13, 47, 5, 52, 2, 54, 1)
11	89	44	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, (0, 55, 55, 21, 76, 8, 84, 3, 87, 1, 88)
12	144	24	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, (0, 89, 89, 34, 123, 13, 136, 5, 141, 2, 143, 1)
13	233	52	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
14	377	28	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
15	610	60	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377
16	987	32	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
17	1597	68	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
18	2584	36	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
19	4181	76	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584
20	6765	40	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
21	10946	84	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
22	17711	44	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
23	28657	92	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711
24	46368	48	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657

Okresy Pisano liczb Lucasa

Jeśli n = L (2 k ) ( k ≥ 1), to π ( n ) = 8 k ; jeśli n = L (2 k + 1) ( k ≥ 1), to π ( n ) = 4 k + 2. To znaczy, jeśli podstawą modulo jest liczba Lucasa (≥ 3) z parzystym indeksem, okres wynosi czterokrotność indeksu. Jeśli podstawą jest liczba Lucasa (≥ 4) z nieparzystym indeksem, okres jest dwa razy większy od indeksu.

k	L ( k )	π( L ( k ))	pierwsza połowa cyklu (dla nieparzystego k ≥ 2) lub pierwsza ćwiartka cyklu (dla parzystego k ≥ 2) lub cały cykl (dla k = 1) (z wybranymi drugimi połówkami lub drugimi ćwiartkami)
1	1	1	0
2	3	8	0, 1, (1, 2)
3	4	6	0, 1, 1, (2, 3, 1)
4	7	16	0, 1, 1, 2, (3, 5, 1, 6)
5	11	10	0, 1, 1, 2, 3, (5, 8, 2, 10, 1)
6	18	24	0, 1, 1, 2, 3, 5, (8, 13, 3, 16, 1, 17)
7	29	14	0, 1, 1, 2, 3, 5, 8, (13, 21, 5, 26, 2, 28, 1)
8	47	32	0, 1, 1, 2, 3, 5, 8, 13, (21, 34, 8, 42, 3, 45, 1, 46)
9	76	18	0, 1, 1, 2, 3, 5, 8, 13, 21, (34, 55, 13, 68, 5, 73, 2, 75, 1)
10	123	40	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, (55, 89, 21, 110, 8, 118, 3, 121, 1, 122)
11	199	22	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, (89, 144, 34, 178, 13, 191, 5, 196, 2, 198, 1)
12	322	48	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, (144, 233, 55, 288, 21, 309, 8, 317, 3, 320, 1, 321)
13	521	26	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
14	843	56	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
15	1364	30	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377
16	2207	64	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
17	3571	34	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
18	5778	72	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
19	9349	38	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584
20	15127	80	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
21	24476	42	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
22	39603	88	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
23	64079	46	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711
24	103682	96	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657

Dla parzystego k cykl ma dwa zera. Dla nieparzystego k cykl ma tylko jedno zero, a druga połowa cyklu, która jest oczywiście równa części po lewej stronie 0, składa się na przemian z liczb F (2 m + 1) i n − F (2 m ), przy czym m maleje.

Liczba zer w cyklu

Liczba wystąpień 0 na cykl wynosi 1, 2 lub 4. Niech p będzie liczbą po pierwszym 0 po kombinacji 0, 1. Niech odległość między zerami będzie równa q .

W cyklu jest oczywiście jedno 0, jeśli p = 1. Jest to możliwe tylko wtedy, gdy q jest parzyste lub n wynosi 1 lub 2.
W przeciwnym razie w cyklu są dwa zera, jeśli p ² ≡ 1. Jest to możliwe tylko wtedy, gdy q jest parzyste.
W przeciwnym razie cykl składa się z czterech zer. Dzieje się tak, gdy q jest nieparzyste, a n nie jest równe 1 ani 2.

Dla uogólnionych ciągów Fibonacciego (spełniających tę samą relację rekurencyjną, ale z innymi wartościami początkowymi, np. liczbami Lucasa) liczba wystąpień 0 na cykl wynosi 0, 1, 2 lub 4.

Stosunek okresu Pisano n do liczby zer modulo n w cyklu daje rangę pojawienia się lub punkt wejścia Fibonacciego n . To znaczy najmniejszy indeks k taki, że n dzieli F ( k ). Oni są:

1, 3, 4, 6, 5, 12, 8, 6, 12, 15, 10, 12, 7, 24, 20, 12, 9, 12, 18, 30, 8, 30, 24, 12, 25, 21, 36, 24, 14, 60, 30, 24, 20, 9, 40, 12, 19, 18, 28, 30, 20, 24, 44, 30, 60, 24, 16, 12, ... ( sekwencja A001177 w OEIS )

$jako$ Renault liczba zer nazywana jest „porządkiem” , oznaczona , a „ranga objawienia” nazywana jest „rangą” i oznaczona ${\ Displaystyle \ alfa (m)}$ .

Zgodnie z przypuszczeniem Walla, ${\ Displaystyle \ alfa (p ^ {e}) = p ^ {e-1} \ alfa (p)}$ . m $=$ ${2} ^ {e_ {2} }}\kropki p_{n}^{e_{n}}}$ ^ { e_ {1}} następnie ${\ Displaystyle \ alfa (m) = \ operatorname {lcm} (\ alfa (p_{1}^{e_{1}}),\alfa (p_{2}^{e_{2}}),\kropki ,\alfa (p_{n}^{e_{n}}))}$ .

Uogólnienia

Okresy Pisano liczb Lucasa to

1, 3, 8, 6, 4, 24, 16, 12, 24, 12, 10, 24, 28, 48, 8, 24, 36, 24, 18, 12, 16, 30, 48, 24, 20, 84, 72, 48, 14, 24, 30, 48, 40, 36, 16, 24, 76, 18, 56, 12, 40, 48, 88, 30, 24, 48, 32, ... (sekwencja A106291 w OIS )

Okresy Pisano liczb Pella (lub liczb 2-Fibonacciego) są

1, 2, 8, 4, 12, 8, 6, 8, 24, 12, 24, 8, 28, 6, 24, 16, 16, 24, 40, 12, 24, 24, 22, 8, 60, 28, 72, 12, 20, 24, 30, 32, 24, 16, 12, 24, 76, 40, 56, 24, 10, 24, 88, 24, 24, 22, 46, 16, ... ( sekwencja A175181 w OEIS )

Okresy Pisano liczb 3-Fibonacciego to

1, 3, 2, 6, 12, 6, 16, 12, 6, 12, 8, 6, 52, 48, 12, 24, 16, 6, 40, 12, 16, 24, 22, 12, 60, 156, 18, 48, 28, 12, 64, 48, 8, 48, 48, 6, 76, 120, 52, 12, 28, 48, 42, 24, 12, 66, 96, 24, ... ( sekwencja A175182 w OEIS )

Okresy Pisano liczb Jacobsthal (lub (1,2) - Fibonacciego) są

1, 1, 6, 2, 4, 6, 6, 2, 18, 4, 10, 6, 12, 6, 12, 2, 8, 18, 18, 4, 6, 10, 22, 6, 20, 12, 54, 6, 28, 12, 10, 2, 30, 8, 12, 18, 36, 18, 12, 4, 20, 6, 14, 10, 36, 22, 46, 6, ... ( sekwencja A175286 w OEIS )

Okresy Pisano liczb (1,3)-Fibonacciego to

1, 3, 1, 6, 24, 3, 24, 6, 3, 24, 120, 6, 156, 24, 24, 12, 16, 3, 90, 24, 24, 120, 22, 6, 120, 156, 9, 24, 28, 24, 240, 24, 120, 48, 24, 6, 171, 90, 156, 24, 336, 24, 42, 120, 24, 66, 736, 12, ... ( sekwencja A175291 w OEIS )

Okresy Pisano liczb Tribonacciego (lub 3-stopniowych liczb Fibonacciego) są

1, 4, 13, 8, 31, 52, 48, 16, 39, 124, 110, 104, 168, 48, 403, 32, 96, 156, 360, 248, 624, 220, 553, 208, 155, 168, 117, 48, 140, 1612, 331, 64, 1430, 96, 1488, 312, 469, 360, 2184, 496, 560, 624, 308, 440, 1209, 2212, 46, 416, ... ( sekwencja A046738 w OEIS )

Okresy Pisano liczb Tetranacciego (lub 4-stopniowych liczb Fibonacciego) są

1, 5, 26, 10, 312, 130, 342, 20, 78, 1560, 120, 130, 84, 1710, 312, 40, 4912, 390, 6858, 1560, 4446, 120, 12166, 260, 156 0, 420, 234, 1710, 280, 1560, 61568, 80, 1560, 24560, 17784, 390, 1368, 34290, 1092, 1560, 240, 22230, 162800, 120, 312, 608 30, 103822, 520, ... ( sekwencja A106295 w OEIS )

Zobacz także uogólnienia liczb Fibonacciego .

Teoria liczb

Okresy Pisano można analizować za pomocą algebraicznej teorii liczb .

Niech będzie $) {\ Displaystyle \ pi _ {k} (n)$ -tym okresem Pisano ciągu k -Fibonacciego fa ( k może być dowolną liczbą naturalną , ciągi te są zdefiniowane jako π k ( n _} F _k (0) = 0, F _k (1) = 1 i dla dowolnej liczby naturalnej n > 1, F _k ( n ) = kF _k ( n −1) + fa _k ( n −2)). Jeśli m i n są względnie pierwsze , to ${\ Displaystyle \ pi _ {k} (m \ cdot n) = \ operatorname {lcm} (\pi _{k}(m),\pi _{k}(n))}$ , według chińskiego twierdzenia o resztach : dwie liczby są przystające modulo mn wtedy i tylko wtedy, gdy są przystające modulo m i modulo n , zakładając, że te ostatnie są względnie pierwsze. Na przykład ${\ Displaystyle \ pi _ {1} (3) = 8}$ i ${\ Displaystyle \ pi _ {1} (4) = 6,}$ więc ${\ Displaystyle \ pi _ {1} (12 = 3 \ cdot 4) = \ operatorname {lcm} (\ pi _ { 1}(3),\pi _{1}(4))=\mathrm {lcm} (8,6)=24.}$ Zatem wystarczy obliczyć okresy Pisano dla potęg pierwszych ${\ Displaystyle q = p ^ {n}.}$ (Zwykle ${\ Displaystyle \ pi _ {k} (p ^ {n}) = p ^ {n-1} \ cdot \ pi _ {k} (p)} , chyba$ że p jest k - Wall–Sun–Sun prim lub k -Fibonacciego–Wiefericha prim, czyli p ² dzieli F _k ( p − 1) lub F _k ( p + 1), gdzie F _k jest k - Ciąg Fibonacciego, na przykład, 241 jest liczbą pierwszą 3-ściana-słońce-słońce, ponieważ 241 ² dzieli F ₃ (242).)

W przypadku liczb pierwszych p można je przeanalizować za pomocą wzoru Bineta :

{\ Displaystyle F_ {k} \ lewo (n \right)={{\varphi _{k}^{n}-(k-\varphi _{k})^{n}} \over {\sqrt {k^{2}+4}}}={ {\varphi _{k}^{n}-(-1/\varphi _{k})^{n}} \over {\sqrt {k^{2}+4}}},\,}

gdzie jest

_

tą średnią metaliczną

{\ Displaystyle \ varphi _ {k} = {\ Frac {k + {\ sqrt {k ^ {2} + 4}}} {2}}.}

Jeśli k ² + 4 jest resztą kwadratową modulo p (gdzie p > 2 i p nie dzieli k ² + 4), to ${\ Displaystyle {\ sqrt {k ^ {2} + 4}}, 1/2,}$ i ${\ Displaystyle k / {\ sqrt {k ^ {2} + 4}}}$ można wyrazić jako liczby całkowite modulo p $a$ Bineta można wyrazić na liczbach całkowitych modulo ${\ Displaystyle \ varphi _ {k} ^ {n}}$ okres Pisano dzieli totient , ponieważ jak ) ma okres dzielący ${\ Displaystyle \ phi (p)},$ ponieważ jest to kolejność grupy jednostek modulo p .

Dla k = 1, to najpierw zachodzi dla p = 11, gdzie 4 ² = 16 ≡ 5 (mod 11) i 2 · 6 = 12 ≡ 1 (mod 11) i 4 · 3 = 12 ≡ 1 (mod 11) więc 4 = √ 5 , 6 = 1/2 i 1/ √ 5 = 3, dając φ = (1 + 4) · 6 = 30 ≡ 8 (mod 11) i kongruencja

{\ Displaystyle F_ {1} \ lewo (n \ prawo) \ równoważnik 3 \ cdot \ lewo (8 ^ {n} -4 ^ {n} \ prawo) {\ pmod {11}}.}

Innym przykładem, który pokazuje, że okres można właściwie podzielić p − 1, jest π ₁ (29) = 14.

Jeśli k ² + 4 nie jest kwadratową resztą modulo p , to zamiast tego wzór Bineta jest zdefiniowany na kwadratowym polu rozszerzenia ${\ Displaystyle (\ mathbb {Z} / p) [{\ sqrt {k^{2}+4}]}$ , który ma elementy p ² i którego grupa jednostek ma zatem rząd p ² − 1, a zatem okres Pisano dzieli p ² − 1. Na przykład dla p = 3 jeden ma π ₁ (3) = 8, co równa się 3 ² − 1 = 8; dla p = 7 mamy π ₁ (7) = 16, co właściwie dzieli 7 ² − 1 = 48.

Ta analiza kończy się niepowodzeniem dla p = 2, a p jest dzielnikiem wolnej od kwadratu części k ² + 4, ponieważ w tych przypadkach są dzielniki zera , więc należy zachować ostrożność przy interpretacji 1/2 lub ${\ displaystyle {\ sqrt {k^{2}+4}}}$ . Dla p = 2, k ² + 4 jest zgodne z 1 mod 2 (dla k nieparzystego), ale okres Pisano to nie p - 1 = 1, ale raczej 3 (w rzeczywistości jest to również 3 dla parzystego k ). Dla p dzieli wolną od kwadratów część k ² + 4, okres Pisano to π _k ( k ² + 4) = p ² - p = p ( p - 1), który nie dzieli p - 1 ani p ² - 1.

Ciągi całkowite Fibonacciego modulo n

Można rozważać ciągi liczb całkowitych Fibonacciego i brać je modulo n , lub inaczej, rozważać ciągi Fibonacciego w pierścieniu Z / n Z . Okres jest dzielnikiem π( n ). Liczba wystąpień 0 na cykl wynosi 0, 1, 2 lub 4. Jeśli n nie jest liczbą pierwszą, cykle obejmują te, które są wielokrotnościami cykli dla dzielników. Na przykład dla n = 10 dodatkowe cykle obejmują cykle dla n = 2 pomnożone przez 5, a dla n = 5 pomnożone przez 2.

Tabela dodatkowych cykli: (z wyłączeniem oryginalnych cykli Fibonacciego) (przy użyciu X i E odpowiednio dla dziesięciu i jedenastu)

N	wielokrotności	inne cykle	liczba cykli (w tym oryginalne cykle Fibonacciego)
1			1
2	0		2
3	0		2
4	0, 022	033213	4
5	0	1342	3
6	0, 0224 0442, 033		4
7	0	02246325 05531452, 03362134 04415643	4
8	0, 022462, 044, 066426	033617 077653, 134732574372, 145167541563	8
9	0, 0336 0663	022461786527 077538213472, 044832573145 055167426854	5
10	0, 02246 06628 08864 04482, 055, 2684	134718976392	6
11	0	02246X5492, 0336942683, 044819X874, 055X437X65, 0661784156, 0773X21347, 0885279538, 0997516729, 0XX986391X, 14593, 18964X 3257, 28X76	14
12	0, 02246X42682X 0XX8628X64X2, 033693, 0448 0884, 066, 099639	07729E873X1E 0EEX974E3257, 1347E65E437X538E761783E2, 156E5491XE98516718952794	10

Liczba cykli liczb całkowitych Fibonacciego mod n to:

1, 2, 2, 4, 3, 4, 4, 8, 5, 6, 14, 10, 7, 8, 12, 16, 9, 16, 22, 16, 29, 28, 12, 30, 13, 14, 14, 22, 63, 24, 34, 32, 39, 34, 30, 58, 19, 86, 32, 52, 43, 58, 22, 78, 39, 46, 70, 102, ... ( sekwencja A015134 w OEIS )

Notatki

Bloom, DM (1965), „Częstotliwość w uogólnionych ciągach Fibonacciego”, Amer. Matematyka Miesięczny , 72 (8): 856–861, doi : 10.2307/2315029 , JSTOR 2315029 , MR 0222015
Brent, Richard P. (1994), „O okresach uogólnionych ciągów Fibonacciego”, Mathematics of Computation , 63 (207): 389–401, arXiv : 1004,5439 , Bibcode : 1994MaCom..63..389B , doi : 10,2307/ 2153583 , JSTOR 2153583 , MR 1216256 , S2CID 1038296
Engstrom, HT (1931), „O sekwencjach określonych przez liniowe relacje powtarzalności”, Trans. Jestem. Matematyka soc. , 33 (1): 210–218, doi : 10.1090/S0002-9947-1931-1501585-5 , JSTOR 1989467 , MR 1501585
Sokół, S.; Plaza, A. (2009), " k -sekwencja Fibonacciego modulo m ", Chaos, solitony i fraktale , 41 (1): 497–504, Bibcode : 2009CSF....41..497F , doi : 10.1016/j. chaos.2008.02.014
Freyd, Piotr; Brown, Kevin S. (1992), „Problemy i rozwiązania: rozwiązania: E3410”, Amer. Matematyka Miesięczny , 99 (3): 278–279, doi : 10.2307/2325076 , JSTOR 2325076
Laxton, RR (1969), „O grupach nawrotów liniowych”, Duke Mathematical Journal , 36 (4): 721–736, doi : 10.1215 / S0012-7094-69-03687-4 , MR 0258781
Wall, DD (1960), „szereg Fibonacciego modulo m”, Amer. Matematyka Miesięczny , 67 (6): 525–532, doi : 10.2307/2309169 , JSTOR 2309169
Ward, Morgan (1931), „Liczba charakterystyczna ciągu liczb całkowitych spełniających liniową relację rekurencji”, tłum. Jestem. Matematyka soc. , 33 (1): 153–165, doi : 10.1090/S0002-9947-1931-1501582-X , JSTOR 1989464
Ward, Morgan (1933), „Teoria arytmetyczna liniowych szeregów powtarzających się”, tłum. Jestem. Matematyka soc. , 35 (3): 600–628, doi : 10.1090/S0002-9947-1933-1501705-4 , JSTOR 1989851
Zierler , Neal ( 1959 ) _ _ _ _ _ _ _ _

Linki zewnętrzne

Sekwencja Fibonacciego modulo m
Badanie liczb Fibonacciego
Ciąg Fibonacciego zaczyna się od q, r modulo m
Johnson, Robert C., zasoby Fibonacciego
na YouTube , wideo z udziałem dr Jamesa Grime'a i Uniwersytetu w Nottingham