前から代数で気になっててんけど、中国式剰余定理ってやつがあるねん。
名前に魅かれてたわけやな。
それで今日はその話やねんけど、まずは中学受験ぐらいのレベルの話やからみんな聞いたってくれ。
それでどんなのかと言うと、中国の算術書「孫子算経」には
「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で割った余りに等しい。
まあ色々ためしてくれ。
ここまでは、ええとして本当の代数としての中国式剰余定理って言うのは、もっと凄いことを言うてて
中国式剰余定理
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 5)
(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∈I_1,x_2∈I_2が存在して
任意の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)
(=は同型)
よって数学的帰納法により題意成立。
数学、物理
高校数学の公式や問題の解説
中学数学の問題や公式
中学受験の算数の問題の解答や解説
整数問題の解法の解説と問題演習
- 関連記事
-
テーマ:日記 - ジャンル:日記
|
