✨ ベストアンサー ✨
ax+by=1が整数解をもつ⇔aとbが互いに素
これで考えてみます。
まずは十分条件について証明してみましょう。
☆ax+by=1が整数解をもつ⇛aとbが互いに素
[証明]
a,bの公約数が2以上の整数dであるとき、ax+byは必ずdの倍数になる。したがって、ax+by=1を満たすのははa,bの公約数が1、つまりa,bが互いに素である。
[証明終]
続いて、必要条件について証明していきます。こちらの証明はやや難ですので気合を入れましょう！
☆aとbが互いに素⇛ax+by=1が整数解をもつ
[証明]
a,bが互いに素であるとき、
まず、b個の整数a,2a,3a...baをbで割ったときの余りについて考える。
a,2a,3a...baのうち、任意の2つの整数をAa.Baとする。（1≦A＜B≦b）
ここで、Aa,Baをbで割ったときの余りが等しいと仮定する。
このとき、Ba-Aa=a(B-A)はbで割り切れることになる。
しかし、0＜B-A＜bでありaとbは互いに素であるのでa(B-A)はbで割り切ることは出来ない。
したがって、b個の整数a,2a,3a...baをbで割ったときの余りはすべて異なる。
上記より、a,2a,3a...baをbで割ったときの余りが1となる整数が1つだけ存在する。その整数をxaとおく。
このときの商を-yとすると、
xa=b(-y)+1が成り立つ。
よって、a,bが互いに素であるとき、ax+by=1が整数解(x,y)をもつ。
[証明終]
ここから下は本題とは離れるので読まなくても大丈夫です。
なるべく簡潔にするつもりがヘビーになってしまいました…。必要条件の証明は証明するのにもう一つの証明を挟む面倒な形式です。
「a,2a,3a...baの中にbで割ると1余る整数が1つだけ存在する」このように値が分かっていなくても存在していることを証明する方法を鳩ノ巣原理なんて言ったりします。この論法は様々な証明に活用出来るので考え方は知っておいて損はないと思います！もし余力があれば調べてみてください。
詳しくありがとうございます！