合同式で余りを計算する
着眼点a\equiv b\pmod m は足す・引く・掛ける・累乗してよい。1（または -1）になる累乗を見つけて指数を小さくする。
a\equiv b,\ c\equiv d\pmod m\ \Longrightarrow\ a\pm c\equiv b\pm d,\quad ac\equiv bd,\quad a^n\equiv b^n
割り算は自由にはできない（m と互いに素な数で割るときのみ可）。
例題
1
3^{100} を7で割った余りを求めよ。
解答
3^3=27\equiv-1\pmod 7 より 3^6\equiv1。
100=6\cdot16+4 なので 3^{100}=(3^6)^{16}\cdot3^4\equiv3^4=81\equiv4。
答 4
100=6\cdot16+4 なので 3^{100}=(3^6)^{16}\cdot3^4\equiv3^4=81\equiv4。
答 4
2
2^{50} の一の位の数を求めよ。
解答
一の位は10で割った余り。2,4,8,6,2,4,\dots と周期4で繰り返す（2^{n+4}\equiv2^n\pmod{10}、n\ge1）。
50=4\cdot12+2 なので 2^{50} の一の位は 2^2 と同じ 4。
答 4
50=4\cdot12+2 なので 2^{50} の一の位は 2^2 と同じ 4。
答 4
注意記述答案で合同式を使う場合、記号の意味を一言添えておくと安全（採点者に誤解されない）。
確認問題
1
7^{2026} を5で割った余りは？
答え
7\equiv2、2^4=16\equiv1。2026=4\cdot506+2 より 2^2=4