• 締切済み

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

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

例によって書き込みミス。 (誤)(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)

tama_55
質問者

お礼

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

回答No.3

なかなか巧妙な方法だ。 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つほどあるが、その中で不定方程式を使う解を紹介する。 求める数をNとし、N=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. よって、N=3a+2=5b+4=7c+4 =105*m+74. 従って、題意の通りに成立する。

  • Mr_Holland
  • ベストアンサー率56% (890/1576)
回答No.2

 #1です。  補足を拝見しました。 >tiのほうに関して、ti=Niをbiで割った余りだとすると >t1 = 1, t2 = 1, t3 = 3 >にはなりませんか?  ご指摘の通りです。  誤記をしました。済みません。  ti=Niをaiで割った余り です。

tama_55
質問者

お礼

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

  • Mr_Holland
  • ベストアンサー率56% (890/1576)
回答No.1

 N1=a2 a3, N2=a3 a1, N3=a1 a2  ti=Niをbiで割った余り

tama_55
質問者

補足

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

関連するQ&A

専門家に質問してみよう