§C3.4フロベニウスの硬貨問題

証明 ($ab - a - b$が表すことができないこと).$ab - a - b = ax + by$（$x \ge 0$、$y \ge 0$は整数）と書くことができたと仮定する。両辺に$a + b$を加えると

となる。この式から、$a$は$b(y+1)$を割り切る。$\gcd(a,b) = 1$であるから、素因数分解の一意性により$a$は$y+1$を割り切る。$y + 1 \ge 1$であるから$y + 1 \ge a$であり、したがって$b(y+1) \ge ab$である。一方、$x + 1 \ge 1$であるから$a(x+1) \ge a > 0$である。この二つを足すと

となるが、$ab>ab$は成り立たない。よって$ab - a - b$は表すことができない。▨

証明 ($ab - a - b$より大きい整数が表すことができること).$n > ab - a - b$を満たす整数$n$を取る。$\gcd(a,b) = 1$であるから、一次不定方程式$ax + by = n$は整数解を持ち、その一般解は、解を一つ$(x_0, y_0)$とすると$x = x_0 + bt$、$y = y_0 - at$（$t$は整数）と書くことができる。

$x$を$b$で割った余りは$t$の取り方によらないので、$t$を選んで$0 \le x \le b - 1$とすることができる。この$x$に対する$y$について、$by = n - ax$であり、$x \le b-1$と$n > ab - a - b$から

を得る。$b > 0$であるから$y > -1$であり、$y$は整数であるから$y \ge 0$である。$x \ge 0$もすでに満たされているので、$n$は$a$と$b$で表すことができる。▨

証明.$0 \le n \le N$を満たす整数$n$を取る。$n = ax + by$、$N - n = ax' + by'$（$x, y, x', y'$はいずれも$0$以上の整数）と書くことができたとすると、辺ごとに加えて$N = a(x+x') + b(y+y')$となり、定理 3.1の 1 に反する。したがって、$n$と$N-n$の両方が表すことができることはない。

一方、$\gcd(a,b) = 1$であるから$ax + by = n$は整数解を持ち、前の証明と同じ理由で$0 \le x \le b-1$を満たす整数解$(x,y)$を取ることができる。$y \ge 0$であれば$n$が表すことができる。$y \le -1$であるときは、

と変形する。$0 \le x \le b-1$より$b - 1 - x \ge 0$であり、$y \le -1$より$-1-y \ge 0$であるから、$N - n$が表すことができる。したがって、$n$と$N-n$の少なくとも一方が表すことができる。▨

証明.$N = ab - a - b$とおく。定理 3.1より、$N$より大きい整数はすべて表すことができる。負の整数は定義の対象ではない。したがって、表すことができない$0$以上の整数は、$0$以上$N$以下の範囲にある。この範囲にある整数の個数は

である。$n$がこの範囲にあれば$N - n$もこの範囲にあるので、$n \mapsto N - n$はこの範囲の整数の入れ替えを与える。定理 4.1により、$n$と$N-n$のうちちょうど一方が表すことができる。とくに$n = N - n$となる$n$は存在しない。もし存在すれば、その$n$について「ちょうど一方」が成り立たない。

したがって、$0$以上$N$以下の$(a-1)(b-1)$個の整数は、$n$と$N-n$という二つずつの組へ重複なく分かれ、各組から表すことができないものがちょうど一つ出る。よって、表すことができない$0$以上の整数の個数は$\dfrac{(a-1)(b-1)}{2}$である。▨