フェルマーの小定理

素数 $p$ と、$p$ と互いに素である整数 $a$ に対し、

\[a^{p-1}\equiv1\pmod p\]

が成り立つ。すなわち、$a$ の $p-1$ 乗を $p$ で割った余りは $1$ になる。

例題

$3^{2021}$ を $19$ で割った時の余りを求めよ

フェルマーの小定理より、$3^{19-1}=3^{18}\equiv1\pmod {19}$ となる。

$2021 = 18\times 112 + 5$ より、

\[3^{2021}\equiv(3^{18})^{112}\times 3^5\equiv1^{112}\times 243 \pmod {19}\] \[243 \equiv 15 \pmod {19}\]

よって求める余りは $15$ 。