Matematyka.pl

akurat Dumel do tego wzorcówki nie ma. zrobilem to zadanie pare miesiecy temu i jak pamietam bylo calkiem fajne, ale moj dowod pamietam jak przez mgle

A jeśli tak, to wrzucę, zwłaszcza, że nie zaobserwowałem protestów;)
Mi też zadanie się spodobało.

Dumel pisze: zad. 6.
Niech \(\displaystyle{ k}\) będzie liczbą całkowitą dodatnią orac ciąg \(\displaystyle{ (a_n)}\) będzie zdefiniowany następująco:
\(\displaystyle{ a_1=k, a_n=k^{a_{n-1}}}\) dla \(\displaystyle{ n>1}\). Pakazać, że jeśli \(\displaystyle{ m}\) jest dowolną liczbą całkowitą dodatnią, to ciąg \(\displaystyle{ a_n}\) jest od pewnego miejsca stały modulo \(\displaystyle{ m}\).

Najpierw bardzo ogólna idea rozwiązania, a w zasadzie wskazówka, jeśli ktoś chciałby zrobić to samemu, ale brakuje mu pomysłu: indukcja, rząd modulo \(\displaystyle{ m}\), chińskie tw o resztach.

Poniżej jest pełne rozwiązanie.

.
.
.
.
.
.
.
.
.

Ustalmy dowolne \(\displaystyle{ k}\) całkowite dodatnie.
Dalej indukcja po \(\displaystyle{ m}\).

Dla \(\displaystyle{ m = 2}\) teza jest oczywista (wszystkie reszty są takie same jak reszty dla \(\displaystyle{ k}\)).

Załóżmy, że zachodzi dla wszystkich liczb naturalnych mniejszych od \(\displaystyle{ m}\).

Jeśli \(\displaystyle{ m = p^{\alpha}}\), gdzie \(\displaystyle{ p}\) jest liczbą pierwszą, \(\displaystyle{ \alpha > 0}\), to mamy dwie sytuacje:

(i) \(\displaystyle{ p|k}\), wtedy wszystkie reszty są od pewnego miejsca zerowe.

(ii) \(\displaystyle{ (p,k) = 1}\), wtedy niech \(\displaystyle{ l}\) będzie rzędem \(\displaystyle{ k}\) modulo \(\displaystyle{ p^{\alpha}}\). Ponieważ \(\displaystyle{ l n_{0}}\), wtedy również \(\displaystyle{ k^{a_{n}} \equiv k^{s}\pmod{p^{\alpha}}}\) dla \(\displaystyle{ n > n_{0}}\), czyli nasz ciąg jest też od pewnego miejsca stały modulo \(\displaystyle{ p^{\alpha}}\).

Jeśli \(\displaystyle{ m = p^{\alpha}\cdot m_{0}}\), gdzie \(\displaystyle{ p}\) jest liczbą pierwszą nie dzielącą \(\displaystyle{ m_{0}> 1}\) oraz \(\displaystyle{ \alpha > 0}\), to z założenia indukcyjnego wiemy, że nasz ciąg jest od pewnego miejsca stały modulo \(\displaystyle{ p^{\alpha}}\) i modulo \(\displaystyle{ m_{0}}\). Z chińskiego tw o resztach dostajemy, że musi być też od tego miejsca stały modulo \(\displaystyle{ p^{\alpha}\cdot m_{0}}\), co kończy krok indukcyjny.

dzieki za fajne rozwiązanie. ja tez wykorzystalem chińskie o resztach i rząd liczby \(\displaystyle{ p^\alpha}\) a reszte mialem jakos inaczej, nie pamietam dokladnie jak, w kazdym razie nieindukcyjnie