Algebra

Analyse

Bewijzen

De grafische rekenmachine

Discrete wiskunde

Fundamenten

Meetkunde

Oppervlakte en inhoud

Rekenen

Schoolwiskunde

Statistiek en kansrekenen

Telproblemen

Toegepaste wiskunde

Van alles en nog wat


\require{AMSmath}

Fibonacci getal modulo zijn index: Fp (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 Fn+1.Fn-1-Fn2=(-1)n en zo meer.
Het was me opgevallen dat voor elk priemgetal p, Fp2=1 (mod p). Hoezeer ik ook puzzel ik kom er niet uit, en ik kan al helemaal geen regelmaat vinden wanneer Fp (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:
F0=0, F1=1 en Fi=Fi-1+Fi-2.

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

Bewijs:
Dat de eigenschap geldt voor p=2 en 3 zie je zo.
Voor p=5, is Fp=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:
Fp=sum(C(p,2j+1).5j:j=0..m)/2p-1 (C: combinaties van p per 2j+1)

We bekijken nu Fp (mod p): omdat ggd(p,2)=1, is 2p-1=1(mod p). We hebben dus:
2p-1.Fp=sum(C(p,2j+1).5j:j=0..m) (mod p), zodat: Fp=sum(C(p,2j+1).5j: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: Fp=5(p-1)/2 (mod p).

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

Men kan verder bewijzen dat Fp=1 (mod p) wanneer p priem is en 1 of -1 (mod 5) en Fp=-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 Fi (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 Fn=-1 (mod n) en de rij getallen waarvoor Fn=1 (mod n).

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