整数 1次合同式 Bachetの定理の証明、除法の定理、Euclidの互除法、互いに素、整数解、必要十分条件、帰納法、1次不定方程式
親切な代数学演習 新装2版―整数・群・環・体 (加藤 明史(著)、現代数学社)の第Ⅰ部(整数)、第4章(1次合同式)の問1の解答を求めてみる。
に整数解が存在するならば、左辺はaとbの最大公約数の倍数になる。
また右辺もaとbの最大公約数の倍数である。
よって、
ゆえに、
逆に、
とする。
のとき、
よって、
が解となる。
のときも同様に考える。
の場合。
aとbの符号が正の場合を考えれば十分。 この解の符号を変更すればよい。
のとき、
なので、
よって、
という解をもつ。
の場合。
を満たす整数
が存在する。
これについて、
で、
ならば、
よって、 帰納法より、
は整数解をもつ。
（証明終）