プロが教える店舗&オフィスのセキュリティ対策術

ある正の整数をAで割るとaあまり、Bで割るとbあまる。
この数をABで割ったあまりはいくつですか?(A,B,a,bはすべて正の整数)

このような問題で、少しも書き並べたりすることなく、解く方法はありますか?
わかりにくかったらごめんなさい。

質問者からの補足コメント

  • 11で割って2余り、13で割って4余る時はどうですか?

      補足日時:2016/04/06 22:52

A 回答 (6件)

ある正の整数をXとおくと、正の整数y、zを用いて、


X=yA+a=zB+b
と表される。

更に、正の整数c、d、e、fを用いて
y=cB+d、z=eA+f(dはBで割り切れない数、fはAで割り切れない数)
とおくと、
X=cAB+dA+a=eAB+fB+b

XをABで割った余りは
dA+a=fB+b(<AB)
である。

A、B、a、bは与えられているとすると、上式を満たす(d,f)の組が見つかれば、それが解となる。

例えば、No.1のお礼について
>3で割って2余り、7で割って1余る数は21で割るといくつ余るのかをどのように知るのですか?

A=3、B=7、a=2、b=1より、
3d+2=7f+1
3d+2≡2(mod 3)
7f+1≡f+1=2(mod3)
従って正の整数gを用いるとf=3g+1が解の候補となる。
f=1、4、7、10、…
f=4の時、7f+1=22>21=ABであるため、不適。

答えはf=1の場合のみで、7f+1=8が余りであると決定される。
    • good
    • 1
この回答へのお礼

わかりやすく、詳しい回答ありがとうございます!
今日学校で聞いたら、それは無理じゃないかなと先生に言われたので、とても嬉しいです!
ありがとうございます!

お礼日時:2016/04/06 19:49

A=11、B=13、a=2、b=4


11d+2=13f+4
11d+2≡2(mod 11)
13f+4≡2f+4=2(mod 11)

f=4の時2f+4≡1(mod11)
f=10の時2f+4=24≡2(mod11)
f=16の時2f+4=36≡3(mod11)

f=76の時2f+4=156≡2(mod11)

従って、f=10、76、142、…が候補
しかし、条件に合うのはf=10の時だけだから、
13f+4=134が余り。
    • good
    • 0
この回答へのお礼

ありがとうございます。
少し勘違いをしていただけでした。

お礼日時:2016/04/07 07:05

ん? 11 で割って 2 余り, 13 で割ると 4 余るって?



143 で割ったら 134 余るな.
    • good
    • 0
この回答へのお礼

すいません。なんか勘違いしてたみたいです。…

お礼日時:2016/04/07 00:19

所々正の整数と書いてしまいましたが、0を含む自然数と適宜読み替えてください。



さて、例題として
A=12、B=24、a=2、b=1を考えてみる。
12d+2=24f+1
24f+1≡1(mod 24)
12d+2≡12d+2=1(mod 24)
このような条件を満たすdは存在しない。
→題意を満たす数は存在しない。

という事も示せる。
    • good
    • 1
この回答へのお礼

自分でやってみて納得することが出来ました!
一見複雑そうに見えますが、やってみたらすぐ答えがわかりとても助かります。
ほんとうにありがとうございます!

お礼日時:2016/04/06 22:43

そのくらいだと実はベタベタ書き出した方が速かったりする (苦笑). 7 で割って 1 余るのは


1, 8, 15, 22, 29, ...
で, このうち「3 で割って 2 余る」のは 8 からスタート. はい終わり.

それはさておき, システマティックにはユークリッドの互除法に基づく手法がよく知られている. 例えば「3 で割って 2 余り, 7 で割って 1 余る数」というのは 2つの整数 x, y を使って
3x+2 = 7y+1 (1)
と書ける. 整理すると
3x-7y = -1
なわけだが, ここで「7 を 3 で割ると商が 2 で余り 1」となることから左辺を
3(x-2y) - y = -1
と書きなおせる. 今 z=x+2y と置きなおすと
3z - y = -1
となるが, これは
y = 3z+1
を意味し, (1) に代入すると求める数は
7(3z+1)+1 = 21z+8
と書ける. つまり 21 で割ると 8 余る.

今の例だと 7 を 3 で割って 1 余るから z で置きなおした後すぐ元の式に戻したけど, ここで余りが 2以上のときは同じように割った商と余りを使って置きなおす処理を繰り返すことで, いつかは余りが 1 になる (ただし A と B が 1 でない公約数を持つとこの部分が成り立たないので注意).
    • good
    • 1
この回答へのお礼

ありがとうございます!!
知りたかったことがしれてとても嬉しいです!

お礼日時:2016/04/06 16:28

「少しも書き並べたりすることなく」ってのは, 何を「少しも書き並べたりすることなく」ってことなんでしょうか? 全く何も書かないわけ

にはいかないと思うんですが... といいつつ, 実はこの条件から決められないんだよなとかこぼしてみる.
    • good
    • 1
この回答へのお礼

表現がうまくいかず申し訳ありません。
書き並べるというのは無視して回答して頂いて構いません。
例えば
3で割って2余り、7で割って1余る数は21で割るといくつ余るのかをどのように知るのですか?

お礼日時:2016/04/06 14:56

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