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.
Końcówka pięciocyfrowa potęgi liczby 11 - dowód.
- Sylwek
- Użytkownik
- Posty: 2716
- Rejestracja: 21 maja 2007, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 160 razy
- Pomógł: 657 razy
Końcówka pięciocyfrowa potęgi liczby 11 - dowód.
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ść.
\(\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ść.
-
- Użytkownik
- Posty: 760
- Rejestracja: 18 mar 2008, o 10:23
- Płeć: Kobieta
- Lokalizacja: z Lublina
- Podziękował: 32 razy
- Pomógł: 177 razy
Końcówka pięciocyfrowa potęgi liczby 11 - dowód.
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...
[ Dodano: 7 Czerwca 2008, 13:04 ]
ps
Jak dobrze znać zasadę szufladkową Dirichleta i kongruencje...