それでは，

［Ｑ］ａグラムとｂグラムのおもりがたくさんあるとき，どんな重さを計ることができるのだろうか？

［Ａ］ｄ＝ｇｃｄ（ａ，ｂ）とすると

［１］ａｘ＋ｂｙ＝ｄは整数解をもつ．

［２］ａｘ＋ｂｙ＝ｎが整数解をもつならな，ｎはｄの倍数である．

　すなわち，計れる重さの最小数が最大公約数であって，その倍数全体を計ることができるのである，ただし，おもりの選び方は１通りでないことに注意．たとえば，ａ＝２２，ｂ＝１５の場合，

　　６＝２２×（−１２）＋１５×１８＝２２×３＋１５×（−４）

　一般に１組の特殊解を（ｘ0，ｙ0）とすると，一般解は

　　ｘ＝ｘ0−ｂｔ／ｄ，ｙ＝ｙ0＋ａｔ／ｄ

で与えられる．もし，使用するおもりの数を最小にしたいならば，

　　｜ｘ｛＋｜ｙ｜＝｜ｘ0−ｂｔ／ｄ｜＋｜ｙ0＋ａｔ／ｄ｜

の最小値を求めればよい．

［Ｑ］ａグラムとｂグラムとｃグラムのおもりがたくさんあるとき，どんな重さを計ることができるのだろうか？

という問題では

［Ａ］ｄ＝ｇｃｄ（ａ，ｂ，ｃ）とすると

［１］ａｘ＋ｂｙ＋ｃｚ＝ｄは整数解をもつ．

［２］ａｘ＋ｂｙ＋ｃｚ＝ｎが整数解をもつならな，ｎはｄの倍数である．

すなわち，２種類のおもりの場合と同様の結果が成立する．

［Ｑ］ａ円玉とｂ円玉を用いてｎ円支払えるための条件を求めよ．

という問題では，

［Ａ］ｎはｄ＝ｇｃｄ（ａ，ｂ）の倍数，ｘ，ｙは非負整数．したがって，ｘ，ｙが存在するための条件は

　　ｘ＝ｘ0−ｂｔ／ｄ≧０，ｙ＝ｙ0＋ｃｔ／ｄ≧０

というｔに関する連立不等式を解けばよい．結局，区間

　　［−ｙ0ｄ／ａ，−ｘ0ｄ／ｂ］

が整数を含めばよいことになる．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】２元１次形式による表現とシルヴェスターの定理

　互いに素な２つの整数ａ1，ａ2が与えられたとき，非負整数が存在して

　　ｍ1ａ1＋ｍ2ａ2＝ｎ

が成り立つことは，硬貨の言葉に置き換えるとａ1円玉とａ2円玉を用いてｎ円が支払えることを意味する．どの額が支払えるか，支払えない最高額はいくらかという問題が考えられるところである（この問題はフロベニウスの硬貨交換問題と呼ばれる）．

　支払えない最高額をフロベニウス数と呼び，ｇ（ａ1，ａ2）で表される．

　　ｇ（ａ1，ａ2）＝ａ1ａ2−ａ1−ａ2＝（ａ1−１）（ａ2−１）−１

で与えられ，１と（ａ1−１）（ａ2−１）の間にある整数のちょうど半数が表現可能である．

　たとえば，ａ1＝４，ａ2＝７の場合，ｇ（ａ1，ａ2）＝１７で，表現不可能な整数の数は（ａ1−１）（ａ2−１）／２＝９となる．

　シルヴェスターの定理の証明は母関数

　　ｆ（ｚ）＝１／（１−ｚ^a1）（１−ｚ^a2）ｚ^n

の定数項と関連しているが，硬貨が３枚以上になると格段複雑になり，ｎ元１次形式に対する公式はほとんど成功しなかった．

　　［参］ベック，ロビンズ「離散体積計算による組合せ数学入門」シュプリンガー・ジャパン

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝