0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

OMC218B(755,整数)

Last updated at Posted at 2024-10-22

コンテスト後しばらくは解説を読んでも理解できなかったので、復習です。
解説によると、フェルマーの小定理使うと解けるらしいです。

フェルマーの小定理を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)$。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?