整数論の問題

方針 フェルマーの小定理を使って指数を小さくする。

フェルマーの小定理は次の定理である。

> $p$ が素数で、$a$ が $p$ の倍数でないとき $a^{p-1}\equiv 1(\mathrm{mod}p)$ が成り立つ。

手順 1：定理が使えることを確かめる。 $p=11$ は素数であり、$a=2$ は $11$ の倍数ではない。よってフェルマーの小定理が使え、
$$2^{10}\equiv 1(\mathrm{mod}11)$$
が成り立つ。

手順 2：指数を $10$ で割る。 $2024=10\times 202+4$ である。したがって
$$2^{2024}={\left(2^{10}\right)}^{202}\cdot 2^4$$
と書ける。

手順 3：合同式の累乗の性質で計算する。 $2^{10}\equiv 1$ の両辺を $202$ 乗すると ${\left(2^{10}\right)}^{202}\equiv 1^{202}=1(\mathrm{mod}11)$ となる。よって
$$2^{2024}\equiv 1\cdot 2^4=16\equiv 5(\mathrm{mod}11)$$
である。

以上より、求める余りは $5$ である。

フェルマーの小定理より $2^{10}\equiv 1(\mathrm{mod}11)$（11 は素数で 2 と互いに素）。$2024=10\cdot 202+4$ なので $2^{2024}=(2^{10}{)}^{202}\cdot 2^4\equiv 1\cdot 16\equiv 5(\mathrm{mod}11)$。
検算：$2^5=32\equiv -1(\mathrm{mod}11)$ なので $2^{10}\equiv 1$。$2^{2024}=2^{5\cdot 404+4}=(2^5{)}^{404}\cdot 16\equiv (-1{)}^{404}\cdot 16=16\equiv 5$。よって余りは 5。