わんこら日記
甘くて切ない日記。わんこら式数学の勉強法、解説記事

中国剰余定理、百五減算の説明
前から代数で気になっててんけど、中国式剰余定理ってやつがあるねん。

名前に魅かれてたわけやな。
それで今日はその話やねんけど、まずは中学受験ぐらいのレベルの話やからみんな聞いたってくれ。


それでどんなのかと言うと、中国の算術書「孫子算経」には

「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か?」

って載ってるねん。


どうやって求めるかと言うと、

まず5と7で割り切れて3で割ると2余る数を考えるねん。

5と7で割り切れるのは5×7=35の倍数なわけや。

35は3で割ると35÷3=11余り2

ちょうど余り2になってるから35でオッケーや。


次に3と7で割り切れて5で割ると3余る数を考えるねん。

3と7で割り切れるのは3×7=21の倍数やろ。

21を5で割ると21÷5=4余り1と言うように1余るわけや。

と言うことは、3余るようになるには21を3倍して63にすると

63は3と7で割り切れるし、5で割ると63÷5=12余り3ってちゃんと3余るわけや。


そして同じように3と5で割り切れて7で割ると2余る数を考えて、

3と5で割り切れるのは15の倍数で、15を7で割ると15÷7=2余り1より2をかけたら2余るようになるから

15を2倍して30にして30÷7=4余り2。


35,63,30って数字が出たから後はどうしたらいいかと言うと全部足すわけや。

35+63+30=128

なんでこれでいいかと言うと、書き方をかえると

(5×7)+3×(3×7)+2×(3×5)=128

と言うように、3で割ると余りは3×(3×7)+2×(3×5)の部分は3で割り切れるから5×7=35を3で割った余りと等しいわけや。
これは2になってたな。

5で割ると余りは(5×7)+2×(3×5)の部分は5で割り切れるから3×(3×7)=63を5で割った余りと等しいわけで、これはちゃんと3になるように21に3かけて調整しといたわけや。

7で割ると余りは(5×7)+3×(3×7)の部分は7で割り切れるから2×(3×5)=30を7で割った余りと等しいわけで、これはちゃんと2にあるように15に2をかけておいて調整してたわけや。

だから全部たした128は全部条件を満たしてるわけやな。


それで3×5×7=105やから105の倍数を引いたり足したりしても、3、5、7で割った余りは変化せえへんわけやん。

128+(3×5×7の倍数)

これが

「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か?」

を満たす整数なわけや。


一番小さい正の整数で言うと128-105=23で23って答えるのが普通かな。



これをちょっと改良すれば、5×7=35の2倍である70は3で割ると70÷3=23余り1
3×7=21は5で割ると余り1
3×5=15は7で割ると余り1

3×5×7=105

だからある数が3で割った余りがx,5で割った余りがy,7で割った余りがzとすると、その数を105で割った余りは

70x+21y+15z

を105で割った余りと等しいわけや。


だから人間の歳は1~105くらいまでやから、人間の歳を当てるのとかに使われる遊びがあるわけやな。


例えばある人の歳が3で割った余りが1,5で割った余りが4,7で割った余りが6ってわかったら

70×1+21×4+15×6=244

105で割ると余りは34で34歳ってわかるわけや。


でも最近は106歳以上生きよるやつがおると。

たしかに106歳なのか、1歳なのかこの計算からではどっちかわからん。

そら見たらどっちかわかるかもしれんけど、歳老いてくると幼児退行してくるから、どっちもパンパースとかつけかえなあかんし,1歳か106歳かいちがいにはどっちかわからんやん。


そういう時は今までの説明から3,5,7でなくても、どの二組の数字も互いに素な整数(最大公約数が1)であればええわけやから
3,5,8とかでもええわけやな。

3×5×8=120

これで120歳まではいける。

ある数が3で割るとx,5で割るとy,8で割るとz余るならば、その数を120で割った余りは

40x+96y+105z

を120で割った余りに等しい。


まあ色々ためしてくれ。

ここまでは、ええとして本当の代数としての中国式剰余定理って言うのは、もっと凄いことを言うてて


中国式剰余定理
090503_m1.jpg

I_1,I_2,…,I_nを可換環Rのどの2つも互いに素なイデアルとする。
このとき
(i)∩(i=1~n)I_i=I_1I_2…I_n
(ii)R/∩(i=1~n)I_i = R/I_1×R/I_2×…×R/I_n
((ii)の=は同型のこと)


ちょっと、大学の数学はもうわけわからん感じかもしれんけど、言葉で簡単に言うと

どの二つも互いに素なn個の整数m_1,m_2,…,m_nがあったとすると、m_1,~,m_nのどの整数の倍数にもなるのは、M=m_1m_2…n_nとするとMの倍数である。

そしてMで割った余りの足し算、引き算、かけ算は、m_1,m_2,…,m_nのそれぞれで割った余りの足し算、引き算、かけ算を考えるのと同じである。(k=1~n)

(体じゃなくて環やから割り算は出来ない。
実際互いに素であっても素数ではない整数mを選べばZ/mZは体にならない。
そういう話は→合同式の割り算とか合同式≡と剰余類の説明と応用問題を参照)

最後の文章は言葉では難しいな。

例えば6に7を足して4をかけると言う計算において

これを3で割った余りで考えると

6は3で割ると余り0

7を3で割ると余り1

4を3で割ると余り1

だから

(0+1)×1=1

で1余るで、6に7を足して4をかけると言う計算に3で割った余りで考えると1が対応してて


5で割った余りで考えると

6は5で割ると余り1

7を5で割ると余り2

4を5で割ると余り4

だから

(1+2)×4=12

12を5で割ると余り2より、計算に5で割った余りは2が対応していて


7で割った余りで考えると

6は7で割ると余り6

7を7で割ると余り0

4を7で割ると余り4

(6+0)×4=24

24を7で割ると余り3で、計算に7で割った余りは3が対応しているってことやねん。

(3で割った余り、2で割った余り,7で割った余り)と言う成分で考えると計算は
((6+7)4,(6+7)4,(6+7)4)
=((0+1)1,(1+2)4,(6+0)4)
=(1,12,24)
=(1,2,3)

と言うような過程に対応していて、(6+7)4=52やけど実際に(1,2,3)と言う結果は
70x+21y+15zを使えば

70×1+21×2+15×3=70+42+45
=157

105で割ると余りは52でちゃんと52になるわけやな。

合同式を勉強していれば、もっとわかりやすく書けて

(6+7)4≡52(mod 105)



(6+7)4≡(0+1)1≡1(mod 3)

(6+7)4≡(1+2)4≡12≡2(mod 2)

(6+7)4≡(6+0)4≡24≡3(mod 7)

の三つを計算してるのと同じことってことやねん。


扱う数字が小さくわけて計算すればよくなるから、この定理使えばコンピューターの計算が高速化されるらしいな。
あんま詳しいことは知らんけど、まあ一応みんな普段からお世話になってる定理らしい。

基本的に数学は知らないところで生活に役立ちまくってるからな。


それでこの中国式剰余定理の証明方法は、

(i)の証明。
数学的帰納法で証明する。
n=2のとき、I_1I_2⊂I_1∩I_2はイデアルの定義から当たり前やから
I_1I_2⊃I_1∩I_2を示したらよい。

I_1とI_2は互いに素より
1=x_1+x_2となるx_1,x_2∈Rが存在して

任意のa∈I_1∩I_2に対してa=ax_1+ax_2でax_1,ax_2∈I_1I_2より
a∈I_1I_2

n=kの時、I_1I_2…I_k=∩(i=1~k)I_iと仮定

I_(k+1)とI_i(1≦i≦k)は互いに素より
各iに対して、x_(k+1)(i)+x_i=1となるx_(k+1)(i)∈I_1,x_i∈I_iが存在。

(x_(k+1)(2)+x_2)(x_(k+1)(3)+x_3)…(x_(k+1)(n)+x_n)=1

x_2x_3…x_n+(どの項もx_(k+1)(i)を含む式)=1

(どの項もx_(k+1)(i)を含む式)∈I_(k+1)

x_2x_3…x_n∈I_2I_3…I_n

よってI_(k+1)+I_2I_3…I_k=RでI_(k+1)とI_2I_3…I_kは互いに素だから

n=2の時の結果から

I_1I_2…I_(k+1)=(I_1I_2…Ik)∩I_(k+1)
=∩(i=1~k)I_i∩I_(k+1)
=∩(i=1~k+1)I_i

よって数学的帰納法より題意成立。

(ii)の証明
数学的帰納法によって証明する。

n=2のとき、凖同型写像
f:R→R/I_1×R/I_2 (f(x)=(p_1(x),p_2(x)))
(p_1:R→R/I_1,p_2:R→R_/I_2は自然な射影)
を考えると、
kerf=I_1∩I_2
よって環凖同型定理から
Imf=R/I_1×R/I_2(=は自然な同型)
つまり全射であれば
R/I_1∩I_2=R/I_1×R/I_2(=は同型)
が言える。

I_1とI_2は互いに素より
1=x_1+x_2(x_1∈I_1,x_2∈I_2)
とできて、任意の2つの元,a,b∈Rに対して
c=bx_1+ax_2とすると
c=bx_1+ax_2≡ax_2=a(1-x_1)
=a-ax_1≡a(mod I_1)

c=bx_1+ax_2≡bx_1=b(1-x_2)
=b-bx_2≡b(mod I_2)
となり
f(c)=(p_1(a),p_2(b))
だから、fは全射。

n=kのとき、R/∩(i=1~k)I_i=R/I_1×R/I_2×…×R/I_kと仮定すると(=は同型)

I_1I_2…I_k=∩(i=1~k)I_iとI_(k+1)は互いに素だから、n=2の場合の結果から

R/(∩(i=1~k)I_i)∩I_(k+1)=R/(∩(i=1~k)I_i)×R/I_(k+1)
=R/I_1×R/I_2×…×R/I_×R/I_(k+1)
(=は同型)

よって数学的帰納法により題意成立。

数学、物理

高校数学の公式や問題の解説

中学数学の問題や公式

中学受験の算数の問題の解答や解説

整数問題の解法の解説と問題演習

テーマ:日記 - ジャンル:日記

▲ページトップへ
この記事に対するトラックバック
トラックバックURL
→http://wankora.blog31.fc2.com/tb.php/1790-30d3c8f3
この記事にトラックバックする(FC2ブログユーザー)
▲ページトップへ
プロフィール

わんこら

Author:わんこら
京都大学理学部を数学専攻で卒業した数学と物理講師

現在、東京で働いています。

かずスクール
で数学を教えてます。

わんこら式数学の勉強法
数学の勉強方法や仕方を説明

詳しいプロフィール


メッセージはこちらへ
メール
迷惑メールにされる危険性があるので出来るだけ
kazuyuki_ht○guitar.ocn.ne.jp
(○を@にしてください)に送ってください

勉強とかでどんな悩み持ってるかなど色々と教えてくれると嬉しいです。
わんこら式のやり方についてはわんこら式診断プログラムを参考にしてメールください
都合がつかず遅れたり返せなかったりする場合があるのは申し訳ないです

リンクはばりばりのフリー
一言メールくれれば相互リンクします。


カテゴリーと名作集
読者に受けが良かった記事を集めてたり、今までの記事をカテゴリー別にまとめてます。



水と空気と街並とからだ
中学時代からの親友てつろうのブログ。
今年、滋賀医科に合格した医学生です。

リンク集
リンク集はこっちです。

このブログは携帯でも見られます。

ランキングサイト


↓ランキング参加中




にほんブログ村 その他日記ブログ 日々のできごとへ

blog Ranking


お勉強BLOGЯanK

リンク

カテゴリー

メールフォーム

名前:
メールアドレス:
件名:
本文:

ブロとも申請フォーム

この人とブロともになる

FC2カウンター

月別アーカイブ

ブログ内検索

RSSフィード