この問題では合同式 (Modular Arithmetic) の性質を利用した計算の簡略化を学習します。大きな数を扱う暗号処理や、ハッシュ関数の計算において、途中の値を小さく保つテクニックとして重要です。
合同式の加法・乗法
$a \equiv b \pmod m$ のとき、加算・乗算を行っても合同関係は保たれます。
$f(x) \pmod m$ を求めるには、まず $x \pmod m$ を計算し、その結果を $f$ に代入すればよい。
1. $n$ の剰余を求める
$n = 123$ を 11 で割ります。
$123 = 11 \times 11 + 2$
したがって、$n \equiv 2 \pmod{11}$ です。
2. 式に代入して計算
$f(123) \equiv f(2) \pmod{11}$ が成り立ちます。
$f(2) = 3(2^2) + 5(2) + 7$
$= 3(4) + 10 + 7$
$= 12 + 10 + 7$
$= 29$
3. 結果の剰余を求める
$29$ を 11 で割った余りを求めます。
$29 = 11 \times 2 + 7$
したがって、答えは 7 です。
計算コストの削減
合同式を使うと、巨大な数 $123^2 = 15129$ を計算することなく、小さな数（2の2乗）だけで結果が得られます。これはコンピュータでの多倍長整数演算の負荷を下げるために必須の考え方です。