問題14　（tomhさん）
問題編

a、b、m、nは自然数とします。
　(1) 1<a<bとする.
　(2) どんなmとnを選んでも、ma+nbは2002にはならない.
　(3) 適当なmとnを選べば、2003以上の自然数はma+nbの形に表せる.
という条件を満たすものとします。
さて、これらの条件を満たす(a,b)の組をすべて見つけてください。

解答編

ほげ　の解答

�T
まずa,bは互いに素でなくてはなりません。
もし　a,bが共にＧで割り切れるとするとma+nbはGの倍数となりますから
2003以上の自然数がma+nbの形に表せることに矛盾します。
よって、a,bは互いに素です。

�U
abができないことの証明
　ab=ma+nbとなるとき　(b-m)a=nbとなりますが　a,bは互いに素ですから
b-mはbの倍数になります。ところが　明らかに0<m<bなので
0<b-m<bとなり、そのような数字は存在しません。
よってabはできません

�V
ab+1以上がすべてできることの証明
�@
　b,2b,3b,…(a-1)bをaで割ったあまりが1〜a-1のいずれかで　全て異なるという証明　を考えます。
bはaと互いに素であり1,2,3…a-1はaで割り切れないので　この中に0はありません。
また　この中に同じあまりとなるものはありません。
というのは　kbとlb　(0<k<l<a-1)をaで割ったあまりが等しいときは、
kb-lb=(k-l)bをaで割ると割り切れることになり、aとbが互いに素であることからk-lがaで割り切れ
0<k-l<aとなり　矛盾が生じるからです。
これらa-1個の数のあまりが全て異なり、それは0以外であるから　
　b,2b,3b,…(a-1)bをaで割ったあまりは1からa-1のどれかになっています。
�A
ma+nbでab+1以上の数字を作る方法
ab+1以上の数字Xを作るには…まずXをaでわります。
�A-1
そのあまりが0の時
X=yaとなりますが　yはbより大きいので　m=y-b　n=aとして
X=（y-b)a+ba=ma+nbとなります。
�A-2
あまりが0でないとき
あまりをrとしてb,2b,3b,…(a-1)bをaで割ったあまりがrになるものがあるので　
その数をkbとします。kb=la+r
このとき　X=ya+r=ya+(kb-la)=(y-l)a+kb　ここで　m=y-l　n=kとすると
明らかに　m,nは自然数ですから　条件に合うように作れたことになります。

�W
以上からabは絶対作れず　ab+1以上は必ず作ることができるので
ab=2002　かつ　1<a<b　かつ　a,bは互いに素である解を求めるとよいことになります。
2002=2×7×11×13から
(a,b)=(2,1001),(7,286),(11,182),(13,154),(14,143),(22,91),(26,77)
が答えです。


tomhさん　の解答

(3)より、aとbは互いに素です。もし、aとbが1よりも大きい公約数dを
もてば、ma+nbはdの倍数にしかならないので、(3)に反するからです。
結局、この問題は、
　互いに素なa、bに対して、ma+nbの形にならない最大の自然数は2002で　ある。
という条件から、a、bを捜し出すということです。

さて、ab=ma+nbという式が成り立つとしましょう。すると、
（aがbと公約数をもたないので）mはbの倍数でなければなりません。
よって、m≧bです。同じようにn≧aです。よって、ab=ma+nb≧2abとなって矛盾です。
このことから、abはma+nbの形に書けない数の一つになります。

次にN>abとして、a個の自然数 N-b, N-2b, …, N-abを考えます。
1≦i＜j≦aのとき、(N-ib)-(N-jb) = (j-i)bは、（j-i<aなので）aで
割り切れません。これは、N-ibとN-jbをaで割ったとき、それらの
余りが異なるということを意味しています。ですから、a個の自然数
N-b, N-2b, …, N-abをaで割ると、それらの余りはすべて異なります。

ところで、aで割ったときの余りというのは、0〜a-1のa個しかないので、
これらの余りとa個の自然数 N-b, N-2b, …, N-abとは1対1に対応します。
そこで余りが0になるものをもってきます。それをN-nbとしましょう。
nは、0≦n≦aを満たすある自然数です。このN-nbがaで割り切れる、
すなわち、aの倍数なので、自然数mを使って、maと書けるはずです。
よって、N-nb=ma. 書き直すとN=ma+nbとなって、N(>ab)は、必ず
ma+nbの形に書けることがわかりました。

　∴ abはma+nbの形に書けない最大の自然数である。

よって、今の問題では
　ab = 2002 = 2x7x11x13,　(a<b)
ですから、(a,b)の可能な組み合わせをすべて書き上げると、
　(2,1001), (7,286), (11,182), (13,154),
　(14,143), (22,91), (26,77)
の7組が答えになります。

感想等

一般に、互いに素な自然数a、bがあるとき、自然数m、nを使って
ma+nbの形に書けない最大の自然数はabとなります。
もし、mとnに0を許しても良いならば、ma+nbの形に書けない最大の
自然数はab-a-bです。
（後者は、"算数にチャレンジ!!"の第44問に使われています。この第44問は、
　[1] 吉川マサル, "子供にウケるソンケーされる!! 算数にチャレンジ!!"　　　(角川書店 2000)
にも収録されています。）


付加情報

解答で示したように、1<a<bなる二つの互いに素なる自然数が
与えられたとき、0<m, 0<nを満たすどんな整数m,nを選んでも、
ma+nbの形に書けない最大の整数はabです
（これを"命題A"と呼ぶことにします。）。

そして、解答の最後に少しだけ触れたように、mとnに0を許したときの
書けない最大の整数はab-a-bになります。

一般に、1<a, 1<bなる二つの互いに素なる自然数に対して、
M<m, N<n（M,Nも整数）を満たす二つの整数m,nをどのように選んでも、
ma+nbの形に書けない最大の整数はab+Ma+Nbとなります。
（これを"命題B"としておきましょう。「みっち物語」の問題は、
M=N=0の場合、0を許す場合は、M=N=-1のときです。）
この"命題B"を示しておきましょう。
（"命題A"は、解答で証明を与えましたので、既知とします。）

m'=m-M, n'=n-Nとすると、0<m', 0<n'となります。そして、

　ma+nb = (m'+M)a +(n'+N)b = (m'a+n'b) +(Ma+Nb)

です。この式の右辺の最初の括弧の中は、"命題A"と同じ形を
しているので、このm'a+n'bで書けない最大の整数はabです。
そして、最後の括弧の量が加わるので、結局、ma+nbで書けない最大の
整数は、ab+Ma+Nbです。■

さて、折角、"命題B"が得られたので、「みっち物語」と同じ状況に
適用してみましょう。違いはmとnの下限M,Nだけです。

解くべき式は、

　2002 = ab+Ma+Nb

です。この式の右辺を次のように変形します：

　2002 = (a+N)(b+M) -MN.

結局、

　2002+MN = (a+N)(b+M)　　　(1<a, 1<b)

を解くことになります。これは、「みっち物語」の問題を解いたときと
同じ状況になります。
但し、注意すべきことは、2002+MNを素因数分解して求めた数の組は
a+Nとb+Mですから、そこからa,bを出して、それらが公約数をもたない
ことを確認しなければならないことです。

では、試しに(M,N)=(+1,+2)の場合をやってみましょう：

　2004 = (a+2)(b+1).

2004=2x2x3x167なので、12個の組み合わせが可能です：

　(a+2,b+1) = (1,2004), (2,1002), (3,668), (4,501),
　　　　　　 (6,334), (12,167), (167,12), (334,6),
　　　　　　 (501,4), (668,3), (1002,2), (2004,1).

このうち、1<a,bで、aとbが互いに素になるのは、
(6,334)と(6,334)で、

　(a,b) = (4,333), (332,5)

となります。

この場合は解が、二つありましたが、(M,N)=(±1,±1)などは、
「解なし」になってしまうので、MとNの値によって、解の個数は
かなり変化しますね。