倍数の問題

質問

次の問題は小学校５・６年の参考書に載ってあったのですが、この問題を見て疑問に思ったことがあります。

【問題】１２，１８のどちらで割っても３余る数のうち、最も小さい整数を求めなさい。

この問題は、どちらで割っても余りが同じになるので、最小公倍数をｇｃｄ（ａ，ｂ）で表すとすると、
　ｇｃｄ（１２，１８）＋３＝３９
で解けるのですが、
（割ると３余るということは、割られる数は割る数の倍数より３大きいということになるから。）
余る数が違ったらどうやって解くんだ！！という疑問が生まれてしまいました。

問題にしてみると、次のようになります。

【問題】ａで割ると余りがｐになり，ｂで割ると余りがｑになる数のうち、ｎ番目の整数を求めよ。
ただし、最小公倍数をｇｃｄ（ａ，ｂ）で表すものとする。

条件を満たす整数を１番目に限定しないようにしました。
これがｐ＝ｑ＝ｒなら、ｇｃｄ（ａ，ｂ）ｎ＋ｒで簡単に求められるのですが、上のように余りが異なる場合はどうやって求めれば良いのでしょうか？

回答No.11

hrsmmhr · ベストアンサー

確かに地道ですが、stがsについて等差数列ですので
q-p=s0t+z0=b+s1t+z1とすれば
b+(s1-s0)t=z0-z1のように+bになるまでにどれくらいq-pに近くなるとか、遠くなるとか
いろいろ推測できて、どこらあたりを計算したほうが良いかなど、目星がつけれて
一個づつsを加算していくといった、本当の地道とは少し違うとは思います

それと最大公約数倍とは、正しいほうのgcdで
q-p=gcd(a,b)*n (nは整数)になることをいってます
ですからa=12, b=16でq-p=4=gcd(12,16)*1は解があります
a=12,b=16,q-p=3だと（例えば12で割って7余り、16で割って4余る等）みて明らかです
ちなみにq-p=2でも全部2で割ってもらえば解りますがa'=6,b'=8,q'-p'=1は
q-p=3と同様に解がすぐに解ります

お礼

なるほど、おおよその目星をつけて探索すればよいのですね。
色々とありがとうございました。

回答No.10

hrsmmhr

すみません。うまく説明しようとして、間違ってしまいました
－－以下修正－－
試しに目標の数とa,bそれぞれの余りを-pしてみますと
atがbで割って余りがq-pになるのはいくつかという問題に置き換わり

aとbが互いに素ならZ/bZでatは0<=t<gcd(a,b)/a=bでそれぞれ1～b-1の異なる剰余類に属し
その余りはst(mod b)です
つまりq-p=st(mod b)
は0<=t<=bで必ず解があります(t=bはq-pが負の場合であり得ます)

解がないときはq-pがaとbの最大公約数倍にならないときです
(sは必ず最大公約数倍ですし)

お礼

やっぱり難しいですね。
理解するのに時間がかかってしまいました。
それでも、まだ最後の部分は理解出来てませんが・・・
そういえば誰にも指摘されませんでしたが、G.C.Dって最大公約数の方でしたね。（今気付いた）
まぁ問題文には「最小公倍数をgcdとする」としているから良しとするか。

回答ありがとうございました。

補足

＞0<=t<=bで必ず解があります(t=bはq-pが負の場合であり得ます)
どんなにｂの値が大きくてもｔは０＜＝ｔ＜＝ｂの範囲で地道に探索するしかないのでしょうか？

＞解がないときはq-pがaとbの最大公約数倍にならないときです
＞(sは必ず最大公約数倍ですし)
最大公約数倍とはどういうことでしょうか？
例えば、12で割ると余りが６になり，16で割ると余りが10になる整数は42がありますが、ｑ－ｐは10－6＝4になり、12と16の最大公約数は４になります。
上記の問題は解があるので、４が４倍ということになりますが、「４が４倍」とはどういう意味でしょうか？
４は何らかの整数の４倍になっているという意味でしょうか？
だとしたら、どうして「ｑ－ｐがａとｂの最大公約数倍」になるのでしょうか？

回答No.9

hrsmmhr

試しに目標の数とa,bそれぞれの余りを-pしてみますと
xb+q-pがaの倍数になるのはいくつかという問題に置き換わり

aとbが互いに素ならZ/aZでrbtは0<=t<gcd(a,b)/b=aでそれぞれ1～a-1の異なる剰余類に属し
その余りは-stです
つまりq-p-st=0(mod a)
(今気づきましたがここ間違ってました)
は0<=t<=aで必ず解があります(t=aはq-pが負の場合であり得ます)

解がないときはq-pがaとbの最大公約数倍にならないときです
(sは必ず最大公約数倍ですし)

お礼

回答ありがとうございます。
訂正版の方を読ませて頂きます。

回答No.8

at9_am

＃２です。追加します。

> もしかして、どんなにａとｂの値が大きくても、一番目の値は自力で探すしかないのでしょうか？

まず、題意に合う数が必ず存在するわけではありません。
例えば12で割ると２あまり、18で割ると５余る整数は存在しません。

次に、一番目の値ですが、一番目かどうかはともかくとして、一つを見つける方法は比較的簡単に求めることが出来ます。

am + (p-q) = bn
を変形すると、
bn = am + p-q
= bm + (a-b)m + p-q
b(n-m) = (a-b)m + p-q
となります。したがって、p=q=rのとき
b(n-m) = (a-b)m
となるので、必ず題意を充たす整数の組が存在します。

ここでm=(p-q)xとすると（xは整数）
b(n-m) = (a-b)(p-q)x + p-q
= {(a-b)x+1}(p-q)
となるので、結局、yを整数として
{(a-b)x+1}=by
とかければ良いことになります。ここから
by = ax - bx + 1
b(y+x) = ax-1
となり、aの倍数から１を引いた数がbの倍数であればよいことになります。その時のxをx_0として
A' = a(p-q)x_0 + p
となります。あとは、GCDで割った余りとしてＡにたどりつけます。

更に、ax+1がbの倍数にならないケースです（上述のケースがそうです）。
この場合には、{(a-b)x+1}(p-q)がbの倍数であり、{(a-b)x+1}がbの倍数ではないので、少なくとも(p-q)はｂの約数のはずです。したがって、
b' = b÷(p-q)を考えれば
b' = (a-b)x+1
= ax-b'(p-q)x+1
b'{1+(p-q)x}= ax+1
を充たすxを考えれば良いことになりますので、
ax-1がb'の倍数になっているものを探せばよいことになります。あとは同様に求められます。

お礼

値一つを見つけるだけでも、これだけ複雑な式になるとは・・・
思ったより難しい問題だったようだ。

回答ありがとうございました。

補足

＞by = ax - bx + 1
＞b(y+x) = ax-1
あれ？ bxを左辺に移項したら右辺の+1が-1に変わってる！！
どうして符号が変わったのでしょうか？

＞aの倍数から１を引いた数がbの倍数であればよいことになります。
つまり、a-1，2a-1，3a-1と探してｂの倍数になる数を見つければよいということでしょうか？
（でもそれだと自力で探してることになっちゃうよな～）

＞その時のxをx_0として
＞A' = a(p-q)x_0 + p
＞となります。
すみません。この部分がよく分かりませんでした。
どうしてb(y+x)=ax-1という式から、上式が得られたのでしょうか？

回答No.7

B-juggler

ども、Ｎｏ．３です。

あ～、勘違いしてた＞＜ゴメン。

最小公倍数は、最初の一つの答え　（ｎ＝１かな）を求めるのに意味がない。

こう訂正しなきゃね。

そうだね、最小公倍数を足せば、自動的に二番目に小さい数字になるか。

小学生だけじゃなくても、結構面倒になりそうな気がするよ～。

　＃未定定数法かなにかで、いくの？

二元一次の不定方程式になるのかな？　数論かな～。

　苦手じゃ～＞＜　σ(・・*)は代数屋＞＜　専門だけどね＾＾；

群論でやったほうが早そうかな？

実際数字があると、群論のが早いかも？　わからない。。

もろもろゴメン　ｍ（＿　＿）ｍ

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

最小の整数をＡとすると

Ａ　ｍｏｄ　ａ　＝ｐ

Ａ　ｍｏｄ　ｑ　＝ｑ

となるＡを探せばいいわけですから、どなたか書かれているような変形になるね。

お礼

不定方程式とか数論とか群論とか色んな分野が出てきましたか。
どれも習っていないのでどんな内容かは知りませんが、色んな分野が出てくるということは、この問題を解く方法は１つとは限らないのかな？

回答ありがとうございました。

回答No.6

Tacosan

や, 1つ見付ければあとは「最小公倍数を足すだけ」なのは明らか (#2 及び #4) ですから, 「その『1つ』をどう見付けるか」という話だと思ってたんですけど....

もっとも, a や b が巨大だとその「1つ」を見付けるのもしらみつぶしではできないわけですが. 単に 2元1次不定方程式を解けばいいだけだから「方法」はあるんだけど, それを「小学校5・6年生に教える」のは... 無理かなぁ.

お礼

不定方程式っていうとｘ＋２ｙ＝３のような式ですか？
なるほど、不定方程式を使うのですね。
習ったことはないので、解き方は分かりませんが・・・

回答ありがとうございました。

回答No.5

noname#157574

この場合の整数は自然数のことですな。したがって
12，18 のどちらで割っても 3 余る整数の中で最小のものを求めなさい。
の答えは 3 です。

お礼

すみません。問題文には"２ケタの"を入れてませんでした。
訂正した問題文はＮｏ．１さんの補足で記述しています。

回答ありがとうございました。

回答No.4

hrsmmhr

a>bとして
a=rb+s:0<r∈Z,s∈Z,0=<s<rとしたとき
q-p=st(mod b)となる最小の0<t∈Zを求めると
A=at+p=(rb+s)t+p=rtb+q-p+ub+p=(rt+u)b+q　(u∈Z)
が最初の条件を満たす整数
A(n)=A+gcd(a,b)*(n-1)

お礼

これは難しいですな～
Ａを求めるまでの過程で頭が混乱してしまいました。
だけど、Ａを求めるのに新しくｔやｕが登場しているから、Ａは自力で求めるしかないのかな？

回答ありがとうございました。

回答No.3

B-juggler

ども。

「最小公倍数が意味をなさない」

それだけです。

違う数字で割るのですから、倍数ではないのでね＾＾；

例題のように、同じ数字で割るから、｛（最小公倍数）×ｎ＋あまり｝

とできるだけ。違う数字で割るのなら、

片方の条件から、絞り込むしか今思いつかない。

　＃Ｎｏ．１さんにおなじく。

ところで、　ｒ　ってなに？

もちろん見て分かるけど、「ｒ＝ｐ＝ｑ　として」

たったこの一文書くだけで、一目で分かるのに、そういうところでサボってはダメよ。

ｎもそう。ｎ番目はいいけど、「小さい順に」と一言つけないとね。

決め事を自分でやるときには、みんなに分かるように。

　＃０番目　はどうする？　ｎが決めてないから、１．５番目なんていうこともできるよ？

意地悪なようだけど、こういうのはきちんとね～。

自分ひとりで納得しないでね。考えるほうが余計なことしなくていいようにするのが親切です。

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

お礼

やっぱり１番目は最小公倍数で解けないのですね。
それにしても文の指摘が細かいですね～
自分は分かりやすく書いているつもりなんですが・・・

回答ありがとうございました。

回答No.2

at9_am

ちょっと面白そうなので参戦。

まずベーシックな問題は
m,nを整数として
am + r = bn + r
なので、am=bn となる整数から最小公倍数で求めることができます。

> 【問題】ａで割ると余りがｐになり，ｂで割ると余りがｑになる数のうち、ｎ番目の整数を求めよ。

この問題については
am + p = bn + q
am + (p-q) = bn
となり、最初から最小公倍数では求めることができません。

最初の一個は
n = (am + p-q)/b
が整数から、am+p-qがbの倍数になる最小のmを求めることで求めることができます。

今、この式を充たす整数の組を(m_1, n_1), (m_2, n_2),...とすることにしましょう。すると
a m_1 + p = b n_1 + q
a m_2 + p = b n_2 + q
となるので、二式を引くと
a (m_2 - m_1) = b (m_2 - m_1)
となります。つまり、二つ目以降は公倍数になります。

したがって、一番最初のものを考え、Aとすれば、
A + n × gcd(a, b)
が求める答えとなります。

お礼

なるほど、１番目は最小公倍数で求めるのは無理でしたか。
そうなると１番目の値は自力で探すしかなさそうだなぁ～
ａとｂの値が小さければ見つけられそうだが、大きくなると無理かも・・・

回答ありがとうございました。

補足

もしかして、どんなにａとｂの値が大きくても、一番目の値は自力で探すしかないのでしょうか？

回答No.1

Tacosan

最も簡単なのは
一方の条件を満たすものを列挙し, もう一方の条件が成り立つかどうか調べる
ことなんだけど... ダメ?

ちなみに最初の問題の答えは 3 かも.

お礼

いや、しらみ潰しに探してたら１００番目や２００番目などを求めるのは流石に無理でしょう。
やっぱり計算で求められないとなぁ～

回答ありがとうございました。

補足

＞ちなみに最初の問題の答えは 3 かも

すみません。参考書には"２ケタの"という記述がありました。
問題文を訂正します。

【問題】１２，１８のどちらで割っても３余る数のうち、最も小さい２ケタの整数を求めなさい。