前の3a + 4bと書かれる自然数の話の 一般化されたこんな問題を考えましょう.

問: 互いに素な二つの自然数\(a\), \(b\)をとる. 以下の命題は正しいか?

ある自然数\(N\)があって, \(N\)以上の自然数\(n\)に対して, 自然数 \(x, y\)があって \(n = ax + by\) が成り立つ.

解: 正しい. \(N = ab + 1\)と取れること, すなわち \(ab + 1\)以上の自然数 \(n\)に対して ある自然数 \(x, y\)があって \(n = ax + by\) が成り立つことを示す.

\[A := \{ n - by; y \in \{1, 2, \ldots, a \} \}\]

のある元が正の \(a\)の倍数であることを示せば十分. \(n \ge ab + 1\)より, この集合の任意の元は正の数である.

\(A\)の任意の元は \(a\)を法として異なることを示す. 任意に\(y, y^\prime \in \{1, 2, \ldots, a \}\) を取り,

\[n - by \equiv n - by^\prime \pmod{a}\]

とすると,

\[by \equiv by^\prime \pmod{a}.\]

さらに \(a\)と\(b\)が互いに素であるから

\[y \equiv y^\prime \pmod{a}.\]

したがって, \(A\)の各元は\(a\)を法として異なる. よって, \(A\)の位数は \(a\)であるから, \(A\)の元で \(a\)の倍数の正数が存在する. ☐