Zasada szufladkowa + potęgi(mat. dyskretna)

[p_lipa]

Moja logika wkroczyła w dość abstrakcyjną fazę, w związku z czym mam problem z rozwiązaniem jednego zadania.

Pokazać, że istnieją dwie potęgi liczby 3, których różnica dzieli się przez 1997. Pokaż, że istnieje potęga liczby 3, której rozwinięcie dziesiętne kończy się cyframi 001.

Wiem, że rozwiązanie bazuje na zasadzie szufladkowej dirichleta, ale w tym konkretnym przypadku nie potrafię jej sobie odpowiednio wyobrazić, a nigdzie nie mogę znaleźć analogicznych przykładów.

Z góry dzięki za podpowiedzi i ewentualne rozwiązania

--
Pozdrawiam
Piotr Lipiak

[Brzytwa]

Pokazać, że istnieją dwie potęgi liczby 3, których różnica dzieli się przez 1997.

Każda potęga musi dawać jaką resztą przy dzieleniu przez 1997. Więc bierzemy 1998 różnych potęg 3. Z zasady szufladkowej mamy, że pewne dwie dają tą samą resztę. Spełniają one oczywiście wówczas tezę zadania.

[BettyBoo]

Druga częśc to jest bezpośredni wniosek z tw Eulera. Ponieważ \(\displaystyle{ NWD(3,1000)=1}\), to oczywiście istnieje takie \(\displaystyle{ n}\), że \(\displaystyle{ 3^n\equiv_{1000}1}\) (takim \(\displaystyle{ n}\) jest np \(\displaystyle{ \varphi(1000)}\)).

Można też na upartego z Dirichleta (analogicznie jak poprzednio) - rozpatrujesz 1001 potęg liczby 3. Dwie muszą dawać tą samą resztę, więc ich różnica jest podzielna przez 1000. Wobec tego \(\displaystyle{ k>n\ \Rightarrow 3^k-3^n=3^{n}(3^{k-n}-1)}\) jest podzielne przez 1000. Ponieważ żadna potęga 3 nie dzieli się przez 1000, to przez 1000 dzieli się ta druga liczba, co daje tezę.

Pozdrawiam.