\require{AMSmath}

Fibonacci getal modulo zijn index: F_p (mod p)

Een paar jaar geleden ontdekte ik de bekende Fibonacci rijen. Toen heb ik wat gepuzzeld en op internet gekeken maar kon nergens bewijs vinden voor een vermoeden dat ik had. Een paar dagen geleden vond ik dit forum en dacht ik het hier maar te vragen.

Ik ken een aantal eigenschappen van de rij ivm de ggd van termen, voorkomen van delers, identiteiten zoals F_n+1.F_n-1-F_n²=(-1)ⁿ en zo meer.
Het was me opgevallen dat voor elk priemgetal p, F_p²=1 (mod p). Hoezeer ik ook puzzel ik kom er niet uit, en ik kan al helemaal geen regelmaat vinden wanneer F_p (mod p) nu 1 of -1(mod p) is.
Er zijn nog veel meer van dat soort dingetjes maar van deze twee zou ik graag een bewijs willen zien, als dat bestaat.

Alvast bedankt,
Jasper

Jasper
Leerling bovenbouw havo-vwo - woensdag 5 november 2003

Antwoord

Hoi,

Heel mooie...

Gegeven:
F₀=0, F₁=1 en F_i=F_i-1+F_i-2.

Te bewijzen:
Als p priem is (en verschillend van 5), dan is F_p=1 of -1 (mod p)

Bewijs:
Dat de eigenschap geldt voor p=2 en 3 zie je zo.
Voor p=5, is F_p=5 en klopt de eigenschap dus niet. We bekijken verder enkel p5 (en dus oneven).

Je kent wellicht de Formule van Binet. Met behulp van het Binomium van Newton kan je die machten van 1+Ö5 en 1-Ö5 als sommaties schrijven en het leuke ervan is dat je de helft van de termen kan schrappen. Bovendien raak je ook die vervelende Ö5 in de noemer kwijt. Met m=(p-1)/2 krijgen we zo:
F_p=sum(C(p,2j+1).5^j:j=0..m)/2^p-1 (C: combinaties van p per 2j+1)

We bekijken nu F_p (mod p): omdat ggd(p,2)=1, is 2^p-1=1(mod p). We hebben dus:
2^p-1.F_p=sum(C(p,2j+1).5^j:j=0..m) (mod p), zodat: F_p=sum(C(p,2j+1).5^j:j=0..m) (mod p)

Verder hebben we:
C(p,2j+1)=1 voor j=m en C(p,2j+1)=0 (mod p) voor j=0..m-1 (omdat p priem is), zodat: F_p=5^(p-1)/2 (mod p).

Uit de kleine stelling van Fermat/Euler weten we ook dat 5^p-1=1 (mod n) zodat F_p²=1 (mod p) en dus p|(F_p-1).(F_p+1). Omdat p priem is, moet ofwel F_p=1 ofwel -1 (mod p).

Men kan verder bewijzen dat F_p=1 (mod p) wanneer p priem is en 1 of -1 (mod 5) en F_p=-1 (mod p) wanneer p priem is en 2 of -2 (mod 5). De bewijzen vind je bijvoorbeeld bij Arudra Burra en Marc Renault. Ze zijn gebaseerd op de theorie van de kwadratische residuën en in het bijzonder de stelling van de kwadratische reciprociteit. Ze bestuderen de lengte van de periode van F_i (mod n) en hebben een aantal heel interessante conclusies over het voorkomen van 0-en in die rijen.

Collega FvL vond de rij getallen waarvoor F_n=-1 (mod n) en de rij getallen waarvoor F_n=1 (mod n).

Jasper, de vraagsteller wou ook bewijzen dat er voor elke natuurlijke n een index k kleiner dan n² bestaat zodat n|F_k of anders: dat F_k=0 (mod n). Dit volgt uit de bedenking dat F_k(mod n) herhaalt zodra twee opeenvolgende termen herhalen. Er zijn maar n² mogelijke opeenvolgende termen modulo n en sommige zoals (0,0) kunnen niet eens voorkomen. F_i(mod n) is dus periodisch met periode kleiner dan n². We kunnen F_i(mod n) uitbreiden naar negatieve indexen met de aanvulling F_i=F_i+2-F_i+1. F_i(mod n) kan dus doorheen alle gehele indexen i verdeeld worden in repeterende blokken met een lengte k. Dus moet F_k=F₀=0 (mod n) waarbij k dus kleiner is dan n²-1. (We hebben die uitbreiding naar negatieve indexen gebruikt om uit te sluiten dat er een aantal termen van F_i in een soort pre-periode zouden zitten en dat er in de periode zelf geen 0-termen zouden voorkomen.)

Groetjes,
Johan

andros
dinsdag 18 november 2003

©2001-2024 WisFaq