先日、同じような問題の解き方を教えてもらったのですが、少し問題が変わったとたん、まったく解けなくなってしまいました。

(1) 5で割って2、7で割って3、11で割って5余る数は385で割っていくつ余るか。
(2) 3で割って1、5で割って3、7で割って4、11で割って8余る数は1155で割っていくつ余るか。

(1)の3つの数で割る数の方は教えてもらったやり方で解いて出た答えが間違った答えになってしまいます。(2)の4つの数で割る方はやり方すらわかりません。
よろしければこれらの問題について教えていただきたいと思います。

A 回答 (2件)

 前回、間違った回答をしてしまったものです。


 まずはお詫びいたします。
 そして、つぎのように訂正させてください。

 ai: 割る数
 bi: aiで割ったときの余り
 N : =Πai
 Ni: =N/ai
 ti: Ni*ti≡1(mod ai) となるような最小の正整数

 そして、これに当てはめたときの各パラメータを以下に記します。

(1)
 ai...5...7..11
 bi...2...3...5
 Ni..77..55..35 (N=385)
 ti...3...6...6

 Σbi*Ni*ti=2502
∴2502 (mod 385)≡192

(2)
 ai...3...5...7..11
 bi...1...3...4...8
 Ni.385.231.165.105 (N=1155)
 ti...1...1...2...2

 Σbi*Ni*ti=4078
∴4078 (mod 1155)≡613
    • good
    • 0
この回答へのお礼

前回に引き続きありがとうございました。
おかげさまでいろいろと理解することができたのでよかったです。

お礼日時:2009/05/25 03:35

(1)について


まず、問題となっている数をNと置くと、最初の3つの条件は
N = 5Q+2 …(1)
N = 7Q'+3 …(2)
N = 11Q''+5 …(3)
と表されます。(Q、Q'、Q''は適当な数です。重要ではありません。)

385 = 5*7*11であることに注目して、(1)を7*11倍、(2)を5*11倍、(3)を5*7倍すると
77N = 385Q+154 …(4)
55N = 385Q'+165 …(5)
35N = 385Q''+175 …(6)
となります。

あとはこれをうまく足し引きして、Nの係数が1になればOKです。
少しひらめきが必要になりますが、(4)*3 - (5)*1 - (6)*5でなんとかなります。
計算して、余りがプラスになるように調節すると
N = 385(3Q-Q'-5Q'')-548 = 385(3Q-Q'-5Q''-2)+222
このような結果が得られ、余りが222となるはずです。

(2)についても、同様の計算で答えが得られるはずです。

しかし計算量が増え、ひらめきが難解になります。
ひょっとしたら、もっとスマートな計算方法があるかもしれません。
    • good
    • 0
この回答へのお礼

ありがとうございました。なんとか解くことができました。
(2)の方も係数が1になるような足し引きも割と簡単に見つけられたのでよかったです。

お礼日時:2009/05/25 03:33

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング