Obliczenie modulo

[matinf]

Witam,
Mam takie coś:

Niech \(\displaystyle{ F(1) = 2 \\ F(k+1) = 2^{F(k)}.}\)
Oblicz \(\displaystyle{ F(5)\ \mod\ 2009}\)

Poza tym, że nie bardzo widzę rozwiązanie tego, to jeszcze nie wiem co to jest to "duże ef".

Tak więc proszę o jakąś wskazówkę, ale i powiedzenie co to jest za funkcja.

[kerajs]

Sądzę że F to zwykła funkcja zadana rekurencyjnie i o argumentach naturalnych.
\(\displaystyle{ F(2)=2 ^{F(1)}=2^2=4}\)
\(\displaystyle{ F(3)=2 ^{F(2)}=2^4=16}\)
\(\displaystyle{ F(4)=2 ^{F(3)}=2^{16}=65536}\)
\(\displaystyle{ F(5)=2 ^{F(4)}=2^{65536}}\)

Pozostaje Ci znaleźć:
\(\displaystyle{ 2^{65536} \mod 2009}\)

[matinf]

Może przedstawię metodę jaką udało mi się policzyć (poprawnie).
Czy ktoś wskaże jakąś prostszą, elegantszą ?

Moja:

Z tw. Eulera mamy, że:
\(\displaystyle{ 2^{\phi(2009)} \equiv_{2009} 1}\)
Podniesiemy do \(\displaystyle{ 39}\) potęgi stronami:
\(\displaystyle{ 2^{1680 \cdot 39} \equiv_{2009} 1}\)
\(\displaystyle{ 2^{65520} \equiv_{2009} 1}\)
Widać, że nie brakuje dużo, potrzebujemy jedynie pomnożyć stronami razy \(\displaystyle{ 2^{16}}\).
Ale wiadomo, że (można policzyć "ręcznie"):
\(\displaystyle{ 2^{11} \equiv_{2009} 39}\)
\(\displaystyle{ 2^{16} \equiv_{2009} 39 \cdot 32}\)
Ostatecznie:
\(\displaystyle{ 2^{65536}\equiv_{2009} 1248}\)

[leszczu450]

matinf, jak dla mnie Twoje rozwiązanie jest bardzo eleganckie : ) Kilka linijek prostych przejść.