べき乗の剰余
【例題】
$29^4$ を $33$ で割った余りを求めよ。
【解答】
mod $33$ で次のように計算する。
\[ 29^4 \equiv (-4)^4 = 256 \equiv 25 \]
【別解】
上の解答で、$256$ を $33$ で割った余りを計算するのが面倒な場合は、次のように、素因数をうまく組み合わせて計算することもできる。
\[ 29^4 \equiv (-4)^4 = 2^8 = 2^5 \cdot 2^3 = 32 \cdot 8 \equiv (-1) \cdot 8 = -8 \equiv 25 \]
[1] を $33$ で割った余りは である。
[2] を $35$ で割った余りは である。
[3] を $39$ で割った余りは である。
[4] を $41$ で割った余りは である。
[5] を $51$ で割った余りは である。