aとbが互いに素でないとき、ax+by=1が整数解をもたないことを証明せよ

一般にax+byの形で表せる最小の自然数はgcd(a.b)となります。
それを証明します。
証明
gcd(a.b)＞ax+by・・・★ と表現できたとする。
するとax+by=gcd(a.b)(px+qy)・・①とかけます。
ところでｐとｑは互いにそですから
一次方程式定理よりpx+qy=1・・・・②とかけるはずです。
★に①を代入し両辺をgcd(a.b)でわり1>px+qy を得ます。しかし①より
1>1となって矛盾です。
背理法により証明が完成しました。

gcd(a.b)が１より大きいのですから
ax+byの形で表せる最小の自然数も１より大きいはずです。

背理法で証明しますね。(^^♪
.
a，bの最大公約数をgとします。
.
ただし、gは2以上の自然数と仮定します。
.
このとき、a=gA，b=gBとおけます。
.
ただし、A，Bは正の整数
.
元の方程式に代入すると、
.
gAx+gBy=1
.
g(Ax+By)=1
.
A，x，B，yは、整数なので、Ax+Byは整数です。
.
2以上の整数gと、整数Ax+Byをかけて、1になることはありません。

たがいに素でないとすると１以外の共通因数をもっている。それをｍとすれば
左辺はｍの倍数
右辺はｍの倍数でない
矛盾。