Math Help Forum: Fibbonaci Puzzler

Prove that there exists a fibbonaci number with 2007 zeros at the end.

Surprised no one answered this. Basically the sequence is periodic for mod 10^k. I'm not great at "mathematical" proofs but I'll try to explain why the

81654467027036406333526832763551927773679097587863 01828103274902654645800068375700423192578874801138 49896633172886417559644153347373906530476511639799 03470572826662271659037360447273031780400848575549 03508099075491216597278597834450044376476326281932 72152447517016200655258545132287805391608994236702 32370210418870367835844101551100928971591752027793 74607868568852438352189365382779980690816983216280 47397573781719260414198780609712500413245349971425 87004390684924423594258925625019876096653599085609 00833537023852992689698182781120930012927796187150 19307793377582295367811015065238563352113043140314 90944085671313823277974734958981557281292085601890 06744176078944577779348337171652625983474768859811 57299089487587648844548714667589147775120730050057 94136877675483582484025033771770603207595920161761 00860244176010390835538357799347775384097791851502 58580435803764905167388254314601808367655065706903 17145676009101910237591110135982587999542354257337 69865643686884677779609681580181367794399263876437 47119348248768178379895525253396714698402834275124 89595937485206340807420157549668224663572188043588 91996801563311872885991207304462688534842842899765 28900852819220986366298798374162295530625566277432 64488853168463514650779309887611114310442114751605 26624148697040922363425273844106276196773808206444 55020825499976294193040707383269299795703071190607 99176489670245238094992146216100081801414489746093 7501st term

is the one you're looking for.

(starting n = 1 is 0, n = 2 is 1, n = 3 is 1, n = 4 is 2, n = 5 is 3, n = 6 is 5.... )


The entire Fibonacci series (F) is determined by two numbers (pairs), and F_n mod 10^k for those numbers also determines the sequence. Because there are a finite number of pairings for x mod 10^k, the sequence created by F_n mod 10^k is periodic.

The periodicity of the sequence F_n mod 10^k can be determined:
at k=1 it's 60, k=2 it's 300, and k=3 it's 1500.

The F_n term immediately following the end of the period in effect "restarts" the mod sequence at 0.

or in other words, the F_n term where n = m*12*5^k + 1 (where m is any positive integer) will always have k zeros. ( F_[m*12*5^k + 1] mod 10^k = 0 )

If someone wants to form an actual proof out of that I'd be interested. Note: There are other terms with k zeros at the end besides the (m*12*5^k + 1)th terms.

Also if any of this is unclear please let me know and I'll do my best.

Actually, wolfram alpha disagrees with me.

Their 37,500th term (n=1, F_n=1) only has 4 zeroes, and my thinking meant it ought to have had 5. Couldn't edit out the above but I'll add more info if I figure this out. I don't think I'm completely wrong.

Spoiler:

48643450298934991745127373431498126302650284091297 91729250358638528232068566519689555390474974235878 55014446731404580526452998299867450933484548818010 03862868708185634546033125178185889015208954813005 99252276278396311090943367609139320905575849677030 69685599206853418989813687719877545331484127152890 55494240017609436553449417214039291977823910697452 91351062035075654058038378141261524647111091210562 30346402557362277562398237342714448598750725903701 91123051892344255548507392123929062693276618677895 77747885080863742556721758941996301755724460709854 57818478754063687825040458950890840607608257639996 04316769791880533421346204730863411877227017205815 33585295803343177142855465828387063146632276646229 76545443966204704581957236386624052272387752470368 71951252303960567706071701405401447635564761904148 41412399265591583848920155868229448707787540020438 62585812279845687068397994578841608956160614872199 35966279130129948385593505374582603400942714638344 50028154413687920779068739880624288939657382105258 81210180286554816248214152558068751378139841299421 83488300256666015390286368092151121002079690417129 87057240362783408524560020825873181518495539210437 68628222707170766294232996283831144314597063001991 66413436770651449652069033416611290554870750443766 04890031147026444545895172326637087648084247366980 32470075832797680752718891340054947041453807352287 33642503862076425310281183559734043688982169624969 04424559327283975514471168921849893859022197198821 86532655558000770844988362653750479772218359164223 17321255783618509247947152809841346314208570157620 57896547853926275262833379246463136778827043951916 49652465742860319444687528251301734961523450469085 65236766273863364951439816382299947997109215196804 30675675208385871219800647337491800593044807793121 85078736204257958725877458831393411348438748580795 49392096861271020990977979882809126537461634618990 53005120973257895321289514900449546835823611524767 74955547997904714199852381608424872670799689845460 79182517530350363494876829371441956375953186467094 97830935425972888649114929067463186529940968295406 66634212549020903580154387442065839894575837714514 35428049046591299840178738792640014319543117350147 63870026161946100235268285065614274683366420006243 14855647841388891354841851739763406801779066979320 04386866392115991105597475348609438546080425320572 26488006634069414489698805581314150031048743355293 64957516958874171841761835650928717080159860027040 75004748547173424512537372811117741108265310080692 17031354215670563694431047626866269949045178261170 34140720658087346814092866366394339132725042024780 55164564355800836757187987527702078391023243595826 72940630277722828989846710853678420913619605002295 66897388918194856797766083581930048032816850148279 96114765342236400447069215134255582310556182484872 32712173837997923583821557324137883938040934354122 92838504510141764554364917963401160213537250867902 35026571424177804506919611120401486124429887319400 12381237317000092359519605869112763202399041840983 74986231903770626901745937497215186561455792450718 52298599658618427987924089859304661244982512284859 31563297019053376484858559027971641600778289966637 85187376748607077833884538306386830078463116674199 14810190200605427578730858212049378226002325596072 42837290075557124717135885428782881764928517816419 55871375775154313237798941485638030813920202128425 53202569887046659350336130991761365220891932353278 57738600743110807292696352583244987311866643587458 92357982980992213554572200179609011811306254973697 54251616115751643056195658695901972354170825026457 85055290423654497067514031738358268992981162793418 68358405652653256784402221159058387851335469517691 59731551071715278457381397125328978193470650096471 80823636968781753857241120839376732699513663324795 83848727447071587166829135583855451566392895657880 59829214439006642967154961353269990914540647836418 93416593869987797854934914553128777492556301905087 27495688122476833580678272967150147869373060888673 15843224915984312913009521386363322404556031961187 55491650917870205684875586546120852239977133941819 96842411436596135241444404680041613297020338376844 82771213595788805235546977761069867689202590433529 69131253775282558404409883623914625923553351973377 75252960806308221454070519623264265504114087038806 84257909842699768393837008297887028124969559441608 69873793298189007929956592262247434957281178196485 78074193316686431204977831499483484972550821842599 83187571328052732224149800548788722741783038405635 73722519622808177592263215402377007842804574924894 59828231753410410998239758979894309696444401516568 86555717854602614142854901196446467032096736291678 01951093805120672031063175770886127009576204920981 09957410722384927661315987297134648571785975573593 16937560896878323628380651791051263578392342885979 82430945414444975642596278767190834494992714425257 19322025142401990117926054871182064270042681298943 37814024846714805975503151201998253597574133279391 95989313682680584984345253936712687946523507468506 48683412971763261452942106895577501110329877379149 32711627368327418892247995527116345216250850051385 06009490813174740105399520133852018801859829606525 34072449394517839598431346717424142885611147678910 12956380304338420935086592397589771281818055748028 07600593176364131988954308399714220756003279302241 66260034695045577681883958418306224010337558758199 49790286535251138731456365571385803303848920841720 61366763267721573938300473325351678547015880622401 37317708080365226805634771280900346587135437837100 91881184062191140464992658278896873596879724295147 87938102246939306948358336652810435020475853135600 01243937032516154242456010523738953834222329823106 71852959559168956260807963052838248369976649033576 03681540221878104807401715525248319600238612515821 40044560862992575787603322053861079803549299108338 49446039043343370526679507750688118949462520622688 38663618398676353389784036319265201887085860718318 28302925856315768021279301278114932260396761808311 03459982448416377163151420749579972122215465995347 31758884767410749643975762073211380911696504210665 07265256794180591182187967515625984625579043872055 40038796147865064901081595615338972244555297729910 21213637482865378094670181312532793236672440519264 07029084923028972103716977348048380476441332785282 39289586816144095235299371580704898580994815280815 26409602308615660419429028271486680635182620348672 95743265112174109306892700077825803831835147812154 89581304588768040733501679969918648601453777295230 17689688968617894772009541137343748359104869699816 10599996363009255084464709680881947091372140605138 69955381098297555357341896627245603921518285927480 18146545980395264302172169473954429837761282953932 63421932757981231198286558330122587063563126120307 82760830950331837629941763490633769846076836216528 49586763520464838100201096704575043767178617443683 11786711847573413866546391026800475359491997216689 24609806092276526160373722273879424301151548738349 54104078735929191992673812557238191339358725540923 73183170168034821093035155264535638468800876626911 34888682320198443600003490418737356183653399009137 63841409631274119309150719415459566015934772287489 27636636796658256387065315888107374741792699235711 00919131454889967105660941526937277135200756782128 47279089299743486457106685758257029284323568241710 24584145614309636067708123531070679212060501330027 04670928428157744710043796944633406696193249687257 89477449572114743773431484050556502260590394365395 69749799703149511559405451137949929203026624168269 37091003010308726436525473382443036989093752985016 47504690535777321184261769934283212704980520360159 46218865262896895863702227017719255879689250570515 03598945878246293429060621640574981081347787373624 30258900055029819129449009075728982051389141518642 35723074791368133059882520599672456507846795970487 53261372829775839920032104238421008431143373120025 92141743609550031360830840218858463506295441331898 75888570112481987122356866990570024386666009556901 1120986370872204732574138583872450000

Originally Posted by Chris11

Prove that there exists a Fibonacci (sp!) number with 2007 zeros at the end.

You want to find N such that divides the Nth Fibonacci number , where n=2007.

I haven't tried to prove any of this, but a quick trawl through a table of Fibonacci numbers shows that (for values of N up to 300) divides whenever N is a multiple of , and divides whenever N is a multiple of .

If you can prove that both of those observations hold in general, then it will follow that divides when . When n=2007, that is a large number even in comparison with those calculated by Stro. But in fact this approach is just a slight modification of the one proposed by Stro in his first comment.