記事ソース/分数で表現した中国の剰余定理 - 物理のかぎプロジェクトWiki

新規

編集

添付

変更点

トップ

メニュー

間違い報告

現在 10 名がオンラインです。

記事ソース/分数で表現した中国の剰余定理†

これはrst2hooktailの記事ソース保存・変換用です（詳細）．

コンバート

最近コンバートされた結果： HTML， PDF， TeX

公開・更新メニュー ▼▲

記事ソースの内容

ソースのテキストファイルを表示

==================================
分数で表現した中国の剰余定理
==================================

整数論の分野では当然のことのように分数は使われていませんが，以外に分数による表現が分かりやすいことが
あります．その例として，中国の剰余定理の内容と証明を分数を用いて説明します．また，同様の考え方で
多項式の剰余の代わりに有理式を用いる説明を付記します．




中国の剰余定理とは
==================================

簡単のため 整数 $a$ を正の整数 $n$ で割った剰余 $a \bmod n$ を $|a|_{n} ~~(0 \leq |a|_{n} < n)$ で
表わします． $|a|_{3} = b, ~~ |a|_{5} = c$ である $|a|_{15}$ は，中国の剰余定理により

<tex>
|a|_{15} = | 10 b + 6 c |_{15}
</tex>

で求められます．この 10 と 6 を詳しく書くと， $10 = 5 \times |5|_{3}^{-1}$, $6 = 3 \times |3|_{5}^{-1}$ 
です．ここで $|5|_{3}^{-1}$ は $|5 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 |35|_{3}^{-1} \\
21 = 3 \times 7 \times |21|_{5}^{-1} \\
15 = 3 \times 5 \times |15|_{7}^{-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}, ~~~~
\frac{x'}{3} = \Delta \frac{x}{3}, ~~~~ \frac{y'}{5} = \Delta \frac{y}{5}
</tex>
<tex>
\Delta \left( \frac{5 x'}{3} + y' \right) = \Delta \frac{2 x'}{3} = \frac{1}{3}
</tex>

から， $x' = 2$ であることが分かります．同様に $y' = 2$ であることも分かり，任意の $a$ に対して成立する

<tex>
\Delta \left( \frac{2 a}{3} + \frac{2 a}{5} \right) 
= \Delta \left( \Delta \frac{2 a}{3} + \Delta \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}$ に $b = 3 \Delta \frac{a}{3}, ~~ c = 5 \Delta \frac{a}{5}$ を代入すると

<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>
\Delta \left( \frac{x'}{3} + \frac{y'}{5} + \frac{z'}{7} \right) = \frac{1}{105}
</tex>
<tex>
\Delta \left( \frac{35 x'}{3} + 7 y' + 5 z' \right) 
= \Delta \frac{2 x'}{3} = \frac{1}{3} = \frac{35}{105},~ \cdots
</tex>

となる $x'$, $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>

が得られます．実質的にはガウスの方法そのものですが，こちらの方が説明しやすいと思いませんか．




補遺
==================================

多項式 $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{56}{21} = \frac{14}{21}, ~~~ \Delta \frac{21}{14} = \frac{7}{14}, ~~~ \Delta \frac{14}{7} = 0
</tex>

と同様に，

<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>

で計算過程を明示できます（この例では最後の分母が定数なので互いに素）． 




あとがき
==================================

$a \bmod 3$ の代わりに $\Delta (a / 3)$ を用いると，本文中の $\Delta (5 x / 3 + y) = \Delta (2 x / 3)$
のような計算を分かり易く表現できます．分数を用いた表現の主役は作用素 $\Delta$ です．概して，複数の法に
対する剰余を考えるときは分数による表現が有効であると思います．ただし，この表現は一般には通用しませんから，
レポート等には使わないでください．



@@reference: ja.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E3%81%AE%E5%89%B0%E4%BD%99%E5%AE%9A%E7%90%86,中国の剰余定理-Wikipedia@@
@@reference: ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95,ユークリッドの互除法-Wikipedia@@
@@reference: www004.upp.so-net.ne.jp/s_honma/gauss/gauss.htm,連立合同式@@
@@reference: oshiete.goo.ne.jp/qa/2740868.html,中国式剰余定理の教え方 - 数学 - 教えて！goo@@
@@reference: okwave.jp/qa/q1789394.html,中国の剰余定理 | OKWave@@

@@author: pulsar@@
@@accept: @@
@@category: 初等代数@@

物理のかぎプロジェクト

メニュー

最新の25件

記事ソース/分数で表現した中国の剰余定理†

コンバート

公開・更新メニュー ▼▲

記事ソースの内容