De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

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
Vragen naar aanleiding van dit antwoord? Klik rechts..!
dinsdag 18 november 2003



home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2024 WisFaq - versie 3