洛星中学入試の問題で

質問

問１は、４と５をおのおの複数個足して、１～２０までにつくれない数を求める問題でした。
例えば、１７は５＋４＋４＋４で、１８は５＋５＋４＋４で作れます。

で、問２なのですが、１２０と４５を複数個足して数をつくるとき、（　　(1)　　）ｇおきに
（　(2)　　　）ｇ以上の数はすべてつくれる．．最少の(1)、(2)を求めよという問題ですが

答えは、a、bを互いに素とするとき、０以上の整数ｘ、ｙをつかってa＊ｘ＋ｂ＊ｙで表せない
もっとも大きな整数はa＊ｂ-a-bだから．．．とあるのですが、これって小学校で習う
自明な事なのですか？　どうやって証明するのですか？
（＊は掛け算の意味で使いました）

回答No.2

mister_moonlight · ベストアンサー

これ、本当に中学入試問題なの？
高校生でも、どうかな？　という問題だよ。

これは、フエルマーの小定理に関連してくる。
証明は到底、小学生には無理。
ＵＲＬを貼っとく。

http://homepage3.nifty.com/sugaku/itijifutei.htm

その定理(＝整数a、bの最大公約数をcとすると、ax＋by＝cを満たす整数　x、yが存在する)を知らないと、解くのは難しい。

120と45の最大公約数は　15　だから整数解を持つなら、kを非負の整数とすると、120x＋45y＝15k　と表せる。
xとyは同時に0にはならない非負の整数から　最小値は　(x、y)＝(0、1)の時に　45.　
よって、k＝1、2、3、‥‥‥として行くと良いから　15おきに　45以上の整数は　120x＋45y　の形で表せる。

ひょっっとしてケアレスミスしてるかな？　中学入試に落ちるか。。。。。。。ｗ

お礼

理工系の大学を二つでているのですが．．．すっかり忘れていました。ありがとうございました。

回答No.1

nag0720

落とすための入試だから習わないことでも問題になるのでしょう。

正確な証明ではないですが、a=4とb=7の場合で説明してみます。

まず、数を次のように並べておきます。

0,7,14,21,28,・・・・
1,8,15,22,29,・・・・
2,9,16,23,30,・・・・
3,10,17,24,31,・・・・
4,11,18,25,32,・・・・
5,12,19,26,33,・・・・
6,13,20,27,34,・・・・

0,4,8,12,16,20,24の数は4の倍数だから、当然ax+byで表せます。
そして、上の表の0,4,8,・・・,24の右側の数も、7の倍数を足しているだけなので、ax+byで表せます。
4と7は互いに素だから、0,4,8,・・・,24ですべての行に対応しており、
24以上の数は、ax+byで表せることが分かます。
ax+byで表せない数で一番大きいのは、24の左側の数で、24-7=17です。
a,bを使って表すと、a(b-1)-b=ab-a-b　となります。

お礼

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