十分性は明らかであるから, 必要性を数学的帰納法で示す.

(i)

$n = 2$ のとき. こちらを参照.

(ii)

$n = k$ ($k$: $2$ 以上の整数) のとき, 主張が成り立つとする. $a_1x_1+\cdots +a_kx_k+a_{k+1}x_{k+1} = c$ が整数解をもつとする. さらに, $a_1,$ $\cdots,$ $a_k$ の最大公約数を $g_k$ とおき, $a_1,$ $\cdots,$ $a_k,$ $a_{k+1}$ の最大公約数を $g_{k+1}$ とおく. このとき, ある整数 $y$ に対して \[ a_1x_1+\cdots +a_kx_k = c-a_{k+1}y\] は整数解をもつから, 数学的帰納法の仮定によりある整数 $x$ について \[ c-a_{k+1}y = g_kx\] となる. $g_kx+a_{k+1}y = c$ は整数解 $(x,y)$ をもつから, (i) の結果により $c$ は $g_k$ と $a_{k+1}$ の最大公約数 $g_{k+1}$ の倍数となる. よって, $n = k+1$ の場合にも主張が成り立つ.

(i), (ii) から, $2$ 以上のすべての整数 $n$ に対して主張が成り立つ.

(1)

$r_k = r_l$ を仮定する. このとき, $ak-al = a(k-l)$ は $b$ の倍数になる. $a,$ $b$ は互いに素であるから, $k-l$ が $b$ の倍数にならざるを得ない. また, $0 \leqq k \leqq b-1,$ $-(b-1) \leqq -l \leqq 0$ から, \[ -(b-1) \leqq k-l \leqq b-1\] である. よって, $k-l = 0$ から, $k = l$ となる.

(2)

$a = ga',$ $b = gb',$ $c = gc',$ $a'x+b'y = 1$ ($a',$ $b',$ $c',$ $x,$ $y$: 整数) のとき, $a(c'x)+b(c'y) = c$ となるから, $c = g = 1$ の場合に示せばよい. このとき, 各整数 $k$ に対して $ak$ を $b$ で割った商を $q_k$ とおくと, $ak = bq_k+r_k$ から \[ ak+b(-q_k) = r_k\] となる. よって, $r_k = 1$ なる整数 $k$ の存在を示せばよい. (1) の対偶を考えると, $0$ 以上 $b-1$ 以下の整数 $k,$ $l$ の各組に対して \[ k \neq l \Longrightarrow r_k \neq r_l\] となるから, \[\{ r_0,\ \cdots,\ r_{b-1}\} = \{ 0,\ \cdots,\ b-1\}\] が成り立つ. よって, $r_k = 1$ なる整数 $k$ が $0$ 以上 $b-1$ 以下の整数から見つかる. ゆえに, $ax+by = c$ の整数解が存在する.

(1)

$c_1,$ $c_2 \in \mathbb Z,$ $i_1,$ $i_2 \in I$ のとき, $i_k = ax_k+by_k$ ($x_k,$ $y_k \in \mathbb Z,$ $k = 1,$ $2$) と表せるから, \[\begin{aligned} c_1i_1+c_2i_2 &= c_1(ax_1+by_1)+c_2(ax_2+by_2) \\ &= a(c_1x_1+c_2x_2)+b(c_1y_1+c_2y_2) \in I \end{aligned}\] $(\because c_1x_1+c_2x_2,\ c_1y_1+c_2y_2 \in \mathbb Z)$ が成り立つ.

(2)

(i)

$d \in I$ と (1) から, $z \in \mathbb Z$ のとき $dz \in I$ が成り立つので, $d\mathbb Z \subset I$ である.

(ii)

$n \in I$ とする. このとき, \[ n = dq+r \quad (q,\ r \in \mathbb Z,\ 0 \leqq r < d)\] と表せる. (1) から, \[ r = 1\cdot n+(-q)d \in I\] である. $d$ の最小性により $r = 0$ であるから, $n = dq \in d\mathbb Z$ が成り立つ. よって, $I \subset d\mathbb Z$ である.

(i), (ii) から, $I = d\mathbb Z$ である.

(3)

(i)

$a = ga',$ $b = gb',$ $d = ax+by$ $(a',\ b',\ x,\ y \in \mathbb Z)$ と表すと, $z \in \mathbb Z$ のとき \[ dz = (ga'x+gb'y)z = g(a'x+b'y)z \in g\mathbb Z\] $(\because (a'x+b'y)z \in \mathbb Z)$ となる. よって, $d\mathbb Z \subset g\mathbb Z$ である.

(ii)

\[\begin{aligned} a &= a\cdot 1+b\cdot 0 \in I = d\mathbb Z, \\ b &= a\cdot 0+b\cdot 1 \in I = d\mathbb Z \end{aligned}\] から, $d$ は $a,$ $b$ の公約数であり, $d$ は $g$ の約数, つまり $g$ は $d$ の倍数である. よって, 各整数 $z$ に対して, $gz$ は $d$ の倍数, つまり $gz \in d\mathbb Z$ である. したがって, $g\mathbb Z \subset d\mathbb Z$ である.

(i), (ii) から, $d\mathbb Z = g\mathbb Z$ であり, (2) と合わせると, $I = g\mathbb Z$ が得られる.

(1)

$a,$ $n$ は互いに素であるから, \[ ax+ny = 1\] つまり $ax-1 = ny$ の整数解 $x,$ $y$ が存在する. $x$ を $n$ で割った商を $q,$ 余りを $r$ とおくと, \[ ar-1 = n(y-aq)\] となるから, $x$ を $r$ に取り替えることにより, この $x$ は $0 \leqq x < n$ の範囲にとれる. $a,$ $y$ の方程式 $ax+ny = 1$ は解をもつから, $x,$ $n$ は互いに素であり, 特に $x \neq 0$ である. $0 < x' < n$ なる整数 $x'$ について $ax'-1$ も $n$ の倍数であるとすると, \[ a(x-x') = (ax-1)-(ax'-1)\] が $n$ の倍数で $a,$ $n$ が互いに素であることから $x-x'$ は $n$ の倍数となり, $-2n < x-x' < n$ から $x-x' = 0$ つまり $x = x'$ となる. ゆえに, $ax-1$ が $n$ の倍数となるような整数 $x$ が $0 < x < n$ の範囲にただ $1$ つ存在する.

(2)

$ab$ が $p$ の倍数であり, $a$ が $p$ の倍数でないとして, $b$ が $p$ の倍数であることを示せばよい. $a,$ $p$ は互いに素であるから, \[ ax+py = 1\] の整数解 $x,$ $y$ について \[ abx+pby = b\] が成り立ち, $abx,$ $pby$ は $p$ の倍数であるから, その和 $b$ は $p$ の倍数である.

　整数 $x$ の存在: $n$ に関する数学的帰納法で示す.

(i)

$n = 2$ のとき. $m_1x_1+a_1 = m_2x_2+a_2$ を満たす整数 $x_1,$ $x_2$ が存在することを示せばよいが, これは \[ m_1x_1+(-m_2)x_2 = a_2-a_1\] の整数解 $(x_1,x_2)$ が存在することからわかる.

(ii)

$n = k$ ($k$: $2$ 以上の整数) のとき条件を満たす整数が存在するとして, $n = k+1$ のときを考える. このとき, $b-a_1$ が $m_1$ の倍数, $\cdots,$ $b-a_k$ が $m_k$ の倍数であるような整数 $b$ が存在する. (i) から, $x-b$ が $m_1\cdots m_k$ の倍数, $x-a_{k+1}$ が $m_{k+1}$ の倍数であるような整数 $x$ が存在する. $m_j$ の倍数 $x-b,$ $b-a_j$ の和 \[ x-a_j = (x-b)+(b-a_j) \quad (1 \leqq j \leqq k)\] は $m_j$ の倍数であるから, $n = k+1$ のとき条件を満たす整数 $x$ が存在する.

(i), (ii) から, $n \geqq 2$ のとき, 条件を満たす整数 $x$ が存在する. $x$ を $m_1\cdots m_n$ で割った商を $q,$ 余りを $r$ とおくと, \[ r-a_j = x-a_j-m_1\cdots m_nq \quad (1 \leqq j \leqq n)\] は $m_j$ の倍数になるから, $x$ を $r$ に取り替えることにより, この $x$ は $0 \leqq x < m_1\cdots m_n$ の範囲にとれる.
　整数 $x$ の一意性: $0 \leqq x' < m_1\cdots m_n$ なる整数 $x'$ も条件を満たすとすると, \[ x-x' = (x-a_j)-(x'-a_j) \quad (1 \leqq j \leqq n)\] が $m_1,$ $\cdots,$ $m_n$ の倍数で $m_1,$ $\cdots,$ $m_n$ が互いに素であることから $x-x'$ は $m_1\cdots m_n$ の倍数になり, $-m_1\cdots m_n < x-x' < m_1\cdots m_n$ から $x-x' = 0,$ $x = x'$ となる.

(1)

整数 $x,$ $y$ が \[ ax+by = ab-a-b \quad \cdots [1]\] つまり \[ a(x+1)+b(y+1) = ab \quad \cdots [2]\] を満たすとする. \[ a(x+1) = b(a-y-1), \quad a(b-x-1) = b(y+1)\] であり, $a,$ $b$ は互いに素であるから, $x+1$ は $b$ の倍数, $y+1$ は $a$ の倍数である. $[2]$ の左辺が $ab$ を超える $ab$ の倍数になることはないから, $x,$ $y \geqq 0$ となることはない. ゆえに, $[1]$ は非負の整数解をもたない.

(2)

$c \geqq ab-a-b+1$ とする. $a,$ $b$ は互いに素であるから, \[ ax+by = c \quad \cdots [3]\] は整数解 $(x,y)$ をもつ. $x$ を $b$ で割った商 $q$ について $(x-bq,y+aq)$ も $[3]$ の整数解であるから, $0 \leqq x \leqq b-1$ なる整数解が存在する. このような整数解について, \[ y = \frac{c-ax}{b} \geqq \frac{ab-a-b+1-a(b-1)}{b} = \frac{1}{b}-1 > -1\] であるから, $y \geqq 0$ も成り立つ. ゆえに, $[3]$ は非負の整数解をもつ.

(1), (2) から, $a$ 円硬貨, $b$ 円硬貨のみを使ってちょうど支払えない金額, つまり $ax+by$ ($x,$ $y$: 非負整数) の形に表せない金額の最大値は $ab-a-b$ 円である.