平山：とりあえず有界性ですか
平石：それぞれ $c$ 倍と $a$ 倍して互除法すれば有界性は分かるのでは
平山：常に $ad-bc$ の約数だから $\ne 0$ の条件あるんですね、理解
宿田：$a$ と $c$ 互いに素なら等号のまま $(n+\mathrm{h}\mathrm{o}\mathrm{g}\mathrm{e},\mathrm{h}\mathrm{o}\mathrm{g}\mathrm{e})$ の形にできるから大丈夫じゃないですか
馬杉：互いに素じゃない場合を考えた方が良さそう
平山：なんか $an+b$ だけ考えれば良さそうな気が
馬杉：$gcd(a,b,c,d)=1$ って条件あんま使ってないけど
宿田：それ必要ある？
平山：無かったら $1$ が入らなくなるよ
宿田：あ、確かに
平山：というか一般の場合も互除法して $c=0$ とみなしていいよね
兒玉：$ad\ne bc$ のおかげで互除法しても $d\ne 0$ になるのか
平山：互いに素の条件も保たれる
馬杉：アイディアとしては、$g=gcd(an+b,d)$ のときに $g$ の素因数 $p$ について $g/p$ を作りたくて
馬杉：そうすると $n$ に $n+g/p$ みたいなのを代入したくなる
馬杉：$a$ が $p$ の倍数の時だけ不味くて、その場合は互いに素の条件に反する
平山：ということはもう各素数だけ見れば良いのかな？
兒玉：これ $d$ あんまし要らない？$an+b$ で素数のオーダーを全部取るみたいな方針が良さげ
平山：$a$ は登場し得る素数と互いに素だから中国剰余定理みたいにして終わりですね
馬杉：$ad\ne bc$ から有界性を保証しないとまずいからそれだけ

• なんだかんだ色々と特殊な気がするのでコメントが難しい
• 最大公約数から互除法というワードが出てくるのは自然…？
• 中国剰余定理はあまり深く考えず使えるようにしたい

$gcd(an+b,cn+d)=gcd(an+b,(a-c)n+(b-d))$ に留意すると, 以下のような変換 $$(a,b,c,d)\mapsto (a,b,a-c,b-d)\mathrm{o}\mathrm{r}(a,b,c-a,d-b)$$ を組 $(a,c)$ に対するEuclidの互除法と同様に実行することで, $c=0$ の場合に帰着できる. このとき明らかに $ad-bc$ および $gcd(a,b,c,d)$ は変換によって不変であるから, 帰着後において $d\ne 0$ および $gcd(a,b,d)=1$ である.

任意の $S$ の元は $d$ の約数であるから, 特に $S$ は有限集合である. $S=1$ のとき示すことはない. そうでないとき, $S$ の元の素因数として現れるものを $p_1,\dots ,p_k$ とし, $S$ の元全体について $p_i$ で割りきれる回数の最大値を $e_i$ とおく. このとき, 以下のように定めればよいことを示す. $$M=p_1^{e_1}\cdots p_k^{e_k}$$ すなわち, 各 $i$ に対し $0\leqq f_i\leqq e_i$ を任意に定めたとき, $$T=p_1^{f_1}\cdots p_k^{f_k}$$ が $S$ に含まれることを示せば十分である.

いま $a$ が $p_i$ の倍数であったとすると, $b$ も $p_i$ の倍数となり $gcd(a,b,d)=1$ に反する. したがって各 $i$ に対し $$a{n}_i+b\equiv p_i^{f_i}(\mathrm{m}\mathrm{o}\mathrm{d}{p}_i^{e_i})$$ なる $n_i$ がとれ, さらに中国剰余定理より $$aN+b\equiv T(\mathrm{m}\mathrm{o}\mathrm{d}M)$$ なる $N$ が存在する. このとき以上の議論より $gcd(aN+b,d)=T$ であるから, 題意は示された.