この問題について教えてください。(中国の剰余定理？)

x を3 で割って2 余り、 5 で割って4 余り、 7 で割って4 余る数とする。このとき、 x を105 = 3・5・7 で割った余りを求めてみよう。今、
a1 = 3, a2 = 5, a3 = 7,
b1 = 2, b2 = 4, b3 = 4 である。
したがって、N = 105, N1 = 35, N2 = 21, N3 = 15 で、
これらからti を求めると、t1 = 2, t2 = 1, t3 = 1 である。
よって、
y = 2・35・2 + 4・21・1 + 4・15・1
= 140 + 84 + 60 = 284
したがって284 を105 で割って、 74 が余りである。

この問題についてN1～N3とt1～t3をどのように求めているのかがわかりません。よろしければ教えてください。

No.4 回答者： mister_moonlight 回答日時： 2009/05/24 14:31

例によって書き込みミス。

（誤）(1)と(2)から、a＝5n＋4＝7k＋3であるから、mを非負の整数としてこの不定方程式を解くと、a＝5m＋3、c＝7m＋4.　‥‥(3)

（正）(1)と(2)から、a＝5n＋4＝7k＋3であるから、mを非負の整数としてこの不定方程式を解くと、k＝5m＋3、n＝7m＋4.　‥‥(3)

この回答へのお礼

とても難しいですが、なんとか理解できたかと思います。
ありがとうございました。

お礼日時：2009/05/24 17:19

No.3 回答者： mister_moonlight 回答日時： 2009/05/24 14:23

なかなか巧妙な方法だ。

xとyを題意を満たす一般的数とすると、x-yは3でも、5でも、7でも割り切れるから、x-y＝105n　つまり　x＝y＋105n　。
この形から、xを105で割った時のあまりは、yを105で割った時のあまりに等しい。
そこで、特別にこのようなyを一つ見つければ、その数で余りを求めると良い。

y＝3*5*a＋3*7*b＋5*7*c （a、b、cは0以上の整数）と置く。←　これが、巧妙。

yを3で割る時の余りは、35＝3*11＋2であるから、2cを割る時のあまりに等しく、それで余りが2になるから、2c＝2　つまり　c＝1.
3*7＝5*4＋1であるから、b＝3とすると、yを5で割ると余りは4.
3*5＝7*2＋1であるから、a＝4とすると、yを7で割ると余りは4.
従って、y＝3*5*a＋3*7*b＋5*7*c＝y＝3*5*4＋3*7*4＋5*7*1＝60＋84＋35＝179＝105＋74.

考えられる方法は、他に2つほどあるが、その中で不定方程式を使う解を紹介する。

求める数をＮとし、Ｎ＝3a+2＝5b＋4＝7c＋4 、（a、b、cは0以上の整数）。
3a+2＝5b＋4より、nを非負の整数として不定方程式を解くと、a＝5n＋4、b＝3n＋2.　‥‥(1)
3a+2＝7c＋4 より、kを非負の整数として不定方程式を解くと、a＝7k＋3、c＝3k＋1.　‥‥(2)
(1)と(2)から、a＝5n＋4＝7k＋3であるから、mを非負の整数としてこの不定方程式を解くと、a＝5m＋3、c＝7m＋4.　‥‥(3)
以上から、a＝7k＋3＝35m＋24、b＝3n＋2＝21m＋14、c＝3k＋1＝15m＋10.
よって、Ｎ＝3a+2＝5b＋4＝7c＋4 ＝105*m＋74.
従って、題意の通りに成立する。

No.2 回答者： Mr_Holland 回答日時： 2009/05/24 14:09

　＃１です。

　補足を拝見しました。

＞tiのほうに関して、ti=Niをbiで割った余りだとすると
＞t1 = 1, t2 = 1, t3 = 3
＞にはなりませんか？

　ご指摘の通りです。
　誤記をしました。済みません。

　ti＝Niをaiで割った余り　です。

この回答へのお礼

なるほど、その計算なら問題の通りになりますね。
やっと理解できました。ありがとうございました。

お礼日時：2009/05/24 17:16

No.1 回答者： Mr_Holland 回答日時： 2009/05/24 11:53

　N1=a2 a3, N2=a3 a1, N3=a1 a2

　ti=Niをbiで割った余り

この回答への補足

回答ありがとうございます。
しかし、Niのほうに関しては納得できたのですが、
tiのほうに関して、ti=Niをbiで割った余りだとすると
t1 = 1, t2 = 1, t3 = 3
にはなりませんか？
理解できず申し訳ありません・・・。

補足日時：2009/05/24 12:28