modulo のバックアップ(No.2)
modulo のバックアップ(No.2)
これはrst2hooktailの記事ソース保存・変換用です（詳細）．
==================================
分数で表現した中国の剰余定理
==================================
整数論の分野では当然のことのように分数は使われていないが，以外に分数による表現が分かりやすいことが
あります．その例として，中国の剰余定理やガロア拡大体を分数式で説明します．
中国の剰余定理とは
==================================
簡単のため 整数 $a$ を正の整数 $b$ で割った剰余 $a \bmod b$ を $|a|_{b} (0 \leq |a|_{b} < b)$ で
表わします． $|a|_{3} = b$, $|a|_{5} = c$ である $|a|_{15}$ は，中国の剰余定理を用いて
<tex>
|a|_{15} = | 10 b + 6 c |_{15}
</tex>
で求められます．この 10 と 6 を詳しく書くと， $10 = 5 \times |3|_{3}^{-1}$, $6 = 3 \times |5|_{5}^{-1}$
です．ここで $|3|_{3}^{-1}$ は $|3 x|_{3} = 1$ となる $x$ （3 を法とする逆元）を意味します．また，
$|a|_{3} = b$, $|a|_{5} = c$, $|a|_{7} = d$ である $|a|_{15}$ （$3 \times 5 \times 7 = 105$）は
