- 追加された行はこの色です。
- 削除された行はこの色です。
#rst2hooktail_source
==================================
分数で表現した中国の剰余定理
==================================
整数論の分野では当然のことのように分数は使われていませんが,以外に分数による表現が分かりやすいことが
あります.その例として,中国の剰余定理やガロア拡大体を分数を用いて説明します.
中国の剰余定理とは
==================================
簡単のため 整数 $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|_{105}$ ( $3 \times 5 \times 7 = 105$ )は
<tex>
|a|_{105} = | 70 b + 21 c + 15 d|_{105}
</tex>
<tex>
70 = 5 \times 7 \times |3|_{35}^{-1} \\
21 = 3 \times 7 \times |5|_{21}^{-1} \\
15 = 3 \times 5 \times |7|_{15}^{-1}
</tex>
です. $m$, $n$ が互いに素であれば
<tex>
m x + n y = 1
</tex>
となる整数 $x$, $y$ が存在するという有名な性質を使って,上記の式を導いてみましょう.
分数による表現
==================================
以下では,有理数 $r$ の整数部を $\Gamma r$, 小数部 $\Delta r$ ( $0 \leq \Delta r < 1$ ) で
表わします.例えば
<tex>
\Gamma \left(-\frac{8}{3} \right) = -3, ~~~~ \Delta \left(-\frac{8}{3} \right) = \frac{1}{3}
</tex>
です. $5 x + 3 y = 1$ は
<tex>
\frac{x}{3} + \frac{y}{5} = \frac{1}{15}
</tex>
と書き換えることができるので,
<tex>
\Delta \left( \frac{x}{3} + \frac{y}{5} \right) = \frac{1}{15}
</tex>
となる $x$ ( $0 \leq x <3$ ), $y$ ( $0 \leq y <5$ ) が存在し,
<tex>
\Delta \left( \frac{5 x}{3} + y \right) = \Delta \frac{2 x}{3} = \frac{1}{3}
</tex>
から, $x = 2$ であることが分かります.同様に $y = 2$ であることも分かり,
<tex>
\Delta \left( \frac{2 a}{3} + \frac{2 a}{5} \right) = \Delta \frac{a}{15}
</tex>
が得られます.
<tex>
\Delta \frac{2 a}{3} = \Delta \left(2 \Gamma \frac{a}{3} + 2 \Delta \frac{a}{3} \right)
= \Delta \left( 2 \Delta \frac{a}{3} \right)
</tex>
ですから,上記の式を
<tex>
\Delta \left(2 \Delta \frac{a}{3} + 2 \Delta \frac{a}{5} \right) = \Delta \frac{a}{15}
</tex>
と書き換えることができます.これが分数で表現した中国の剰余定理です.
先に示した $|a|_{15} = | 10 b + 6 c |_{15}$ に
<tex>
b = 3 \Delta \frac{a}{3}, ~~~~ c = 5 \Delta \frac{a}{5}
</tex>
を代入すると
<tex>
15 \Delta \frac{a}{15} = 15 \Delta \frac{10 \cdot 3 \Delta \frac{a}{3} + 6 \cdot 5 \Delta \frac{a}{5}}{15}
= 15 \Delta \left( 2 \Delta \frac{a}{3} + 2 \Delta \frac{a}{5} \right)
</tex>
となり,上式と等価であることを確認できます. $|a|_{105} = | 70 b + 21 c + 15 d|_{105}$ については
<tex>
\frac{x}{3} + \frac{y}{5} = \frac{1}{15}, ~~~~ \frac{w}{15} + \frac{z}{7} = \frac{1}{105}
</tex>
から
<tex>
\frac{w x}{3} + \frac{w y}{5} + \frac{z}{7} = \frac{1}{105}
</tex>
となる $w x$, $w y$, $z$ を 2, 1, 1 として
<tex>
\Delta \left( \frac{2}{3} + \frac{1}{5} + \frac{1}{7} \right) = \Delta \frac{106}{105} = \frac{1}{105}
</tex>
<tex>
\Delta \left(2 \Delta \frac{a}{3} + \Delta \frac{a}{5} + \Delta \frac{a}{7} \right) = \Delta \frac{a}{105}
</tex>
が得られます.
ユークリッドの互助法
==================================
互いに素か否かの判定に使うユークリッドの互助法も $\Delta$ を使うと表現が簡単になります.例えば 70 と 24 の
最大公約数を求める計算は次のようになります.
<tex>
\Delta \frac{70}{24} = \frac{22}{24}, ~~~ \Delta \frac{24}{22} = \frac{2}{22}, ~~~ \Delta \frac{22}{2} = 0
</tex>
多項式 $P(x)$ を多項式 $G(x)$ で割ったときの商を $Q(x)$, 剰余を $R(x)$ として
<tex>
\Gamma \frac{P(x)}{G(x)} = Q(x), ~~~ \Delta \frac{P(x)}{G(x)} = \frac{R(x)}{G(x)}
</tex>
で $\Gamma (P(x)/G(x))$, $\Delta (P(x)/G(x))$ を定めると,多項式についても同様の計算
<tex>
\Delta \frac{x^2 + 2 x + 3}{x^2 - 1} = \frac{2 x -4}{x^2 - 1}, ~~~
\Delta \frac{x^2 - 1}{x - 2} = \frac{3}{x - 2}, ~~~ \Delta \frac{x - 2}{1} = 0
</tex>
によって共通因数の有無を調べることができます.