互いに素な数の線形結合

命題

$ a_1,\dots,a_nを正の整数とし、それらの最大公約数を$ d = \gcd(a_1,\dots, a_n)とする。集合$ Sを次のように定める。

$ S = \left\{\sum_{i=1}^n x_i a_i\mid x_i\in\mathbb Z_{\geq 0} \right\}.

このとき $ \exist M\in d\mathbb Z_{> 0}\; \mathrm{s.t.}\; m\geq M,\ m|\, d \implies m\in S.

(証明)

Bézout の補題より

$ \sum_{i=1}^n x_ia_i = d

となるような整数$ x_1,\dots, x_nが存在する。今、上の式で正の項の総和を$ d^+、負の項の絶対値の総和を$ d^-とすると

$ d^+ - d^- = d.

定義より$ d^+, d^-\in Sである。

ここで$ M = d^- \times (d^- - 1)とし、$ m\geq M,\ m|dとする。$ d^-で$ mを割ることで

$ m = qd^- + r

を得る。ここで$ q \geq (d^--1),\ 0\leq r\leq d^--1。今、$ m,\ qd^-は$ dの倍数なので$ rもそうである。そこで$ r=kdとする。以上より二つ目の等式を用いると

$ m = qd^- + k(d^+ - d^-),

$ m = kd^+ + (q - k)d^-.

$ Sは足し算と自然数倍の下で閉じているので$ m\in S。$ \square