Pisanoperioden

Handling av de första 10 000 Pisanoperioderna.

I talteorin är den n: e Pisanoperioden , skriven som $π$ ( n ), den period med vilken sekvensen av Fibonacci-tal tagna modulo n upprepas. Pisanoperioder är uppkallade efter Leonardo Pisano, mer känd som Fibonacci . Förekomsten av periodiska funktioner i Fibonacci-tal noterades av Joseph Louis Lagrange 1774.

Definition

Fibonacci-talen är talen i heltalssekvensen :

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181. ... (sekvens A000045 i OEIS )

definieras av återfallsrelationen

F_{0}=0

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

\displaystyle F_{1}=1}

För vilket heltal n som helst är sekvensen av Fibonacci-tal F _i taget modulo n periodisk. Pisanoperioden, betecknad $π$ ( n ), är längden på perioden för denna sekvens. Till exempel börjar sekvensen av Fibonacci-tal modulo 3:

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, ... (sekvens A082115 i OEIS )

Denna sekvens har period 8, så $π$ (3) = 8.

Egenskaper

Med undantag för $π$ (2) = 3 är Pisanoperioden $π$ ( n ) alltid jämn . Ett enkelt bevis på detta kan ges genom att observera att $π$ ( n ) är lika med ordningen på Fibonacci-matrisen

\mathbf {Q} ={\begin{bmatrix}1&1\\1&0\end{bmatrix}}

i den allmänna linjära gruppen GL ₂ (ℤ _n ) av inverterbara 2 gånger 2 matriser i den finita ringen ℤ _n av heltal modulo n . Eftersom Q har determinant −1 är determinanten för Q ^{$π$ ( n )} (−1) ^{$π$ ( n )} , och eftersom denna måste vara lika med 1 i ℤ _n , är antingen n ≤ 2 eller $π$ ( n ) jämn.

Om m och n är coprime , då $π$ ( mn ) är den minsta gemensamma multipeln av $π$ ( m ) och $π$ ( n ), av den kinesiska restsatsen . Till exempel, $π$ (3) = 8 och $π$ (4) = 6 antyder $π$ (12) = 24. Således kan studiet av Pisanoperioder reduceras till det för Pisanoperioder med primpotenser q = p ^k , för k ≥ 1 .

Om p är primtal delar $π$ ( p ^{k )} p ^{k –1} $π$ ( p ) . Det är okänt om $\pi (p^{k})=p^{k-1}\pi (p)$ för varje primtal p och heltal k > 1. Varje primtal p som ger ett motexempel skulle nödvändigtvis vara ett Vägg–Sun–Sol primtal , och omvänt ger varje Vägg–Sun–Sun primtal p ett motexempel (uppsättning k = 2).

Så studiet av Pisano-perioder kan reduceras ytterligare till det av Pisano-perioder av primtal. I detta avseende är två primtal anomala. primtal 2 har en udda Pisanoperiod, och primtal 5 har period som är relativt mycket större än Pisanoperioden för något annat primtal. Kraftperioderna för dessa primtal är följande:

Om n = 2 ^k , då $π$ ( n ) = 3·2 ^{k –1} = 3·2 ^k / 2 = 3 n / 2 .
om n = 5 ^k , då $π$ ( n ) = 20·5 ^{k –1} = 20·5 ^k / 5 = 4 n .

Av dessa följer att om n = 2 · 5 ^k så $är π$ ( n ) = 6 n .

De återstående primtalen ligger alla i restklasserna $p\equiv \pm 1{\pmod {10}}$ eller $p\equiv \ 3:00 {\pmod {10}}$ . Om p är ett primtal som skiljer sig från 2 och 5, så innebär modulo p -analogen av Binets formel att $π$ ( p ) är multiplikationsordningen av en rot av $x 2 - x - 1$ modulo p . Om $p\equiv \pm 1{\pmod {10}}$ tillhör dessa rötter $\mathbb {F} _{p} =\mathbb {Z} /p\mathbb {Z}$ (genom kvadratisk reciprocitet ). Deras ordning, $π$ ( p ) är alltså en divisor av p − 1. Till exempel, $π$ (11) = 11 − 1 = 10 och $π$ (29) = (29 − 1)/2 = 14.

Om $p\equiv \pm 3{\pmod {10}},$ hör inte rötterna modulo p av $x 2 - x - 1 till$ $\mathbb {F} _{p}$ (genom kvadratisk ömsesidighet igen), och tillhör det finita fältet

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

Eftersom Frobenius-automorfismen $x\mapsto x^{p}$ byter ut dessa rötter, följer det att vi , genom att beteckna dem med r och s , har r ^p = s , och alltså r ^{p +1} = – 1. Det vill säga r ^{2( p +1)} = 1, och Pisanoperioden, som är ordningen för r , är kvoten av 2( p +1) med en udda divisor. Denna kvot är alltid en multipel av 4. De första exemplen på ett sådant p , för vilket $π$ ( p ) är mindre än 2( p +1), är $π$ (47) = 2(47 + 1)/3 = 32, $π$ (107) = 2(107 + 1)/3 = 72 och $π$ (113) = 2(113 + 1)/3 = 76. ( Se tabellen nedan )

Det följer av ovanstående resultat att om n = p ^k är en udda primpotens så att $π$ ( n ) > n , så är $π$ ( n )/4 ett heltal som inte är större än n . Den multiplikativa egenskapen hos Pisano-perioder innebär alltså att

$π$ ( n ) ≤ 6 n , med likhet om och endast om n = 2 · 5 ^r , för r ≥ 1.

De första exemplen är $π$ (10) = 60 och $π$ (50) = 300. Om n inte har formen 2 · 5 ^r , då $π$ ( n ) ≤ 4 n .

Tabeller

De första tolv Pisano-perioderna (sekvens A001175 i OEIS ) och deras cykler (med blanksteg före nollorna för läsbarhet) är (med hexadecimala cypher A och B för tio respektive elva):

n	π( n )	antal nollor i cykeln ( OEIS : A001176 )	cykel ( OEIS : A161553 )	OEIS- sekvens för cykeln
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

De första 144 Pisano-perioderna visas i följande tabell:

π( 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

Pisanoperioder av Fibonacci-tal

Om n = F (2k ) ( k ≥ 2), så är π( n ) = 4k ; om n = F (2 k + 1) ( k ≥ 2), så är π( n ) = 8 k + 4. Det vill säga om modulobasen är ett Fibonacci-tal (≥ 3) med ett jämnt index, är perioden två gånger indexet och cykeln har två nollor. Om basen är ett Fibonacci-tal (≥ 5) med ett udda index, är perioden fyra gånger indexet och cykeln har fyra nollor.

k	F ( k )	π( F ( k ))	första halvan av cykeln (för jämna k ≥ 4) eller första kvartalet av cykeln (för udda k ≥ 4) eller hela cykeln (för k ≤ 3) (med valda andra halvor eller andra kvartal)
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, 10971,
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, 10946, 10946,

Pisano-perioder av Lucas-tal

Om n = L (2k ) ( k ≥ 1), så är π( n ) = 8k ; om n = L (2 k + 1) ( k ≥ 1), så är π( n ) = 4 k + 2. Det vill säga om modulobasen är ett Lucas-tal (≥ 3) med ett jämnt index, är perioden fyra gånger indexet. Om basen är ett Lucas-tal (≥ 4) med ett udda index, är perioden två gånger indexet.

k	L ( k )	π( L ( k ))	första halvan av cykeln (för udda k ≥ 2) eller första kvartalet av cykeln (för jämna k ≥ 2) eller hela cykeln (för k = 1) (med valda andra halvor eller andra kvartal)
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, 10971,
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, 10946, 10946,

För jämn k har cykeln två nollor. För udda k har cykeln bara en nolla, och den andra halvan av cykeln, som naturligtvis är lika med delen till vänster om 0, består av omväxlande siffror F (2 m + 1) och n − F (2) m ), med m minskande.

Antal nollor i cykeln

Antalet förekomster av 0 per cykel är 1, 2 eller 4. Låt p vara talet efter den första nollan efter kombinationen 0, 1. Låt avståndet mellan nollorna vara q .

Det finns en nolla i en cykel, uppenbarligen, om p = 1. Detta är bara möjligt om q är jämnt eller n är 1 eller 2.
Annars finns det två nollor i en cykel om p ² ≡ 1. Detta är endast möjligt om q är jämnt.
Annars finns det fyra nollor i en cykel. Detta är fallet om q är udda och n inte är 1 eller 2.

För generaliserade Fibonacci-sekvenser (som uppfyller samma återfallsrelation, men med andra initiala värden, t.ex. Lucas-talen) är antalet förekomster av 0 per cykel 0, 1, 2 eller 4.

Förhållandet mellan Pisanoperioden av n och antalet nollor modulo n i cykeln ger rangen för uppenbarelse eller Fibonacci-ingångspunkt för n . Det vill säga minsta index k så att n delar F ( k ). Dom är:

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, ... ( sekvens A001177 i OEIS )

I Renaults tidning kallas antalet nollor "ordningen" av F mod m , betecknad $\omega (m)$ , och "rank of apparition" kallas "rank" och betecknas $\alpha (m)$ .

Enligt Walls gissning är $\alpha (p^{e})=p^{e-1}\alpha (p)$ . Om $m$ har primtalsfaktorisering $m=p_{1}^{e_{1}}p_{2}^{e_{2 }}\dots p_{n}^{e_{n}}$ sedan $\alpha (m)=\operatörsnamn {lcm} (\alpha (p_{1}^{e_{1}}),\alpha (p_{2}^{e_{2}}),\dots ,\alpha (p_{n}^{e_{n}}))$ .

Generaliseringar

Pisanoperioderna för Lucas- tal är

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, ... (sekvens A1062 i OEIS )

Pisanoperioderna för Pell-tal (eller 2-Fibonacci-tal) är

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, ... ( sekvens A175181 i OEIS )

Pisanoperioderna för 3-Fibonacci-tal är

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, ... ( sekvens A175182 i OEIS )

Pisanoperioderna för Jacobsthal-tal (eller (1,2)-Fibonacci-tal) är

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, ... ( sekvens A175286 i OEIS )

Pisanoperioderna för (1,3)-Fibonacci-tal är

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, ... sekvens A175291 i OEIS )

Pisanoperioderna för Tribonacci-tal (eller 3 - stegs Fibonacci-tal) är

1, 4, 13, 8, 31, 52, 48, 16, 39, 124, 110, 104, 168, 48, 403, 32, 96, 156, 360, 248, 624, 220, 50, 5, 5, 5, 5 168, 117, 48, 140, 1612, 331, 64, 1430, 96, 1488, 312, 469, 360, 2184, 496, 560, 624, 308, 2090, ... sekvens A046738 i OEIS )

Pisanoperioderna för Tetranacci-tal (eller 4 - stegs Fibonacci-tal) är

1, 5, 26, 10, 312, 130, 342, 20, 78, 1560, 120, 130, 84, 1710, 312, 40, 4912, 390. 0, 420, 234, 1710, 280, 1560, 61568, 80, 1560, 24560, 17784, 390, 1368, 34290, 1092, 1560, 240, 012, 820, 240, 120, 312 30, 103822, 520, ... ( sekvens A106295 i OEIS )

Se även generaliseringar av Fibonacci-tal .

Talteori

Pisanoperioder kan analyseras med hjälp av algebraisk talteori .

Låt $\pi _{k}(n)$ vara den n -te Pisanoperioden i k -Fibonacci-sekvensen F _k ( n ) ( k kan vara vilket naturligt tal som helst , dessa sekvenser definieras som F _k (0) = 0, F _k (1) = 1, och för alla naturliga tal n > 1, F _k ( n ) = kF _k ( n −1) + F _k ( n −2)). Om m och n är coprime så är ${\displaystyle \pi _{k}(m\cdot n)=\mathrm {lcm} (\pi _{k}(m),\pi _{k}(n))} ,$ av den kinesiska restsatsen : två tal är kongruenta modulo mn om och endast om de är kongruenta modulo m och modulo n , förutsatt att dessa senare är coprime. Till exempel, $\pi _{1}(3)=8$ och $\pi _{1}(4)=6,$ så $\pi _{1}(12 =3\cdot 4)=\mathrm {lcm} (\pi _{1}(3),\pi _{1}(4))=\mathrm {lcm} (8,6)=24.$ Således räcker för att beräkna Pisano-perioder för primpotenser $q=p^{n}.$ (Vanligtvis, $\pi _{k}(p^{n})=p ^{n-1}\cdot \pi _{k}(p)$ , om inte p är k - Wall–Sun–Sun primtal eller k -Fibonacci–Wieferich primtal, det vill säga p ² delar F _k ( p − 1) eller F _k ( p + 1), där F _k är k -Fibonacci-sekvensen, till exempel, 241 är ett 3-vägg-sol-sol-primtal, eftersom 241 ² delar F ₃ (242).)

För primtal p kan dessa analyseras genom att använda Binets formel :

F_{k}\left(n \right)={{\varphi _{k}^{n}-(k-\varphi _{k})^{n}} \över {\sqrt {k^{2}+4}}}={ {\varphi _{k}^{n}-(-1/\varphi _{k})^{n}} \över {\sqrt {k^{2}+4}}},\,

där

\varphi _{k}

är det k: te metalliska medelvärdet

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

Om k ² + 4 är en kvadratisk rest modulo p (där p > 2 och p inte delar k ² + 4), då ${\sqrt {k^{2}+ 4}},1/2,$ och $k/{\sqrt {k^{2}+4}}$ kan uttryckas som heltal modulo p , och därmed kan Binets formel uttryckas över heltal modulo p , och därmed delar Pisanoperioden totienten $\phi (p)=p-1$ , eftersom vilken potens som helst (som $\varphi _ {k}^{n}$ ) har perioddelning $\phi (p),$ eftersom detta är ordningen för gruppen av enheter modulo p .

För k = 1 inträffar detta först för p = 11, där 4 ² = 16 ≡ 5 (mod 11) och 2 · 6 = 12 ≡ 1 (mod 11) och 4 · 3 = 12 ≡ 1 (mod 11) så 4 = √ 5 , 6 = 1/2 och 1/ √ 5 = 3, vilket ger φ = (1 + 4) · 6 = 30 ≡ 8 (mod 11) och kongruensen

F_{1}\left(n\right)\equiv 3\cdot \left(8^{n}-4^{n}\right){\pmod {11}}.

Ett annat exempel, som visar att perioden korrekt kan dividera p − 1, är π ₁ (29) = 14.

Om k ² + 4 inte är en kvadratisk rest modulo p , så definieras Binets formel istället över det kvadratiska förlängningsfältet ( $\displaystyle (\mathbb {Z} /p)[{\ sqrt {k^{2}+4}}]}$ , som har p ² element och vars grupp av enheter alltså har ordningen p ² − 1, och därmed delar Pisanoperioden p ² − 1. Till exempel för p = 3 en har π ₁ (3) = 8 vilket är lika med 3 ² − 1 = 8; för p = 7 har man π ₁ (7) = 16, vilket korrekt delar 7 ² − 1 = 48.

Denna analys misslyckas för p = 2 och p är en divisor av den kvadratfria delen av k ² + 4, eftersom det i dessa fall är nolldelare , så man måste vara försiktig med att tolka 1/2 eller ${\ sqrt {k^{2}+4}}$ . För p = 2 är k ² + 4 kongruent med 1 mod 2 (för k udda), men Pisanoperioden är inte p − 1 = 1, utan snarare 3 (i själva verket är detta också 3 för jämn k ). För p delar den kvadratfria delen av k ² + 4 är Pisanoperioden π _k ( k ² + 4) = p ² − p = p ( p − 1), vilket inte delar p − 1 eller p ² − 1.

Fibonacci heltalssekvenser modulo n

Man kan betrakta Fibonacci-heltalssekvenser och ta dem modulo n , eller uttryckt annorlunda, betrakta Fibonacci-sekvenser i ringen Z / n Z . Perioden är en divisor av π( n ). Antalet förekomster av 0 per cykel är 0, 1, 2 eller 4. Om n inte är ett primtal inkluderar cyklerna de som är multiplar av cyklerna för divisorerna. Till exempel, för n = 10 inkluderar de extra cyklerna de för n = 2 multiplicerat med 5, och för n = 5 multiplicerat med 2.

Tabell över de extra cyklerna: (de ursprungliga Fibonacci-cyklerna är exkluderade) (med X och E för tio respektive elva)

n	multiplar	andra cykler	antal cykler (inklusive de ursprungliga Fibonacci-cyklerna)
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. 257, 28X76	14
12	0, 02246X42682X 0XX8628X64X2, 033693, 0448 0884, 066, 099639	07729E873X1E 0EEX974E3257, 1347E65E437X538E761783E2, 156E5491XE98516718952794	10

Antalet Fibonacci heltalscykler mod n är:

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, ... ( sekvens A015134 i OEIS )

Anteckningar

Bloom, DM (1965), "Periodicity in generalized Fibonacci-sekvenser", Amer. Matematik. Monthly , 72 (8): 856–861, doi : 10.2307/2315029 , JSTOR 2315029 , MR 0222015
Brent, Richard P. (1994), "On the periods of generalized Fibonacci sequences", Mathematics of Computation , 63 (207): 389–401, arXiv : 1004.5439 , Bibcode : 1994MaCom..63..389B : 7/01 , do..i . 2153583 , JSTOR 2153583 , MR 1216256 , S2CID 1038296
Engstrom, HT (1931), "Om sekvenser definierade av linjära återfallsrelationer", Trans. Am. Matematik. Soc. , 33 (1): 210–218, doi : 10.1090/S0002-9947-1931-1501585-5 , JSTOR 1989467 , MR 1501585
Falkar.; Plaza, A. (2009), " k -Fibonacci-sekvens modulo m ", Chaos, Solitons & Fractals , 41 (1): 497–504, Bibcode : 2009CSF....41..497F , doi : 10.1016/j. kaos.2008.02.014
Freyd, Peter; Brown, Kevin S. (1992), "Problem and Solutions: Solutions: E3410", Amer. Matematik. Monthly , 99 (3): 278–279, doi : 10.2307/2325076 , JSTOR 2325076
Laxton, RR (1969), "On groups of linear recurrences", Duke Mathematical Journal , 36 (4): 721–736, doi : 10.1215/S0012-7094-69-03687-4 , MR 0258781
Wall, DD (1960), "Fibonacci series modulo m", Amer. Matematik. Monthly , 67 (6): 525–532, doi : 10.2307/2309169 , JSTOR 2309169
Ward, Morgan (1931), "Det karakteristiska numret för en sekvens av heltal som uppfyller en linjär rekursionsrelation", Trans. Am. Matematik. Soc. , 33 (1): 153–165, doi : 10.1090/S0002-9947-1931-1501582-X , JSTOR 1989464
Ward, Morgan (1933), "The aritmetical theory of linear recurring series", Trans. Am. Matematik. Soc. , 35 (3): 600–628, doi : 10.1090/S0002-9947-1933-1501705-4 , JSTOR 1989851
Zierler, Neal (1959), "Linear recurring sequences", J. SIAM , 7 (1): 31–38, doi : 10.1137/0107003 , JSTOR 2099002 , MR 0101979

externa länkar

Fibonacci-sekvensen modulo m
En forskning för Fibonacci-tal
Fibonacci-sekvensen börjar med q, r modulo m
Johnson, Robert C., Fibonacci-resurser
på YouTube , en video med Dr James Grime och University of Nottingham