次の問題は小学校5・6年の参考書に載ってあったのですが、この問題を見て疑問に思ったことがあります。
【問題】12,18のどちらで割っても3余る数のうち、最も小さい整数を求めなさい。
この問題は、どちらで割っても余りが同じになるので、最小公倍数をgcd(a,b)で表すとすると、
gcd(12,18)+3=39
で解けるのですが、
(割ると3余るということは、割られる数は割る数の倍数より3大きいということになるから。)
余る数が違ったらどうやって解くんだ!!という疑問が生まれてしまいました。
問題にしてみると、次のようになります。
【問題】aで割ると余りがpになり,bで割ると余りがqになる数のうち、n番目の整数を求めよ。
ただし、最小公倍数をgcd(a,b)で表すものとする。
条件を満たす整数を1番目に限定しないようにしました。
これがp=q=rなら、gcd(a,b)n+rで簡単に求められるのですが、上のように余りが異なる場合はどうやって求めれば良いのでしょうか?
No.1
- 回答日時:
最も簡単なのは
一方の条件を満たすものを列挙し, もう一方の条件が成り立つかどうか調べる
ことなんだけど... ダメ?
ちなみに最初の問題の答えは 3 かも.
この回答への補足
>ちなみに最初の問題の答えは 3 かも
すみません。参考書には"2ケタの"という記述がありました。
問題文を訂正します。
【問題】12,18のどちらで割っても3余る数のうち、最も小さい2ケタの整数を求めなさい。
いや、しらみ潰しに探してたら100番目や200番目などを求めるのは流石に無理でしょう。
やっぱり計算で求められないとなぁ~
回答ありがとうございました。
No.2
- 回答日時:
ちょっと面白そうなので参戦。
まずベーシックな問題は
m,nを整数として
am + r = bn + r
なので、am=bn となる整数から最小公倍数で求めることができます。
> 【問題】aで割ると余りがpになり,bで割ると余りがqになる数のうち、n番目の整数を求めよ。
この問題については
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)
が求める答えとなります。
なるほど、1番目は最小公倍数で求めるのは無理でしたか。
そうなると1番目の値は自力で探すしかなさそうだなぁ~
aとbの値が小さければ見つけられそうだが、大きくなると無理かも・・・
回答ありがとうございました。
No.3
- 回答日時:
ども。
「最小公倍数が意味をなさない」
それだけです。
違う数字で割るのですから、倍数ではないのでね^^;
例題のように、同じ数字で割るから、{(最小公倍数)×n+あまり}
とできるだけ。違う数字で割るのなら、
片方の条件から、絞り込むしか今思いつかない。
#No.1さんにおなじく。
ところで、 r ってなに?
もちろん見て分かるけど、「r=p=q として」
たったこの一文書くだけで、一目で分かるのに、そういうところでサボってはダメよ。
nもそう。n番目はいいけど、「小さい順に」と一言つけないとね。
決め事を自分でやるときには、みんなに分かるように。
#0番目 はどうする? nが決めてないから、1.5番目なんていうこともできるよ?
意地悪なようだけど、こういうのはきちんとね~。
自分ひとりで納得しないでね。考えるほうが余計なことしなくていいようにするのが親切です。
(=^. .^=) m(_ _)m (=^. .^=)
やっぱり1番目は最小公倍数で解けないのですね。
それにしても文の指摘が細かいですね~
自分は分かりやすく書いているつもりなんですが・・・
回答ありがとうございました。
No.5
- 回答日時:
この場合の整数は自然数のことですな。
したがって12,18 のどちらで割っても 3 余る整数の中で最小のものを求めなさい。
の答えは 3 です。
すみません。問題文には"2ケタの"を入れてませんでした。
訂正した問題文はNo.1さんの補足で記述しています。
回答ありがとうございました。
No.6
- 回答日時:
や, 1つ見付ければあとは「最小公倍数を足すだけ」なのは明らか (#2 及び #4) ですから, 「その『1つ』をどう見付けるか」という話だと思ってたんですけど....
もっとも, a や b が巨大だとその「1つ」を見付けるのもしらみつぶしではできないわけですが. 単に 2元1次不定方程式を解けばいいだけだから「方法」はあるんだけど, それを「小学校5・6年生に教える」のは... 無理かなぁ.
不定方程式っていうとx+2y=3のような式ですか?
なるほど、不定方程式を使うのですね。
習ったことはないので、解き方は分かりませんが・・・
回答ありがとうございました。
No.7
- 回答日時:
ども、No.3です。
あ~、勘違いしてた><ゴメン。
最小公倍数は、最初の一つの答え (n=1かな)を求めるのに意味がない。
こう訂正しなきゃね。
そうだね、最小公倍数を足せば、自動的に二番目に小さい数字になるか。
小学生だけじゃなくても、結構面倒になりそうな気がするよ~。
#未定定数法かなにかで、いくの?
二元一次の不定方程式になるのかな? 数論かな~。
苦手じゃ~>< σ(・・*)は代数屋>< 専門だけどね^^;
群論でやったほうが早そうかな?
実際数字があると、群論のが早いかも? わからない。。
もろもろゴメン m(_ _)m
(=^. .^=) m(_ _)m (=^. .^=)
最小の整数をAとすると
A mod a =p
A mod q =q
となるAを探せばいいわけですから、どなたか書かれているような変形になるね。
不定方程式とか数論とか群論とか色んな分野が出てきましたか。
どれも習っていないのでどんな内容かは知りませんが、色んな分野が出てくるということは、この問題を解く方法は1つとは限らないのかな?
回答ありがとうございました。
No.8
- 回答日時:
#2です。
追加します。> もしかして、どんなにaとbの値が大きくても、一番目の値は自力で探すしかないのでしょうか?
まず、題意に合う数が必ず存在するわけではありません。
例えば12で割ると2あまり、18で割ると5余る整数は存在しません。
次に、一番目の値ですが、一番目かどうかはともかくとして、一つを見つける方法は比較的簡単に求めることが出来ます。
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の倍数から1を引いた数がbの倍数であればよいことになります。その時のxをx_0として
A' = a(p-q)x_0 + p
となります。あとは、GCDで割った余りとしてAにたどりつけます。
更に、ax+1がbの倍数にならないケースです(上述のケースがそうです)。
この場合には、{(a-b)x+1}(p-q)がbの倍数であり、{(a-b)x+1}がbの倍数ではないので、少なくとも(p-q)はbの約数のはずです。したがって、
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の倍数から1を引いた数がbの倍数であればよいことになります。
つまり、a-1,2a-1,3a-1と探してbの倍数になる数を見つければよいということでしょうか?
(でもそれだと自力で探してることになっちゃうよな~)
>その時のxをx_0として
>A' = a(p-q)x_0 + p
>となります。
すみません。この部分がよく分かりませんでした。
どうしてb(y+x)=ax-1という式から、上式が得られたのでしょうか?
No.9
- 回答日時:
試しに目標の数と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.10
- 回答日時:
すみません。
うまく説明しようとして、間違ってしまいました--以下修正--
試しに目標の数と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は必ず最大公約数倍ですし)
この回答への補足
>0<=t<=bで必ず解があります(t=bはq-pが負の場合であり得ます)
どんなにbの値が大きくてもtは0<=t<=bの範囲で地道に探索するしかないのでしょうか?
>解がないときはq-pがaとbの最大公約数倍にならないときです
>(sは必ず最大公約数倍ですし)
最大公約数倍とはどういうことでしょうか?
例えば、12で割ると余りが6になり,16で割ると余りが10になる整数は42がありますが、q-pは10-6=4になり、12と16の最大公約数は4になります。
上記の問題は解があるので、4が4倍ということになりますが、「4が4倍」とはどういう意味でしょうか?
4は何らかの整数の4倍になっているという意味でしょうか?
だとしたら、どうして「q-pがaとbの最大公約数倍」になるのでしょうか?
やっぱり難しいですね。
理解するのに時間がかかってしまいました。
それでも、まだ最後の部分は理解出来てませんが・・・
そういえば誰にも指摘されませんでしたが、G.C.Dって最大公約数の方でしたね。(今気付いた)
まぁ問題文には「最小公倍数をgcdとする」としているから良しとするか。
回答ありがとうございました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C#の問題で2つの整数a,bの最大公約数(GCD)を求めるユークリッドの互除法は,aをbで割った余り 2 2022/06/26 16:52
- その他(教育・科学・学問) 小学生の算数の商について 3 2023/03/06 14:11
- 大学受験 合同式 1 2022/09/03 12:37
- 数学 整数問題についてですが、 「正の整数aに対してa²を4で割ったときの余りを求めよ」という問題で、答え 12 2023/08/28 15:03
- 数学 中2 数学 8 2023/06/27 21:56
- 数学 合同式について 3 2022/05/03 23:14
- 数学 数学(質問の内容に誤りがあったので再度質問させて頂きます) 連続した3つの奇数の和は、6で割ると3余 3 2023/01/20 21:30
- 数学 どうか教えてください。 4 2022/07/02 20:18
- 大学受験 合同式 2 2022/08/19 13:12
- 数学 正の数aは4の倍数で、7でわると2余る数である。√576-aが正の整数となるようなaの値を求める 12 2023/06/19 19:34
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
小学校4年生の算数の教科書で...
-
x³+1で割ると余りが2x+3であり...
-
4の100乗を、7で割った余りとい...
-
1から9の数字を書いたカードが...
-
2は5で割り切れません。 あまり...
-
190分はなん時間何分ですか?
-
0は奇数か偶数なのか?
-
問題 整式X³+X²-2X+1を整式B...
-
10進法⇒2進法には何故2で割るか
-
小学生への割り算の答えの確か...
-
解き方を教えてください。 中3...
-
例題39の一の位は10で割った余...
-
剰余演算子(%)を使用しないで余...
-
場合の数 漏れなく数える方法
-
1から9の数字を五乗してでき...
-
高一数学のめっちゃ最初のほう...
-
有理数を小数で表すと有限小数...
-
高1数学Aの問題で、 「a、bは整...
-
読んで割っても6で割っても3余...
-
0から9までの数字を使ってでき...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
190分はなん時間何分ですか?
-
2は5で割り切れません。 あまり...
-
小学校4年生の算数の教科書で...
-
負の余りはあり得ますか?
-
剰余演算子(%)を使用しないで余...
-
0から9までの数字を使ってでき...
-
高1数学Aの問題で、 「a、bは整...
-
10進法⇒2進法には何故2で割るか
-
1から9の数字を書いたカードが...
-
問題 整式X³+X²-2X+1を整式B...
-
これの求め方を教えて下さい!...
-
4の100乗を、7で割った余りとい...
-
1 から 9 までの数字を使って引...
-
20人を4人の5チームに分ける通...
-
下記の問題について、「5は素数...
-
1000本のワインがあって、1つは...
-
Accessで割り算の余りを求める...
-
〖エクセル〗MOD関数で、小さな...
-
0は奇数か偶数なのか?
-
有理数を小数で表すと有限小数...
おすすめ情報