Udowodnić że dla dowolnej liczby naturalnej \(\displaystyle{ n}\) istnieje \(\displaystyle{ k}\) takie, że liczba \(\displaystyle{ 3^k}\) kończy się ciągiem \(\displaystyle{ n-1}\) zer i jedynką.
*
Pierwsza potęga trójki zakończona ciągiem \(\displaystyle{ 01}\) to: \(\displaystyle{ 3^{20}=348678401=3486784 \cdot 100+1=100N+1}\)
Liczbę zakończoną ciągiem \(\displaystyle{ n-1}\) zer i jedynką dostanie się przez podniesienie powyższej liczby do potęgi \(\displaystyle{ 10^ {n-2}}\)
Czyli innymi słowy chcemy udowodnić, że dla dowolnej liczby całkowitej dodatniej \(\displaystyle{ n}\) istnieje takie \(\displaystyle{ k\in \NN^+}\), że \(\displaystyle{ 3^k\equiv 1\pmod{10^n}}\).
Jest to natychmiastowa konsekwencja twierdzenia Eulera, ale można to uzyskać elementarnie: ustalmy dowolne \(\displaystyle{ n\in \NN^+}\).
Na mocy zasady szufladkowej Dirichleta
wśród liczb \(\displaystyle{ 3, \ 3^2, \ldots 3^{10^n+1}}\) (jest to \(\displaystyle{ 10^n+1}\) liczb postaci \(\displaystyle{ 3^k}\))
istnieją dwie, które dają tę samą resztę z dzielenia przez \(\displaystyle{ 10^n}\). Weźmy takie dwie konkretne liczby, niech będą to \(\displaystyle{ 3^p}\) i \(\displaystyle{ 3^q}\), gdzie \(\displaystyle{ 1\le p<q\le 10^n+1}\). Wówczas liczba \(\displaystyle{ 3^{q-p}}\) spełnia warunki zadania.
Uważam, że rozwiązanie kerajsa jest ciekawsze, bo przynajmniej znalazło się w nim jakieś spostrzeżenie.