MathLabs

第2問

a1,a2,a3,…a_1, a_2, a_3, \ldots を正の整数からなる無限増加数列とする。任意の p≥1p \ge 1 に対して、am=xap+yaqa_m = xa_p + ya_q の形（ただし x,yx, y は正の整数、q>pq > p）に書ける ama_m が無限に存在することを証明せよ。
ステップ 1/4: pp を固定し、apa_p で割った余りに着目する
前のステップ次のステップ
ざっくり言うと

apa_p で割ったときの余りは 0,1,…,ap−10, 1, \ldots, a_p-1 の apa_p 通りしかないが、位置 pp より後ろには数列の項が無限に存在する。無限個の鳩と有限個の巣穴に対する鳩の巣原理と同様に、いずれかの余りが無限回現れるはずである。そしてその余りを共有する任意の二項の差は apa_p の倍数になり、これはまさに目標の式 xap+yaqxa_p+ya_q が必要とする構造である。

a1<a2<a3<⋯ ,p≥1 fixeda_1<a_2<a_3<\cdots,\quad p\ge 1 \text{ fixed}
詳しい解説

p≥1p \ge 1 を固定する。各添字 ii に対し、aia_i を apa_p で割った余りを rir_i とすると ri∈{0,1,…,ap−1}r_i \in \{0, 1, \ldots, a_p - 1\} であり、取りうる値は apa_p 通りしかない。数列 a1,a2,a3,…a_1, a_2, a_3, \ldots は無限であるから、鳩の巣原理により、少なくとも一つの余り rr が無限個の添字 ii で現れる。