線形結合の問題　　 　　　　　　　　　　　　　 　　　　　　　　　　　

　３円と５円の２種類の切手のみで、８円以上のすべての郵便料金を払うことができるだろ

うか？




































（答）　払える！

　　　この問題は、平成２１年３月２１日付けで、当ＨＰがいつもお世話になっているＳ（Ｈ）さ
　　んにご紹介いただいたもの。素朴な問題に引かれました！

　数学的には、「８以上の自然数は、３と５の線形結合で表されるか」という問題である。

　証明は、易しい。　自然数 Ｎ に対して、

Ｎ＝８　ならば、　Ｎ＝３・１＋５・１＝８　で、　８は、３と５で表すことが出来る。

そこで、Ｎ≧９　とする。Ｎを３で割った商を Ｑ とし、余りを Ｒ とおくと、

　　　Ｎ＝３・Ｑ＋Ｒ　（ただし、Ｒ＝０、１、２）

と書ける。Ｎ≧９　なので、　Ｑ≧３　である。

　このとき、

　Ｒ＝０　ならば、　Ｎ＝３・Ｑ　で、Ｎは３のみで表される。

　Ｒ＝１　ならば、　３・（−３）＋５・２＝１　なので、

　　　　Ｎ＝３・Ｑ＋１＝３・Ｑ＋３・（−３）＋５・２＝３・（Ｑ−３）＋５・２

　　　Ｑ−３≧０　に注意して、　Ｎは、３と５で表すことが出来る。

　Ｒ＝２　ならば、　Ｎ＝３・Ｑ＋２＝３・Ｑ＋３・（−１）＋５・１＝３・（Ｑ−１）＋５・１

　　　Ｑ−１＞０　に注意して、　Ｎは、３と５で表すことが出来る。

　以上から、８以上のすべての自然数は、３と５の線形結合で表される。


　平成２１年３月２８日付けで、ＨＮ「あとねこ」さんより、次のように考えると視覚的に（？）分
かるかもという解答をお寄せいただいた。あとねこさんに感謝します。

　８＝３＋５　、　９＝３・３　、　１０＝５・２　、　１１＝３・２＋５　、　１２＝３・４

と、第１行の数はすべて、３と５の線形結合で表される。

　第２行以下の数については、第１行の数に５の倍数を加えることにより得られる。

したがって、８以上のすべての自然数は、３と５の線形結合で表される。

（コメント）　私の解答に比べて、視覚的に説得力がありますね！
　　　　　　この考え方は、成海璃子主演のＴＶドラマ「受験の神様」でも紹介された。

　この話題に関連して、平成２１年３月２９日付けで、Ｓ（Ｈ）さんは、

　３円、５円、８０円の３種類の切手のみで、２０００円の郵便料金を支払う方法は何通りあ
るか？

という問題を考えられた。この問題は、

　等式 ３ｘ＋５ｙ＋８０ｚ＝２０００　を満たす ０ 以上の整数 ｘ 、ｙ 、ｚ の組（ ｘ ，ｙ ，ｚ ）は何
組あるか？

ということに等しい。

　８０ｚ≦２０００　より、　ｚ≦２５　なので、　ｚ＝０、１、２、・・・、２４、２５　について調べれば
よい。

　ｚ＝２５　のとき、　３ｘ＋５ｙ＝０　より、　ｘ＝０　、ｙ＝０

　ｚ＝２４　のとき、　３ｘ＋５ｙ＝８０　で、　５ｙ≦８０　より、　ｙ≦１６

　　　このとき、（ ｘ ，ｙ ）＝（ ０ ，１６ ）、（ ５ ，１３ ）、（ １０ ，１０ ）、
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（ １５ ，７ ）、（ ２０ ，４ ）、（ ２５ ，１ ）

　　・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

等々、場合の数はたくさんありそうですね！

　さらに、Ｓ（Ｈ）さんは、次の問題も紹介された。

１．　５０円切手と８０円切手がそれぞれたくさん（無数に）ある。これらを使って支払うことが
　　出来ない郵便料金は何通りあるか？ただし、郵便料金は、１０の倍数とする。

（解）　１０円（×）、２０円（×）、３０円（×）、４０円（×）、５０円（○）、６０円（×）、７０円（×）、

　　　　８０円（○）、９０円（×）、１００円＝５０円*２（○）、１１０円（×）、１２０円（×）、

　　　１３０円＝５０円＋８０円（○）、１４０円（×）、１５０円＝５０円*３（○）、

　　　１６０円＝８０円*２（○）、１７０円（×）、１８０円＝５０円*２＋８０円（○）、１９０円（×）、

　　　２００円＝５０円*４（○）、２１０円＝５０円＋８０円*２（○）、２２０円（×）、

　　　２３０円＝５０円*３＋８０円（○）、２４０円＝８０円*３（○）、２５０円＝５０円*５（○）、

　　　２６０円＝５０円*２＋８０円*２（○）、２７０円（×）、２８０円＝５０円*４＋８０円（○）、

　　　２９０円＝５０円＋８０円*３（○）、３００円＝５０円*６（○）、

　　　３１０円＝５０円*３＋８０円*２（○）、３２０円＝８０円*４（○）、・・・・・

　以下、２８０円、２９０円、３００円、３１０円、３２０円 の支払いパターンに、５０円切手を何
枚かずつ追加することにより、２８０円以上のすべての金額が５０円と８０円の組合せにより
得られる。

　したがって、求める場合の数は、

　　１０円、２０円、３０円、４０円、６０円、７０円、９０円、１１０円、１２０円、１４０円、１７０円、
１９０円、２２０円、２７０円

の１４通りである。　　（終）


２．　１３円、１４円、１５円、１６円、１７円の３種類の切手のみで、すべての金額が支払える
　　のは何円以上の場合か？


（追記）　平成２２年６月５日付け

　上記では、

　３円、５円の２種類の切手のみで、８円以上の全ての郵便料金が払えること

　５円、８円の２種類の切手のみで、２８円以上の全ての郵便料金が払えること

が示された。

　この話題に関連して、当ＨＰがいつもお世話になっているＦＮさんが、問題の一般化を試み
られた。（平成２２年６月２日付け）

　ａ 、 ｂ を互いに素な自然数とする。すべての整数が整数 ｘ 、 ｙ を使って、 ａｘ＋ｂｙ の形
で表されることはよく知られている。ここで、 ｘ 、 ｙ を０以上としたとき、 ａｘ＋ｂｙ の形で表
される整数はどのような数であろうか。ある数以上はこの形で表すことができる。そのある
数を求めてください。

　すなわち、

　ａ 、 ｂ を互いに素な自然数とする。次の命題が成り立つ最小の自然数Ｎを求めよ。

「Ｎ以上の整数は０以上の整数 ｘ 、 ｙ を使って ａｘ＋ｂｙ の形で表すことができる。」

同じことであるが次の形に書いてもいいだろう。

　ａ 、 ｂ を互いに素な自然数とする。０以上の整数 ｘ 、 ｙ を使って ａｘ＋ｂｙ の形で
表すことができない最大の整数を求めよ。

　ＦＮさんが、ａ＝５、ｂ＝７　の場合の解答を寄せられた。（平成２２年６月４日付け）

　０以上の整数 ｘ 、 ｙ を使って、５ｘ＋７ｙ の形で表される数の集合をＡとする。

１から順に自然数を５個毎に行を変えながら書いていく。（Ａに入らないものは黒字）

　　　５本の列は、５で割った余りが、１、２、３、４、０ であ
　　る自然数を小さいものから順に並べたものである。

　　　右端の列、即ち、５で割り切れる数はすべてＡに入っ
　　ている。それ以外の列は、どこかで７の倍数が現れ、
　　それ以後はすべてＡに入る。

　　　右端以外の各列で最初に現れる７の倍数のうち最も
　　遅く現れるのは、２８である。

　従って、Ａに入っていない最大の数は、２８の現れる列で、２８の上にある２３である。

即ち、２４以上の整数はすべてＡに属する。

　これと同じことを、一般の場合もやればいいのだが、具体的な場合と違い意外と書きにく
い。

　ＧＡＩ さんが、

　ａ 、 ｂ を互いに素な自然数とする。０以上の整数 ｘ 、 ｙ を使って ａｘ＋ｂｙ の形で
表すことができない最大の整数を求めよ。

という問題について、次のような表を作られた。（平成２２年６月６日付け）

　さらに、ＦＮさんは、

　ａ 、 ｂ を互いに素な自然数とする。０以上の整数 ｘ 、 ｙ を使って ａｘ＋ｂｙ の形で
表すことができない最大の自然数は、 ａｂ−ａ−ｂ である

ことを次のように証明された。（平成２２年６月７日付け）

（証明）　ａｂ−ａ−ｂ　が、ａｘ＋ｂｙ　（ ｘ 、ｙ は０以上の整数）の形には書けないことを、まず
　　　　示す。

　　　ａｂ−ａ−ｂ＝ａｘ＋ｂｙ　（ ｘ 、ｙ は０以上の整数）の形に書けるとする。

　　　ａ（ｂ−１−ｘ）＝ｂ（ｙ＋１）　で、ａ 、ｂ は互いに素より、ｙ＋１ は ａ の倍数となる。

　　　ｙ＋１≧１　より、　ｙ＋１≧ａ　なので、　ｂ（ｙ＋１）≧ａｂ

　　　一方、　ａ（ｂ−１−ｘ）＜ａｂ　なので、これは矛盾である。

　　　　よって、ａｂ−ａ−ｂ　は、ａｘ＋ｂｙ　（ ｘ 、ｙ は０以上の整数）の形には書けない。

　　次に、ａｂ−ａ−ｂ＋１　以上の整数はすべて、ａｘ＋ｂｙ　（ ｘ 、ｙ は０以上の整数）の形に
　書けることを示す。

　　整数 ｎ が、　ｎ≧ａｂ−ａ−ｂ＋１＝（ａ−１）（ｂ−１）　を満たすとする。

　ｎ　、　ｎ−ｂ　、　ｎ−２ｂ　、　・・・　、　ｎ−（ａ−１）ｂ　を ａ で割った余りを考える。

　これらは、ａ 個あるので、次の（１）（２）のどちらかが成り立つ。

　　（１）　これらの中に同じものがある。

　　（２）　これらの中に０がある。

　（１）のとき、異なる ｓ、ｔ （０≦ｓ＜ｔ≦ａ−１）が存在して、ｎ−ｓｂ−（ｎ−ｔｂ）＝（ｔ−ｓ）ｂ　が

ａ で割り切れる。ｂ と ａ は互いに素であるから、ｔ−ｓ が ａ で割り切れる。

　しかるに、０＜ｔ−ｓ≦ａ−１ より、それは不可能である。

　（２）のとき、ｎ−ｓｂ を ａ で割った余りが ０ であるとする。このとき、ｎ−ｓｂ＝ｔａ　と書ける。

ｎ＝ｓｂ＋ｔａ　において、ｓ≧０　、ｔ≧０　である。

　実際に、ｎ−ｓｂ≧ｎ−（ａ−１）ｂ≧ａｂ−ａ−ｂ＋１−ａｂ＋ｂ＝−ａ＋１　より、ｎ−ｓｂ＋ａ≧１

で、ｎ−ｓｂ＝ｔａ　から、　（ｔ＋１）ａ≧１　より、　ｔ＋１≧１　なので、　ｔ≧０　と言える。

　以上から、求める最大の自然数が、ａｂ−ａ−ｂ　であることが示された。　（終）

（コメント）　ＦＮさんによれば、「ａｂ−ａ−ｂ」が自然に出る構成的・発見的な証明ではないで
　　　　　すが．．．とのことですが、数学らしい立派な証明ですね！

　また、上記の問題と同趣旨の問題が、昭和６２年度　防衛大学校の記述式問題として出題
されている。世間的には、難問と認識されているようである。

　ａ、ｂ を負でない整数とし、３ａ＋７ｂ の形で表せる自然数全体を Ｓ とする。たとえば、

４７＝３×４＋７×５　ゆえ　４７はＳの要素である。このとき、次の問に答えよ。

（１）　１０以下の自然数でＳの要素であるものをすべて求めよ。

（２）　ｎ がＳの要素であるとき、ｎ＋３ もＳの要素であることを示せ。

（３）　連続する３個の自然数　ｍ 、ｍ＋１ 、ｍ＋２　がいずれもＳの要素となるような自然

　　数 ｍ のうち最小のものを求めよ。

（４）　（３）で求めた ｍ 以上の任意の自然数 ｎ は、Ｓの要素であることを証明せよ。

（解）（１）　１≦３ａ＋７ｂ≦１０　において、ａ≧０、ｂ≧０　に注意して、

　　　　　　　（ ａ ， ｂ ）＝（ ０ ， １ ）、（ １ ， ０ ）、（ １ ， １ ）、（ ２ ， ０ ）、（ ３ ， ０ ）

　　　　　　が条件を満たす。よって、求める要素は、　３、６、７、９、１０

（２）　題意より、　負でない整数 ａ、ｂ を用いて、　ｎ＝３ａ＋７ｂ　と書ける。

　　　このとき、　ｎ＋３＝３（ａ＋１）＋７ｂ　において、ａ＋１、ｂ は負でない整数なので、

　　　ｎ＋３ は、Ｓ の要素である。

（３）　１１は、Ｓ の要素でない。実際に、１１が、Ｓ の要素であると仮定すると、負でない整

　　　数 ａ、ｂ を用いて、　１１＝３ａ＋７ｂ　と書ける。

　　　　ここで、ａ＝０　とすると、１１が７で割り切れることになるので、ａ≧１

　　　このとき、　８＝３（ａ−１）＋７ｂ　において、ａ−１、ｂ は負でない整数なので、８ は、Ｓ

　　　の要素となる。しかるに、これは（１）の結果に矛盾する。

　　　　よって、１１は、Ｓ の要素でない。

　　　（１）より、９、１０ はＳの要素なので、（２）より、１２、１３もＳの要素である。

　　　また、１４＝３・０＋７・２　と書けるので、１４もＳの要素である。

　　　　以上から、連続する３個の自然数　ｍ 、ｍ＋１ 、ｍ＋２　がいずれもＳの要素となる

　　　ような自然数 ｍ のうち最小のものは、１２である。

（４）　（３）の結果より、１２、１３、１４ は、Ｓの要素である。１２以上の任意の自然数 ｎ を３

　　　で割った余りで分類する。

　　　　　ｎ＝３・ｐ＋１２　（ｐは負でない整数）　のとき、（２）の結果と、１２がＳの要素である

　　　　ことから、ｎ はＳの要素であることが分かる。

　　　　　ｎ＝３・ｐ＋１３　（ｐは負でない整数）　のとき、（２）の結果と、１３がＳの要素である

　　　　ことから、ｎ はＳの要素であることが分かる。

　　　　　ｎ＝３・ｐ＋１４　（ｐは負でない整数）　のとき、（２）の結果と、１４がＳの要素である

　　　　ことから、ｎ はＳの要素であることが分かる。

　　以上から、１２以上の任意の自然数 ｎ に対して、Ｓの要素であることが示された。（終）

（コメント）　（４）の証明は厳密には数学的帰納法で示す必要があるかもしれない。


　あとねこさんがＦＮさんの証明の別証を考えられた。（平成２２年１１月９日付け）

　ａ、ｂ を互いに素な自然数とする。0以上の整数 ｘ、ｙ を使って ａｘ＋ｂｙの形で表す
ことができない最大の自然数は ａｂ−ａ−ｂ である。

（証明）　ｂ＞ａ として考える。0以上の整数 ｘ、ｙ を使って、ａｘ＋ｂｙ の形で表される数の集合

　をＡとする。１から順に ｂ 個毎に行を変えながら ａｂ まで書く。

　　1　　 2　　3　 …　　b
　 b+1　 … 　… 　… 　2b
　 ・　　　　　　　　　 ・
　 ・　　　　　　　　　 ・
　 ・　　　　　　　　　 ・
(a-1)b+1 … 　… 　… 　ab

a の倍数に着目したとき、a の倍数は各列1つしか現れない。

　実際に、　ｔｂ≡ｆ　 (ｍｏｄ　ａ)　のとき、t(ａ＋ｎ)ｂ≡f　 (ｍｏｄ　ａ)　が成り立つ ｎ は
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（ ｔ と ｎ は整数）
　　　　t(ａ＋ｎ)ｂ≡(ａ＋ｎ)ｆ≡ｎｆ    (ｍｏｄ　ａ)

であるから、ｎ＝ｋａ＋１　 （ｋは整数）である。

すなわち、 ｂ、２ｂ、３ｂ、・・・ａｂ は a で割った余りがそれぞれ違うことを意味する。

　ここで、ある列に ａ の倍数が２つあるとすると、ｉｂ と ｊｂ を ａ で割った余りが一致するとい

うことになる。（ ｉ 、 ｊ は自然数で、 ｉ≠ｊ 、 ｉ≦ａ 、 ｊ≦ａ）

　しかるに、これは矛盾。同列に、 ａ の倍数が３つ以上であっても同様に矛盾する。

　したがって、 ａ の倍数は各列１つしか現れない。

　右端の列、即ち、ｂ で割り切れる数はすべてＡに入っている。それ以外の列は、どこかで

ａ の倍数が現れ、それ以後はすべてＡに入る。

ａ の倍数は各列1つしか現れないので、最後にＡに含まれる列は、ａ(ｂ−１) が含まれる列

なので、表すことの出来ない最大の数は、その１行前の数字 ａ(ｂ−１)−ｂ＝ａｂ−ａ−ｂ　と

なる。（証終）


（コメント）　あとねこさん、別証ありがとうございます。あとねこさんの証明を参考にして私流
　　　　　　に書き直してみました。

（証明）　ｂ＞ａ として考える。0以上の整数 ｘ、ｙ を使って、ａｘ＋ｂｙ の形で表される数の集合

　をＡとする。１から順に ｂ 個毎に行を変えながら ａｂ まで書く。

　　1　　 2　　3　 …　　b
　 b+1　 … 　… 　… 　2b
　 ・　　　　　　　　　 ・
　 ・　　　　　　　　　 ・
　 ・　　　　　　　　　 ・
(a-1)b+1 … 　… 　… 　ab

a の倍数に着目したとき、a の倍数は各列1つしか現れない。

　実際に、任意の列　ｋ、ｂ＋ｋ、２ｂ＋ｋ、・・・、（ａ−１）ｂ＋ｋ　（ｋは自然数で、１≦ｋ≦ｂ）に

おいて、ある自然数 ｍ、ｎ （１≦ｍ＜ｎ≦ａ）が存在して、　ｍｂ＋ｋ≡ｎｂ＋ｋ　（ｍｏｄ　ａ）　が

成り立つと仮定すると、

　　（ｍ−ｎ）ｂ≡０　（ｍｏｄ　ａ）　で、（ａ，ｂ）＝１　より、　ｍ−ｎ≡０　　（ｍｏｄ　ａ）　となる。

　しかるに、これは、　１≦ｍ＜ｎ≦ａ　に矛盾する。

　したがって、ａ個の任意の列　ｋ、ｂ＋ｋ、２ｂ＋ｋ、・・・、（ａ−１）ｂ＋ｋ　の各項を ａ で割った

余りは全て異なる。このとき、この列の項で、ａ で割り切れるものがただ一つ存在する。

　右端の列、即ち、ｂ で割り切れる数はすべてＡに入っている。それ以外の列は、どこかで

ａ の倍数が現れ、それ以後はすべてＡに入る。

ａ の倍数は各列1つしか現れないので、最後にＡに含まれる列は、ａ(ｂ−１) が含まれる列

なので、表すことの出来ない最大の数は、その１行前の数字 ａ(ｂ−１)−ｂ＝ａｂ−ａ−ｂ　と

なる。（証終）


　当ＨＰがいつもお世話になっているＨＮ「ＦＮ」さんが、この話題に関連して、次の問題を提
起された。（平成２２年１１月１０日付け）

　ａ、ｂ を互いに素な自然数とする。０以上の整数 ｘ、ｙ を使って ａｘ＋ｂｙの形で表す
ことができない自然数の個数を求めよ。

　この問題は、上記のＳ（Ｈ）さんの問題の一般化である。


　Ｓ（Ｈ）さんの問題を単純化して、

　５円切手と８円切手がそれぞれたくさん（無数に）ある。これらを使って支払うことが
出来ない郵便料金は何通りあるか？

　この問題を、あとねこさんやＦＮさんの解答に照らして考えると次のように解けるだろう。


　０以上の整数 ｘ 、 ｙ を使って、５ｘ＋８ｙ の形で表される数の集合をＡとする。

　１から順に自然数を５個毎に行を変えながら書いていく。（Ａに入らないものは黒字）

　５本の列は、５で割った余りが、１、２、３、４、０ である自然数を小さいものから順に並べ
たものである。

　　　右端の列、即ち、５で割り切れる数はすべてＡに入っ
　　ている。それ以外の列は、どこかで８の倍数が現れ、
　　それ以後はすべてＡに入る。

　　　右端以外の各列で最初に現れる８の倍数のうち最も
　　遅く現れるのは、３２である。

　　　従って、Ａに入っていない最大の数は、３２の現れる
　　列で、３２の上にある２７である。

　　　即ち、２８以上の整数はすべてＡに属する。


　各列には８の倍数がただ1つ存在し、しかも全て異なる。

　よって、８、２・８、３・８、４・８　の各項を５で割った商の総和を求めればよい。

　「８」のある列の項で、５ｘ＋８ｙ の形で表されない項の数は、

　　　　８÷５＝１　・・・　３

より、１個である。同様にして、「１６」、「２４」、「３２」　のある項で、５ｘ＋８ｙ の形で表されな
い項の数は、

　　　　２・８÷５＝３　・・・　１　、　３・８÷５＝４　・・・　４　、　４・８÷５＝６　・・・　２

より、３個、４個、６個あるので、求める場合の数は、

　　　１＋３＋４＋６＝１４　（個）

となる。これは、次のように計算してもよい。［ｘ］ をガウス記号として、

　　［８/５］＋［２・８/５］＋［３・８/５］＋［４・８/５］＝１＋３＋４＋６＝１４　（個）

　このことから、

　ａ、ｂ を互いに素な自然数とする。０以上の整数 ｘ、ｙ を使って ａｘ＋ｂｙの形で表す
ことができない自然数の個数を求めよ。

の解は、

　　［ａ/ｂ］＋［２・ａ/ｂ］＋［３・ａ/ｂ］＋・・・＋［（ｂ−１）・ａ/ｂ］

と書けることが分かる。

（コメント）　上式をもっと簡潔に表すことはできないだろうか．．．？


　ＦＮさんより、「ａ で割った余りが ｒ である列と、ａ−ｒ である列をペアにして考えては．．．」
とアドバイスをいただきました。（平成２２年１１月１３日付け）

　ＦＮさんからいただいたヒントをもとに、再度考えてみました。

（解）　ａ、２ａ、３ａ、・・・、（ｂ−１）ａ　の各数を ｂ で割った余りは、１、２、３、・・・、ｂ−１ の何

　　れかで、互いに１対１に対応する。このとき、求める場合の数は、

　　［｛ａ＋２ａ＋３ａ＋・・・＋（ｂ−１）ａ｝−｛１＋２＋３＋・・・＋（ｂ−１）｝］/ｂ

　＝（ａ−１）｛１＋２＋３＋・・・＋（ｂ−１）｝/ｂ

　＝（ａ−１）（ｂ−１）/２

で与えられる。

　したがって、ａｘ＋ｂｙ の形で表すことができない自然数の個数は、

　　　　　　　

である。　（終）

（コメント）　解が綺麗に求まりましたね！ＦＮさんに感謝します。あとねこさんにも、解が正し
　　　　　　いことを追認していただきました。（平成２２年１１月１４日付け）


　ＦＮさんより、証明をいただきました。（平成２２年１１月１４日付け）

（証明）　ａｘ＋ｂｙ の形で表される数の集合をＡとする。0＜ｒ＜ｂ として、ｂ で割って ｒ 余る数

　　ｒ　、　ｂ＋ｒ　、　２ｂ＋ｒ　、　・・・　、　（ａ−１）ｂ＋ｒ

を考える。この中に、ａ の倍数になるものがただ1つある。それを、　ｋｂ＋ｒ　とする。

　このとき、この中でＡに属さないものは、ｒ から (ｋ−１)ｂ＋ｒ　までのｋ 個ある。

　同様に、ｂ で割って、ｂ−ｒ 余る数

　　ｂ−ｒ　、　ｂ＋ｂ−ｒ＝２ｂ−ｒ　、　３ｂ−ｒ　、　・・・　、　ａｂ−ｒ

の中に、ａ の倍数になるものがただ1つある。それを、ｌｂ−ｒ　とする。

　このとき、この中でＡに属さないものは、ｂ−ｒ から (ｌ−１)ｂ−ｒ までのｌ−１ 個ある。

　ｋｂ＋ｒ≡０　（ｍｏｄ　ａ）　、ｌｂ−ｒ≡０　（ｍｏｄ　ａ）　より、　(ｋ＋ｌ)ｂ≡０　（ｍｏｄ　ａ）

　ａ と ｂ は互いに素であるから、　ｋ＋ｌ≡０　（ｍｏｄ　ａ）

　ここで、　０≦ｋ≦ａ−１　、　１≦ｌ≦ａ　より、　１≦ｋ＋ｌ≦２ａ−１　なので、

　　　ｋ＋ｌ＝ａ　すなわち、　ｋ＋ｌ−１＝ａ−１

　ｂ で割って余りが ｒ、ａ−ｒ であるもののうちで、Ａに属さないものが

　　　ｋ＋ｌ−１＝ａ−１（個）

ある。 ａ と ｂ は互いに素なので、少なくとも一方は奇数である。そこで、ｂ を奇数に取ってお

くと、余りが １ と ｂ−１で ａ−１個、２ と ａ−２で ａ−１個、・・・ となり、全部で、

　　　　　（ａ−１）（ｂ−１）/２　個

である。　(証終）

（コメント）　各列毎の項数がきちんと求められるんですね！求める自信がなかったので、上
　　　　　　記のようなアバウトな証明にしてしまいました。ＦＮさんの精緻な証明に感動しまし
　　　　　　た。


　ＦＮさんに、今までのことをまとめていただきました。

　次の２つが証明できたことになる。

(１A) 　ａ、ｂ を互いに素な自然数とする。０以上の整数 ｘ、ｙ を使って、ａｘ＋ｂｙの形

　　　で表せない最大の整数は、ａｂ−ａ−ｂ＝（ａ−１）（ｂ−１）−１ である。

　従って　(ａ−１)(ｂ−１)以上の整数は、すべて ａｘ＋ｂｙ　(ｘ，ｙ は０以上の整数)の形に表す
ことができる。

(２A) 　ａ、ｂ を互いに素な自然数とする。０以上の整数 ｘ、ｙ を使って、ａｘ＋ｂｙの形

　　　で表せない自然数は、（ａ−１）（ｂ−１）/２個ある。

　ｘ、ｙ は０以上の整数ですが、これを、ｘ、ｙ が自然数に変えたのもやっておきましょう。

　(1A)(2A)からすぐ出ますが(1A)(2A)を使わないで証明するのも面白いです。

(１Ｂ) 　ａ、ｂ を互いに素な自然数とする。自然数 ｘ、ｙ を使って、ａｘ＋ｂｙ の形で表せ

　　　ない最大の整数は、「？」である。

(２Ｂ) 　ａ、ｂ を互いに素な自然数とする。自然数 ｘ、ｙ を使って、ａｘ＋ｂｙ の形で表せ

　　　ない自然数は、「？」個ある。


２つの場合が済めば３つの場合を考えたくなります。

　自然数 ａ、ｂ、ｃ の最大公約数は１であるとする。

０以上の整数 ｘ 、 ｙ 、ｚ を使って、ａｘ＋ｂｙ＋ｃｚ　の形で表せない最大の整数を求め

よ。

　これは大変難しそうで、２個の場合のような簡単な式で表すことは、とてもできそうにありま
せん。 ａ、ｂ、ｃ にもっと強い制限をつけてもいいですから、なんらかの結果はでないでしょう
か。とりあえず具体的な数で調べてみましたが何もわかりません。


　攻略法さんが、ＦＮさんの問いかけに答えられた。（平成２２年１１月１６日付け）

　（１Ｂ）（２Ｂ）の「？」は次の通りである。

　　　(１Ｂ)　ａｂ

　　　(２Ｂ)　（ａ＋１）（ｂ＋１）/２−１＝（aｂ＋ａ＋ｂ−１）/２

　　　　　（２Ａ）より、ａｂ 以下の自然数のうちで、ａｘ＋ｂｙ　（ｘ、ｙ は、０以上の整数）で表せな

　　　　い数は、(ａ−１)(ｂ−１)/２個ある。

　　　　　さらに、ｙ＝０　のとき、ａ の倍数 ａ、２ａ、・・・、ａ（ｂ−１）、ａｂ　は、ｂ 個

　　　　　　　　　ｘ＝０　のとき、ｂ の倍数 ｂ、２ｂ、・・・、ｂ（ａ−１）、ａｂ　は、ａ 個

　　　　で、ａｂが、１個重複している。

　　　　　よって、　（ａ−１）（ｂ−１）/２＋ｂ＋ａ−１＝（ａｂ−ａ−ｂ＋１＋２ｂ＋２ａ−２）/２

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　＝（ａｂ＋ａ＋ｂ−１）/２

　自然数 ａ、ｂ、ｃ の最大公約数は１であるとする。

０以上の整数 ｘ 、 ｙ 、ｚ を使って、ａｘ＋ｂｙ＋ｃｚ　の形で表せない最大の整数を求め

よ。

については、

　ａ、ｂ が互いに素で、ｃ＝ｍａ＋ｎｂ　（ｍ、ｎ を０以上の整数）と表される場合、ａｂ−（ａ＋ｂ）


　上記で得られた公式を用いると、次の問題も容易だろう。

東洋大学　工学部（１９９２）

　ｍ、ｎ が負でない整数のとき、９ｍ＋１０ｎ で表せない正の整数の個数を求めよ。
また、その中の最大整数を求めよ。

（解）　９ｍ＋１０ｎ で表せない正の整数の個数は、

　　　　　（９−１）（１０−１）/２＝３６（個）

　　　　９ｍ＋１０ｎ で表せない正の整数のうち、最大な整数は、

　　　　　（９−１）（１０−１）−１＝７１　　（終）


　冒頭の問題は、第10回　日本数学オリンピック予選問題（平成１２年）で、

　３ａ＋５ｂ (ただし, a, b は 0 以上の整数) の形で表わせない自然数の最大値を求
　めよ。

として出題されている。


（追記）　令和２年７月３０日付け

問題　４と７の足し算だけで表せない整数が存在する。例えば、

　　　１、２、３、５、６、・・・　など。

　実は、このような数には、最大値が存在する。それは何か？

　この問いかけを数学的に定式化すると、

　０以上の整数ｘ、ｙに対して、　４ｘ＋７ｙ　の形で書けない最大の整数を求めよ。

答えは、１７　である。



　　　以下、工事中