Frobeniusの硬貨問題

同義語：硬貨の問題Frobenius coin problemcoin problem

概要

前提知識: 整数の割り算と互除法, 不定方程式の解法, 合同式の計算規則

高校での出発点：3 円玉と 5 円玉で払える金額

3 円玉と 5 円玉だけがたくさんある国を考える。お釣りはもらえないとすると、ちょうど払える金額と、どうしても払えない金額がある。小さい金額から順に調べてみる。

3 円玉と 5 円玉

3 円玉を $x$ 枚、5 円玉を $y$ 枚使うと、金額は $3x+5y$ 円である（$x$、$y$ は $0$ 以上の整数）。$0$ 円から $15$ 円までを調べる。
(1) $5$ 円玉を使わない（$y=0$）と、払えるのは $3$ の倍数 $0,3,6,9,12,15$ である。
(2) $5$ 円玉を 1 枚使う（$y=1$）と、$5,8,11,14$ が払える。
(3) $5$ 円玉を 2 枚使う（$y=2$）と、$10,13$ が払える。$5$ 円玉を 3 枚使う（$y=3$）と $15$ で、これは (1) にも出ている。
(1)〜(3) に出てこない $1,2,4,7$ の 4 つが払えない金額である。$8,9,10$ が続けて払えるので、それぞれに 3 円玉を 1 枚ずつ足していけば $11,12,13$、さらに $14,15,16$、… と、$8$ 円以上はすべて払える。したがって、払えない金額の最大は $7$ 円で、払えない金額は全部で 4 つである。

0 から 15 までの数のうち、3x+5y の形で表せる数（青）と表せない数（赤）。弧は n と 7−n を結び、どの弧も青と赤を 1 つずつ結ぶ

4 円玉と 6 円玉

4 円玉と 6 円玉では、金額 $4x+6y=2(2x+3y)$ はいつも偶数である。したがって $1,3,5,7,\ldots$ の奇数の金額は、いくら大きくても払えない。払えない金額には最大のものがない。
偶数の金額 $2m$ は、$2x+3y=m$ が $0$ 以上の整数解をもつときに払える。$m\ge2$ なら、$m$ が偶数のときは $(x,y)=\left(\dfrac m2,0\right)$、奇数のときは $(x,y)=\left(\dfrac{m-3}2,1\right)$ が解である。$m=1$ だけは $2x+3y=1$ の $0$ 以上の解がない。よって払えない偶数の金額は $2$ だけである。

ex-fcp-start2 のように、2 つの金額が $1$ より大きい公約数をもつと、その公約数の倍数でない金額はすべて払えない。そこでこの記事では、2 つの数が互いに素な場合を考える。答える問いは次の 3 つである。

払えない金額の最大はいくつか。→ thm-fcp-max
払えない金額はいくつあるか。→ thm-fcp-count

図 1 の弧に見える対称性は、いつも成り立つか。→ thm-fcp-count

高校の計算	この記事の言葉	大学の言葉
1 次不定方程式 $ax+by=n$ の整数解	標準形 $0\le x\le b-1$	剰余類の代表
$0$ 以上の整数解があるか	表せる数・表せない数	数の半群
$ab-a-b$	表せない最大の数	半群の Frobenius 数
$n$ と $ab-a-b-n$	表せる／表せないの対称性	対称な半群

言葉の準備：表せる数と標準形

以下、$a$、$b$ は正の整数とする。

$a$ と $b$ で表せる数

整数 $n$ が、$0$ 以上の整数 $x$、$y$ を使って
$$ n=ax+by $$
と書けるとき、$n$ は $a$ と $b$ で表せる という。そう書けないとき、$n$ は $a$ と $b$ で表せない という。

$0=a\cdot0+b\cdot0$ はいつも表せる。負の整数は、$ax+by\ge0$ なので表せない。この記事の関心は、$0$ 以上の整数のうちどれが表せないかである。

表し方は 1 通りとは限らない

$a=3$、$b=5$ とする。
(1) $22=3\cdot4+5\cdot2$ なので、$22$ は表せる。$22=3x+5y$ となる $0$ 以上の組 $(x,y)$ をすべて探す。$5y\le22$ より $y=0,1,2,3,4$ で、$22-5y=22,17,12,7,2$ のうち $3$ で割り切れるのは $12$ だけなので、組は $(4,2)$ だけである。
(2) $30=3\cdot10=3\cdot5+5\cdot3=5\cdot6$ なので、$30$ の表し方は $(x,y)=(10,0),(5,3),(0,6)$ の 3 通りある。
(3) $7$ は表せない（ex-fcp-start）。しかし $y$ を負にしてよければ $7=3\cdot4+5\cdot(-1)$ と書ける。

ex-fcp-def の (3) のように、$x$、$y$ に負の整数を許すと、$\gcd(a,b)=1$ のときはすべての整数が $ax+by$ の形に書ける（整数の割り算と互除法の定理「整数の Bézout の等式」を $n$ 倍すればよい）。その整数解のうち、$0$ 以上の組があるかどうかが問題である。そこで、整数解の中から 1 つを「標準形」として選ぶ。

標準形

$a$、$b$ を互いに素な正の整数とする。どの整数 $n$ も
$$ n=ax+by,\qquad 0\le x\le b-1,\quad y\text{ は整数} $$
の形に、ただ 1 通りに書ける。この書き方を $n$ の 標準形 という。

$ax$ を $b$ で割った余りを調べる

方針：$x=0,1,\ldots,b-1$ に対する $ax$ を $b$ で割った余りが、すべて異なることを示す。すると余りは $0,1,\ldots,b-1$ のどれも 1 回ずつ現れるので、$n$ と同じ余りをもつ $ax$ がちょうど 1 つ選べる。
段 1（余りはすべて異なる）。$0\le x< x'\le b-1$ で、$ax$ と $ax'$ を $b$ で割った余りが等しいとする。すると $ax'-ax=a(x'-x)$ は $b$ の倍数である。$a$ と $b$ は互いに素なので、互いに素な数で割り切る性質（整数の割り算と互除法の系「互いに素な数による割り算」）から、$b$ は $x'-x$ を割り切る。ところが $0< x'-x\le b-1$ なので、$x'-x$ は $b$ の倍数ではない。これは矛盾である。よって $b$ 個の数 $a\cdot0,a\cdot1,\ldots,a(b-1)$ を $b$ で割った余りはすべて異なる。
段 2（存在）。$b$ で割った余りは $0,1,\ldots,b-1$ の $b$ 種類しかなく、段 1 より $b$ 個の数 $ax$ の余りはすべて異なるので、どの余りもちょうど 1 回ずつ現れる。$n$ を $b$ で割った余りを $r$ とし、$ax$ を $b$ で割った余りが $r$ になる $x$（$0\le x\le b-1$）をとる。$n-ax$ は余りが等しい 2 数の差なので $b$ の倍数で、$y=\dfrac{n-ax}b$ は整数である。このとき $n=ax+by$ となる。
段 3（一意性）。$n=ax+by=ax'+by'$（$0\le x,x'\le b-1$）とすると、$ax\equiv n\equiv ax'\pmod b$ なので、$ax$ と $ax'$ を $b$ で割った余りは等しい。段 1 より $x=x'$ で、$by=by'$ から $y=y'$ である。

$a=3$、$b=5$ の標準形

$x=0,1,2,3,4$ に対して $3x=0,3,6,9,12$ を $5$ で割った余りは $0,3,1,4,2$ で、すべて異なる。
(1) $n=8$：$8$ を $5$ で割った余りは $3$ で、余りが $3$ になるのは $x=1$（$3x=3$）である。$y=\dfrac{8-3}5=1$ なので、標準形は $8=3\cdot1+5\cdot1$ である。
(2) $n=7$：$7$ を $5$ で割った余りは $2$ で、余りが $2$ になるのは $x=4$（$3x=12$）である。$y=\dfrac{7-12}5=-1$ なので、標準形は $7=3\cdot4+5\cdot(-1)$ である。
(3) $n=-1$：$-1=5\cdot(-1)+4$ なので $5$ で割った余りは $4$ で、余りが $4$ になるのは $x=3$（$3x=9$）である。$y=\dfrac{-1-9}5=-2$ なので、標準形は $-1=3\cdot3+5\cdot(-2)$ である。

標準形の $y$ の符号を見れば、表せるかどうかが分かる。

表せるための条件

$a$、$b$ を互いに素な正の整数とし、整数 $n$ の標準形を $n=ax+by$（$0\le x\le b-1$）とする。$n$ が $a$ と $b$ で表せるのは $y\ge0$ のときで、そのときに限る。

使う $a$ の個数を $b$ 個ずつまとめる

$y\ge0$ なら、標準形そのものが $0$ 以上の $x$、$y$ による表し方である。
逆に $n$ が表せるとし、$n=ax'+by'$（$x'\ge0$、$y'\ge0$）とする。$x'$ を $b$ で割って $x'=bq+x''$（$q\ge0$、$0\le x''\le b-1$）と書くと
$$ n=a(bq+x'')+by'=ax''+b(aq+y') $$
である。$0\le x''\le b-1$ なので、これは $n$ の標準形であり、lem-fcp-standard の一意性から $x''=x$、$aq+y'=y$ である。$q\ge0$、$y'\ge0$ より $y=aq+y'\ge0$ となる。

硬貨で言えば、$a$ 円玉が $b$ 枚あれば $b$ 円玉 $a$ 枚と同じ金額なので、$a$ 円玉を $b-1$ 枚以下にまとめ直せる。まとめ直した後に $b$ 円玉の枚数が $0$ 以上なら払え、負なら払えない。
図 2 は $a=3$、$b=5$ で、整数を $x=0,1,2,3,4$ の 5 つの列に分けたものである。列 $x$ には標準形の $x$ が等しい数を並べ、下から $y=-2,-1,0,1,2,\ldots$ の順に置く。lem-fcp-criterion より、各列で表せる数は $y\ge0$ の段、つまり $3x$ から上である。
a=3, b=5 で整数を標準形の x ごとに 5 列に並べた表。各列は 3x から上（青）が表せる数で、その下の 0 以上の数（赤）が表せない数、灰色は負の数。赤の最大は列 x=4 の 7

主定理 1：表せない最大の数は $ab-a-b$

図 2 では、各列の表せない数の最大は、その列の最初の表せる数 $3x$ から $5$ を引いた $3x-5$ である。これが最も大きくなるのは右端の列 $x=4$ で、$3\cdot4-5=7$ になる。一般の $a$、$b$ でも同じ考えで最大が求まる。

表せない最大の数

$a$、$b$ を互いに素な正の整数とし、$g=ab-a-b$ とおく。
(1) $g$ は $a$ と $b$ で表せない。
(2) $g$ より大きい整数は、すべて $a$ と $b$ で表せる。
とくに $a\ge2$、$b\ge2$ のとき $g=(a-1)(b-1)-1\ge0$ で、$g$ は $a$ と $b$ で表せない $0$ 以上の整数のうち最大のものである。

標準形の $y$ の符号を調べる

$g=ab-a-b=a(b-1)+b\cdot(-1)$ であり、$0\le b-1\le b-1$ なので、これは $g$ の標準形である（lem-fcp-standard）。$y=-1<0$ なので、lem-fcp-criterion より $g$ は表せない。
$n>g$ とし、$n$ の標準形を $n=ax+by$（$0\le x\le b-1$）とする。$ax\le a(b-1)$ なので
$$ by=n-ax>g-a(b-1)=(ab-a-b)-(ab-a)=-b $$
である。両辺を $b>0$ で割ると $y>-1$ で、$y$ は整数なので $y\ge0$ である。lem-fcp-criterion より $n$ は表せる。
最後の主張。$(a-1)(b-1)-1=ab-a-b+1-1=g$ である。$a\ge2$、$b\ge2$ なら $(a-1)(b-1)\ge1$ なので $g\ge0$ である。(1) と (2) より、$g$ は表せない $0$ 以上の整数のうち最大である。

$a=1$ のときは $g=b-b-1=-1$ で、$0$ 以上の整数はすべて表せる（$n=1\cdot n+b\cdot0$）。これも (1)・(2) と合っている。

主定理 1 を確かめる

$a=3$、$b=5$：$g=15-3-5=7$ である。ex-fcp-start の結果と一致する。$8,9,10$ の標準形は $8=3\cdot1+5\cdot1$、$9=3\cdot3+5\cdot0$、$10=3\cdot0+5\cdot2$ で、どれも $y\ge0$ である。
$a=4$、$b=7$：$g=28-4-7=17$ である。$17$ の標準形は $17=4\cdot6+7\cdot(-1)$ で $y<0$ なので、$17$ は表せない。$18=4\cdot1+7\cdot2$、$19=4\cdot3+7\cdot1$、$20=4\cdot5+7\cdot0$、$21=4\cdot0+7\cdot3$ は表せる。$18$ から $21$ まで 4 つ続けて表せるので、$4$ を足していけば $18$ 以上はすべて表せる。
$a=5$、$b=8$：$g=40-5-8=27$ である。

数学的帰納法と整列性の命題「3 と 5 で作れる数」は、$8$ 以上の整数がすべて $3a+5b$ の形に書けることを、$8,9,10$ から $3$ ずつ足していく強い帰納法で示している。ex-fcp-max の (2) の「$a$ 個続けて表せれば、それ以上はすべて表せる」も同じ考え方である。thm-fcp-max は、どこから先がすべて表せるかを、一般の $a$、$b$ について式で与える。

主定理 2：表せない数の個数と対称性

図 1 では、$0$ から $7$ までの数を $n$ と $7-n$ の組にすると、どの組も「一方が表せて、他方が表せない」になっていた。

表せない数の対称性と個数

$a$、$b$ を互いに素な正の整数とし、$g=ab-a-b$ とおく。
(1) $0\le n\le g$ を満たす整数 $n$ について、「$n$ が $a$ と $b$ で表せる」ことと「$g-n$ が $a$ と $b$ で表せない」ことは同値である。
(2) $a$ と $b$ で表せない $0$ 以上の整数は、ちょうど $\dfrac{(a-1)(b-1)}2$ 個ある。

標準形を $g$ から引く

整数 $n$ の標準形を $n=ax+by$（$0\le x\le b-1$）とする。$g=a(b-1)+b\cdot(-1)$ から $n$ を引くと
$$ g-n=a(b-1-x)+b(-1-y) $$
である。$0\le x\le b-1$ より $0\le b-1-x\le b-1$ なので、これは $g-n$ の標準形である（lem-fcp-standard）。lem-fcp-criterion より、$n$ が表せることは $y\ge0$ と、$g-n$ が表せることは $-1-y\ge0$、つまり $y\le-1$ と同値である。整数 $y$ について「$y\ge0$」と「$y\le-1$」はちょうど一方だけが成り立つので、$n$ が表せることは、$g-n$ が表せないことと同値である。
$a=1$ または $b=1$ なら、$0$ 以上の整数はすべて表せて、$\dfrac{(a-1)(b-1)}2=0$ なので成り立つ。以下 $a\ge2$、$b\ge2$ とすると $g\ge0$ である。thm-fcp-max より、表せない $0$ 以上の整数はすべて $0$ 以上 $g$ 以下にある。この範囲の整数は $g+1=(a-1)(b-1)$ 個ある。
$0\le n\le g$ のとき $0\le g-n\le g$ なので、$n$ と $g-n$ を組にできる。$n=g-n$ となる $n$ はない。もしあれば、(1) で「$n$ が表せる」と「$n$ が表せない」が同値になり、矛盾するからである。したがって $0,1,\ldots,g$ の $(a-1)(b-1)$ 個の数は、$n\ne g-n$ の組 $\dfrac{(a-1)(b-1)}2$ 組にちょうど分かれる。(1) より、どの組にも表せない数がちょうど 1 つ入っている。よって表せない数は $\dfrac{(a-1)(b-1)}2$ 個である。

証明の (2) から、$(a-1)(b-1)$ はいつも偶数であることも分かる（互いに素な $a$、$b$ の少なくとも一方は奇数で、奇数から $1$ を引くと偶数になることからも確かめられる）。

主定理 2 を確かめる

$a=3$、$b=5$、$g=7$：組は $(0,7)$、$(1,6)$、$(2,5)$、$(3,4)$ で、表せない数は $7$、$1$、$2$、$4$ である。個数は $\dfrac{2\cdot4}2=4$ である。
$a=4$、$b=7$、$g=17$：表せない数は
$$ 1,\ 2,\ 3,\ 5,\ 6,\ 9,\ 10,\ 13,\ 17 $$
の 9 個で、$\dfrac{3\cdot6}2=9$ と一致する。$17$ から引くと $16,15,14,12,11,8,7,4,0$ で、これらはどれも表せる（たとえば $16=4\cdot4$、$15=4\cdot2+7$、$11=4+7$、$0=0$）。
$a=5$、$b=8$ の場合を開く
$g=27$ で、表せない数は $1,2,3,4,6,7,9,11,12,14,17,19,22,27$ の 14 個である。$\dfrac{4\cdot7}2=14$ と一致する。$27$ から引いた $26,25,24,23,21,20,18,16,15,13,10,8,5,0$ はどれも表せる（$26=5\cdot2+8\cdot2$、$23=5\cdot3+8$、$21=5+8\cdot2$、$13=5+8$ など）。

いくつかの組 $(a,b)$ を表にすると、次のようになる。表せない数の最大と個数は、どちらも $(a-1)(b-1)$ で決まる。

$(a,b)$	$(a-1)(b-1)$	表せない最大の数 $ab-a-b$	表せない数の個数	表せない数
$(2,3)$	$2$	$1$	$1$	$1$
$(2,5)$	$4$	$3$	$2$	$1,3$
$(3,4)$	$6$	$5$	$3$	$1,2,5$
$(3,5)$	$8$	$7$	$4$	$1,2,4,7$
$(4,5)$	$12$	$11$	$6$	$1,2,3,6,7,11$
$(3,7)$	$12$	$11$	$6$	$1,2,4,5,8,11$
$(4,7)$	$18$	$17$	$9$	$1,2,3,5,6,9,10,13,17$
$(5,7)$	$24$	$23$	$12$	$1,2,3,4,6,8,9,11,13,16,18,23$
$(5,8)$	$28$	$27$	$14$	（ex-fcp-count）

$(4,5)$ と $(3,7)$ は最大も個数も同じだが、表せない数の並びは違う。

格子点で見る

表せない数は、座標平面の格子点（$x$ 座標も $y$ 座標も整数の点）と 1 対 1 に対応させることもできる。$x$ 座標と $y$ 座標に正の整数をとる点 $(X,Y)$ を考える。

表せない数と直線の下の格子点

$a$、$b$ を互いに素な $2$ 以上の整数とする。正の整数 $X$、$Y$ で $aX+bY< ab$ を満たす組 $(X,Y)$ に、整数
$$ n=ab-aX-bY $$
を対応させると、これは「そのような組 $(X,Y)$ 全体」と「$a$ と $b$ で表せない $0$ 以上の整数全体」の 1 対 1 の対応になる。

標準形の $x$ と $y$ を $b-X$、$-Y$ と読む

段 1（組から表せない数へ）。正の整数 $X$、$Y$ が $aX+bY< ab$ を満たすとする。$n=ab-aX-bY>0$ である。$aX< ab$ より $X< b$、つまり $1\le X\le b-1$ なので、
$$ n=a(b-X)+b\cdot(-Y),\qquad 0\le b-X\le b-1 $$
は $n$ の標準形である（lem-fcp-standard）。$-Y\le-1<0$ なので、lem-fcp-criterion より $n$ は表せない。標準形はただ 1 通りなので、$n$ から $b-X$ と $-Y$、つまり $X$ と $Y$ が決まる。よって違う組からは違う $n$ ができる。
段 2（表せない数から組へ）。$n\ge0$ が表せないとし、標準形を $n=ax+by$（$0\le x\le b-1$）とすると、lem-fcp-criterion より $y\le-1$ である。$X=b-x$、$Y=-y$ とおくと $Y\ge1$、$1\le X\le b$ で、$n=a(b-X)-bY=ab-aX-bY$ である。$X=b$ なら $x=0$ で $n=by<0$ となり $n\ge0$ に反するので、$X\le b-1$ である。$n=0$ は表せるので $n>0$ で、$aX+bY=ab-n< ab$ となる。段 1 の対応でこの $(X,Y)$ から作る数は $n$ そのものなので、段 1 の対応ですべての表せない数が現れる。

図 3 は $a=3$、$b=5$ の場合で、直線 $3X+5Y=15$ より下にある格子点（$X\ge1$、$Y\ge1$）は $(1,1)$、$(2,1)$、$(3,1)$、$(1,2)$ の 4 個である。それぞれ $n=15-3X-5Y=7,4,1,2$ で、ex-fcp-start の表せない数 $1,2,4,7$ がちょうど 1 回ずつ現れる。
直線 3X+5Y=15 と、その下にある X≧1, Y≧1 の格子点 4 個（赤）。各点の横の数は 15−3X−5Y で、表せない数 7, 4, 1, 2 になる

格子点による個数の別証明

prop-fcp-lattice を使うと、thm-fcp-count の (2) を、長方形の中の格子点を数えて示せる。

別証明を開く

$1\le X\le b-1$、$1\le Y\le a-1$ の長方形の中の格子点は $(a-1)(b-1)$ 個ある。直線 $aX+bY=ab$ の上にはこのような格子点はない（$aX=b(a-Y)$ から $b$ が $aX$ を割り切り、$a$ と $b$ は互いに素なので $b$ が $X$ を割り切るが、$1\le X\le b-1$ に反する）。点 $(X,Y)$ を点 $(b-X,a-Y)$ に移すと、長方形の格子点は長方形の格子点に移り、$a(b-X)+b(a-Y)=2ab-(aX+bY)$ なので、直線より下の点と上の点が入れかわる。また、$X\ge1$、$Y\ge1$ で直線より下にある格子点は、$aX< ab$、$bY< ab$ より $X\le b-1$、$Y\le a-1$ を満たすので、すべて長方形の中にある。したがって直線より下の格子点は、長方形の格子点のちょうど半分の $\dfrac{(a-1)(b-1)}2$ 個で、prop-fcp-lattice より表せない数も同じ個数である。

図形の下の格子点を数える考え方は、ガウス記号と整数の個数で約数の個数の和を双曲線の下の格子点として数えるときにも使う。

例と反例

主定理の仮定を 1 つずつ外すと、結論がどう崩れるかを表にする。

外す条件	反例	成り立たなくなること
$a$ と $b$ が互いに素	$a=4$、$b=6$	表せない数に最大のものがある（ex-fcp-cx-gcd）
$x$、$y$ は $0$ 以上	$3x+5y$ で負の $x$、$y$ も許す	表せない整数がある（ex-fcp-cx-negative）
標準形の $0\le x\le b-1$	$8=3\cdot1+5\cdot1=3\cdot6+5\cdot(-2)$	表し方がただ 1 通り、$y$ の符号で判定できる（ex-fcp-cx-range）
硬貨が 2 種類	$5$、$7$、$9$ の 3 種類	表せない数が $n\leftrightarrow g-n$ で対になる（ex-fcp-cx-three）

反例：公約数があると表せない数が無限にある

$a=4$、$b=6$ では、$4x+6y$ は偶数なので、奇数はどれも表せない（ex-fcp-start2）。表せない数は $1,2,3,5,7,9,11,\ldots$ と限りなく続き、最大のものはない。公式に入れた $ab-a-b=24-4-6=14$ は $14=4\cdot2+6\cdot1$ と表せるので、「表せない最大の数」ではない。
一般に $d=\gcd(a,b)>1$ なら、$ax+by$ は $d$ の倍数なので、$d$ の倍数でない数はすべて表せない。lem-fcp-standard の証明の段 1 で $a$ と $b$ が互いに素であることを使っていて、そこが崩れる。$a=4$、$b=6$ で $x=0,1,2,3,4,5$ の $4x$ を $6$ で割った余りは $0,4,2,0,4,2$ で、同じ余りがくり返し現れる。

反例：負の枚数を許すとすべて表せる

$3x+5y$ で $x$、$y$ に負の整数も許すと、$3\cdot2+5\cdot(-1)=1$ なので、どの整数 $n$ も $n=3\cdot2n+5\cdot(-n)$ と書ける。たとえば $7=3\cdot14+5\cdot(-7)=3\cdot4+5\cdot(-1)$ である。表せない整数がなくなり、「表せない最大の数」という問いは意味をもたない。硬貨で言えば、お釣りをもらえるなら何円でも払える。この場合の整数解の全体は不定方程式の解法や整数の割り算と互除法の定理「1 次不定方程式」で求められる。

反例：$x$ の範囲を決めないと判定できない

$a=3$、$b=5$ で、$8$ は $8=3\cdot1+5\cdot1$ とも $8=3\cdot6+5\cdot(-2)$ とも書ける。2 つ目の書き方では $y=-2<0$ だが、$8$ は表せる。$x$ の範囲を $0\le x\le b-1$ に決めないと、整数解は $x$ を $5$ 増やして $y$ を $3$ 減らすことで無数に作れ、1 つの書き方の $y$ の符号だけでは表せるかどうか決まらない。lem-fcp-criterion が $y$ の符号で判定できるのは、標準形がただ 1 つに決まるからである。

反例：3 種類の硬貨では対称性が崩れる

$5$、$7$、$9$ の 3 種類で $5x+7y+9z$（$x,y,z\ge0$）と表せない $0$ 以上の整数は
$$ 1,\ 2,\ 3,\ 4,\ 6,\ 8,\ 11,\ 13 $$
の 8 個で、最大は $13$ である。$0$ から $13$ までを $n$ と $13-n$ の組にすると、組 $(2,11)$ では $2$ も $11$ も表せない（$11-5=6$、$11-7=4$、$11-9=2$ はどれも表せないので $11$ は表せない）。thm-fcp-count の (1) の対称性が成り立たない。個数も、$0$ から $13$ までの 14 個の半分の 7 個ではなく 8 個である。
3 種類の場合には、2 種類の $ab-a-b$ のような閉じた形の式がない（rem-fcp-three）。

演習

$5$ 円玉と $7$ 円玉

$5$ 円玉と $7$ 円玉だけで払えない金額の最大と、払えない金額の個数を求めよ。また、払えない金額をすべて挙げよ。

解答を開く

$5$ と $7$ は互いに素なので、thm-fcp-max より最大は $35-5-7=23$ 円、thm-fcp-count より個数は $\dfrac{4\cdot6}2=12$ 個である。$0$ から $23$ までで $5x+7y$ と表せるのは、$y=0$ の $0,5,10,15,20$、$y=1$ の $7,12,17,22$、$y=2$ の $14,19$、$y=3$ の $21$ の 12 個である。残りの $1,2,3,4,6,8,9,11,13,16,18,23$ の 12 個が払えない金額で、個数も最大も公式と一致する。$23$ から引くと $22,21,20,19,17,15,14,12,10,7,5,0$ で、これは表せる 12 個とちょうど同じである（thm-fcp-count の (1)）。

最大が $11$ になる組

互いに素な正の整数 $a< b$ で、$a$ と $b$ で表せない最大の数が $11$ になるものをすべて求めよ。また、そのとき表せない数はいくつあるか。

解答を開く

thm-fcp-max より $ab-a-b=11$、つまり $(a-1)(b-1)=12$ である（$a=1$ なら最大は $-1$ なので $a\ge2$）。$1\le a-1< b-1$ で積が $12$ になるのは $(a-1,b-1)=(1,12),(2,6),(3,4)$ で、$(a,b)=(2,13),(3,7),(4,5)$ となる。どれも互いに素である。表せない数の個数は、どれも thm-fcp-count より $\dfrac{12}2=6$ 個である（表の $(4,5)$、$(3,7)$ の行、$(2,13)$ では $1,3,5,7,9,11$）。

大学数学で見る：数の半群と 3 種類の硬貨

$a$ と $b$ で表せる数の全体 $S=\{ax+by\mid x,y\ge0\}$ は、$0$ を含み、2 つの元の和がまた $S$ に入る（$(ax+by)+(ax'+by')=a(x+x')+b(y+y')$）。このように、足し算で閉じていて $0$ を含む $0$ 以上の整数の集合で、$0$ 以上の整数のうち $S$ に入らないものが有限個であるものを、大学数学では 数の半群 と呼ぶ。thm-fcp-max は「$a$、$b$ が互いに素なら、$S$ は数の半群になり、入らない最大の数は $ab-a-b$」と言い換えられる。thm-fcp-count の (1) の性質をもつ数の半群は対称であるといい、2 つの数から作った半群はいつも対称である。

3 種類以上の硬貨

硬貨の種類を増やし、$a_1,\ldots,a_m$（最大公約数が $1$）で表せない最大の数を求める問題は、Wei26 では coin problem（硬貨の問題）と呼ばれ、この最大の数は Frobenius number と呼ばれている。同じ頁は、2 種類の場合の $a_1a_2-a_1-a_2$ を「数学の言い伝え（folklore）」と述べ、表せない数の個数が $\dfrac12(a_1-1)(a_2-1)$ であることも挙げている。3 種類の場合については、閉じた形の解はないが、値を速く計算できる半ば明示的な解が知られていると述べている。

3 種類の例を開く

$4,6,9$ では表せない数は $1,2,3,5,7,11$ で最大は $11$、$5,7,9$ では ex-fcp-cx-three のとおり最大は $13$、$3,5,7$ では表せない数は $1,2,4$ で最大は $4$ である（どれも $0$ から順に、表せる数から $a_i$ を足して作れる数を印を付けていく計算で求めた）。$3$ と $5$ に $7$ を加えると、$3$ と $5$ だけでは表せなかった $7$ が表せるようになり、最大が $7$ から $4$ に下がる。$4,6,9$ の $4$ と $6$ のように、3 つのうち 2 つが互いに素でなくても、3 つ全体の最大公約数が $1$ なら表せない数は有限個である。

さらに先へ

連続する整数の和は「連続する数の和」、この記事は「2 つの決まった数の和」で表す問題だった。次のエジプト式分数では、分数を「異なる単位分数の和」で表す。
標準形の証明で使った「$ax$ を $b$ で割った余りがすべて異なる」ことは、$a$ が $b$ を法として逆数をもつことと同じである。同じ考え方は合同式の計算規則や中国剰余定理（高校数学）でも使う。
格子点を数える問題としては、円の中の格子点を数える Gaussの円問題がある。