Matematyka.pl

Udowodnij, że istnieje liczba postaci \(\displaystyle{ 11 ^{n}}\) której końcówka pięciocyfrowa to 00001.


Zadanie pochodzi z Internetowego Kółka Matematycznego dla gimnazjum.

Zauważmy, że nigdy nie zachodzi: \(\displaystyle{ 11^n \equiv 0 \ (mod \ 100000)}\), teraz warty zapamiętania trick: zauważmy, że wśród 100000 liczb: \(\displaystyle{ 11^1, \ 11^2, \ 11^3, \ \ldots, \ 11^{99999}, \ 11^{100000}}\) istnieją dwie dające taką samą resztę z dzielenia przez 100000 (i tą resztą nie jest to 0) - dowód wynika natychmiastowo z Zasady Szufladkowej Dirichleta. Zatem dla pewnych k,p, prezyjmijmy \(\displaystyle{ 1\leqslant k < p qslant 100000}\) mamy:
\(\displaystyle{ 11^p-11^k \equiv 0 \ (mod \ 100000) \ \iff \ 11^k (11^{p-k}-1) \equiv 0 \ (mod \ 100000)}\), zatem:
\(\displaystyle{ 11^{p-k}-1 \equiv 0 \ (mod \ 100000) \ \iff \ 11^{p-k} \equiv 1 \ (mod \ 100000)}\), toteż \(\displaystyle{ n=p-k}\) spełnia warunki zadania, co należało dowieść.

Rzeczywiście rozwiązanie jest proste, gdy skorzystamy z dwóch pierwszych zadań w tym bukiecie. (Nie wiem, czy z nich skorzystałeś czy nie), a ja nie wiedziałem jak je wykorzystać. Dziękuję bardzo.

[ Dodano: 7 Czerwca 2008, 13:04 ]
ps

Jak dobrze znać zasadę szufladkową Dirichleta i kongruencje...