ax+by=1の整数解

ax+by=1⇒a,bは互いに素
ユークリッド互除法

ax+by=1⇒a,bは互いに素

不定方程式ax+by=1の性質について。

不定方程式ax+by=1に整数解があると仮定。
gcd(a,b)=d(仮定)
仮定と最大公約数定義より、aはdの整数a’倍。
よって
a=a’d,b=b’d(最大公約数定義)
と構成できます。

a,bに代入して
a’dx+b’dy=1(代入)
d(a’x+b’y)=1(分配法則)
(a’x+b’y)は整数。かつgcd(a,b)=dはその性質上は正。
それらの乗法が1。すなわち
d=1

ax+bx=1になるのは、最大公約数が1の場合のみ。すなわち、a,bが互いに素である場合のみ。
よって
ax+by=1⇒a,bは互いに素

a,bが互いに素⇒ax+bx=1

命題
a,bが互いに素ならば、ax+bx=1が整数解を持つ

ユークリッド互除法

整数a,bの最大公約数を考えます。

gcd(a,b)=d(最大公約数)
aをbで割った商がq,余りがrとすると
a=bq+r(除法定義)
r=a-bq(加法逆元)…①

最大公約数の定義よりbを共有するgcd(a,b)とgcd(b,r)は約数を共有…②

a=x･gcd(a,b)(最大公約数)…③
b=y･gcd(a,b)(最大公約数)…④
①の式に③④を代入
r=a-bq(①)
r=x･gcd(a,b)-y･gcd(a,b)(③④代入)
r=gcd(a,b)(x-y)(分配法則)…⑤

⑤はgcd(a,b)がrの約数であることを示しています。

また、gcd(a,b)の性質上、それは同時にbの約数でもあります。

gcd(a,b)はbとrの公約数なので、その最大公約数との間には
gcd(a,b)≤gcd(r,b)…※1
が成り立ちます。

同様に
r=r’gcd(r,b)
b=b’gcd(r,b)

①へ代入。
a=q･b’･gcd(r,b)+r’･gcd(r,b)(代入)
a=gcd(r,b)(q･b’+r’)(分配法則)

gcd(r,b)はaの約数なので、
gcd(r,b)≤gcd(a,b)(最大公約数)…※2
が成り立つ。

※1※2より
gcd(r,b)=gcd(a,b)(反対称関係)

最大公約数

勝手に使った概念のお勉強。

最大公約数は一言で言えば二つの整数の「約数の内で最大のもの」。

約数

整数 a ≠ 0 が N の約数であるとは、「ある整数 b をとると N = ab が成立することである」であるが、条件「a ≠ 0」を外すこともある。このときは、N = 0 のときに限り 0 も約数になる。約数が無数にある整数は 0 だけである。

ウィキペディア

最大公約数

最大公約数（さいだいこうやくすう、英: greatest common divisor[注釈 1]）とは、すべての公約数を約数にもつ公約数である。

素朴な定義
以下では、自然数は

$\displaystyle 0$ を含むとし、$\displaystyle a$ が $\displaystyle b$ を割り切ること（つまり $\displaystyle b=ca$ となる自然数 $\displaystyle c$ が存在すること）を$\displaystyle a\mid b$ と表す。

写像 $\displaystyle \gcd \colon \mathbb {N} ^{n}\to \mathbb {N} ;(a_{1},\dots ,a_{n})\mapsto d$ を

すべての $\displaystyle 1\leqq i\leqq n$ に対して $\displaystyle d\mid a_{i}$ であり、

すべての自然数 $\displaystyle b$ に対し、すべての$\displaystyle 1\leqq i\leqq n$ に対して $\displaystyle b\mid a_{i}$ ならば $\displaystyle b\mid d$ となるように定める。

$\displaystyle d$ を$\displaystyle a_{1},\dots ,a_{n}$ の最大公約数といい、$\displaystyle d$を$\displaystyle a_{1},\dots ,a_{n}$ の最大公約数といい、$\displaystyle \gcd(a_{1},\dots ,a_{n})$ や $\displaystyle (a_{1},\dots ,a_{n})$ と表す。

ウィキペディア