コンテスト後しばらくは解説を読んでも理解できなかったので、復習です。
解説によると、フェルマーの小定理使うと解けるらしいです。
フェルマーの小定理をWikipediaで調べると、
$a$を$p$の倍数でない整数($a$と$p$は互いに素)とするときに、
$a^{p-1}≡1$ $(mod$ $p)$
が成立する。
と書かれています。
問題文より$2^{16}+1$は素数であり、$a_{n+1}=2^{a_n+1}$は$2$のべき乗です。
$2$と$2^{16}+1$が互いに素であることを利用して、
$2^{2^{16}}≡1$ $(mod$ $2^{16}+1)$
を示したいです。
さて、
$a_2=2^{a_1+1}=2^{1+1}=2^2=4$
$a_3=2^{a_2+1}=2^{4+1}=2^5=32$
$a_4=2^{a_3+1}=2^{32+1}=2^{33}$
$a_5=2^{a_4+1}=2^{2^{33}+1}$
$a_5>2^{2^{16}+1}$なので、ここからフェルマーの小定理が使えそうです。
$2^{33}=2^{16}×2^{17}$より、$2^{33}$は$2^{16}$の倍数なので、
$2^{2^{33}}≡2^{2^{33}-2^{16}}≡2^{2^{33}-2^{16}×2}≡2^{2^{33}-2^{16}×3}≡…≡2^0(=1)$ $(mod$ $2^{16}+1)$になります。
したがって、$a_5≡2$ $(mod$ $2^{16}+1)$になります。
同様に$a_6$の指数部$2^{a_5+1}$ ($a_5$は$16$以上の整数)の$2^{a_5}$は、$2^{16}$の倍数です。($2^{a_5}=2^{16}×2^{a_5-16}$)
というわけで、$2^{a_5}≡1$ $(mod$ $2^{16}+1)$なので、$a_6≡2$ $(mod$ $2^{16}+1)$となります。
$a_7$から先も前の章の$(a_5,a_6)$を$(a_n,a_{n+1})$に置き換えるだけなので同じです。
したがって$a_{100}≡2$ $(mod$ $2^{16}+1)$。