Задача о числах Фибоначчи

[Whitaker]

Здравствуйте уважаемые!
Помогите пожалуйста решить следующую задачку. Я пока вообще не знаю с чего начать.
Найдется ли среди первых $100 000 001$ первых членов ряда Фибоначчи числа, оканчивающееся четырьмя нулями?

С уважением, Whitaker.

[Sonic86]

В лоб так: число $x$ оканчивается 4-я нулями $\Leftrightarrow x \equiv 0 \pmod {2^4 \cdot 5^4}$ - это сравнение можно разбить на 2 сравнения, найти периоды чисел Фибоначчи по модулям $2^k, 5^k$, решить сравнения ну и сделать вывод.

[Whitaker]

Sonic86, а можно ли решить без сравнений?
Решать сравнения я пока не могу

[Null]

Вообще-то кол-во членов $= 10000^2+1$, это делается стандартно через принциц дирихле и цикличность.

[Whitaker]

Null
Ну да я заметил, что количество членов равно $=10^8+1$
А причём здесь цикличность?

-- Вт ноя 29, 2011 11:53:39 --

Sonic86 Большое спасибо Вам
Я понял Вашу подсказку и у меня получилось.

[kiyanyn]

Whitaker в сообщении #509486 писал(а):

Здравствуйте уважаемые!
Помогите пожалуйста решить следующую задачку. Я пока вообще не знаю с чего начать.
Найдется ли среди первых $100 000 001$ первых членов ряда Фибоначчи числа, оканчивающееся четырьмя нулями?

Ну, например, $F_{7500}$, если компьютер не врет, равно
11423965231520587047220488928656904198487186633317560797959030595738263643588305
26396432108051699142993762888622955534014664444274447318546077830293474380700224
81096957412087824111591899946515209300912020351012693505236094172765422096822611
68150544790025062794209091503702088574338650460569295592498666443239807989522593
07256215864094746865688764587935620130159484187249149755638955581727750834905833
04980075838142701233297243532331560291279109683700527348111926604927333753944726
92191584489489590970254440914222778382439339334175624660291588778456250479185237
89830911231882998435821633734754901433651748649664322450277338004207117436059719
23430563184892870384470047309220739808700729907060675086240384078884712940489122
94153491398930715643640170172837379127969101176561450586945715460276780809807889
66427281831686571172498564655455930533434031899461218526071904200896031126900012
26725897312834196080983033672603823796604022618865749522117836831044533342816844
25994447306306414660032519055079504313562694958935754118796157632978970220780288
16899218169970892297141706773514492946119363908144520078688154933115038121607370
54175311667866346904692064186115246630138541980452848067207352737150468887049168
21855277543026346215355286395854263168251068150374988851620501196943905031285049
07762844380405213450702250468248329339621526818662012476237974466809216603531455
35417315372459462564228618525730062304923222596303422943508271848406075099692893
28320360093204783447860955806396350723341261564285649453007949089154165288839814
442677339344794691881510389855765582716774490000...

[Whitaker]

Ваууу