ユークリッドの互除法ごじょほうと一次いちじ不定方程式ふていほうていしき

2.1最大公約数さいだいこうやくすうGreatest common divisor

$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,b)$\gcd(a, b) とは、$a$a と $b$b の共通きょうつう約数やくすうのうち最大さいだいのものである。$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,b)=d$\gcd(a, b) = d は「$a$a と $b$b を公平こうへいに割わり切きれる最大さいだいの単位たんい」を意味いみする。

2.2一次いちじ不定方程式ふていほうていしきLinear Diophantine equation

のように、係数けいすうが整数せいすうで整数解せいすうかいを求もとめる方程式ほうていしきを一次いちじ不定方程式ふていほうていしきLinear Diophantine equationという。

「不定ふてい」の命名めいめい：解かいが一意いちいでなく（不定ふてい＝定さだまらない）、無数むすうに存在そんざいし得うることから命名めいめい。Diophantine（ディオファントス）はこの種類しゅるいの方程式ほうていしきを研究けんきゅうした 3 世紀せいきのギリシャ数学者すうがくしゃの名なに由来ゆらい。

2.3ユークリッドの互除法ごじょほう

「互ご」の命名めいめい：互たがいに除わり合あう操作そうさの繰くり返かえしから命名めいめい。英語えいご Euclidean algorithm（ユークリッドの算法さんぽう）は古代こだいギリシャの数学者すうがくしゃユークリッドが著書ちょしょ「原論げんろん」（紀元前きげんぜん 3 世紀せいき）に記しるしたことから命名めいめい。

4.11. なぜ余あまりへ落おとしてよいか

$a=bq+r$a = bq + r のとき、$a$a と $b$b の共通きょうつう約数やくすう $d$d は $r=a-bq$r = a - bq も割わるので $d$d は $b$b と $r$r の共通きょうつう約数やくすうでもある。逆ぎゃくも同様どうように成立せいりつするので

余あまりへ落おとしても共通きょうつう約数やくすうの集合しゅうごうが変かわらない—これが互除法ごじょほうの核心かくしんである。

4.22. ユークリッドの互除法ごじょほう（例れい：$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(84,30)$\gcd(84, 30)）

$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(84,30)=6$\gcd(84, 30) = 6。

4.33. 拡張互除法かくちょうごじょほう：$\text{[PARSE ERROR: Undefined("Command("gcd")")]}$\gcd を $ax+by$ax+by の形かたちへ

ステップ 2 から逆向ぎゃくむきに代入だいにゅうする：

ステップ 1 より $24=84-30\times 2$24 = 84 - 30 \times 2 を代入だいにゅう：

したがって $x=-1$x = -1, $y=3$y = 3 が一ひとつの解かいである。

4.44. 一次いちじ不定方程式ふていほうていしきの可解条件かかいじょうけん

$ax+by=c$ax + by = c が整数解せいすうかいを持もつための必要十分条件ひつようじゅうぶんじょうけん：

証明しょうめい（必要ひつよう条件じょうけん）：$d=\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,b)$d = \gcd(a, b) とすると $a=d{a}^{\prime }$a = da', $b=d{b}^{\prime }$b = db' なので $ax+by=d(a^{\prime }x+b^{\prime }y)$ax + by = d(a'x + b'y) は必かならず $d$d の倍数ばいすう。

証明しょうめい（十分じゅうぶん条件じょうけん）：$c=dk$c = dk かつ $d=a{x}_0+b{y}_0$d = ax_0 + by_0 なら $c=a\left(k{x}_0\right)+b\left(k{y}_0\right)$c = a(kx_0) + b(ky_0)。

一般解いっぱんかい：一ひとつの解かい $(x_0,y_0)$(x_0, y_0) があれば全解ぜんかいは

この式しきが全解ぜんかいを与あたえることを両方向りょうほうこうから確認かくにんする。まず、この式しきを左辺さへんへ代入だいにゅうすると、$t$t を含ふくむ部分ぶぶんは

と相殺そうさいする。したがって、すべての $t\in \mathbb{Z}$t\in\mathbb Z について元もとの方程式ほうていしきを満みたす。

逆ぎゃくに、$(x,y)$(x,y) を任意にんいの解かいとする。$(x_0,y_0)$(x_0,y_0) も解かいなので、差さを取とると

である。$a=d{a}^{\prime }$a=da'、$b=d{b}^{\prime }$b=db'、$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a^{\prime },b^{\prime })=1$\gcd(a',b')=1 と書かけば、$a^{\prime }(x-x_0)=-b^{\prime }(y-y_0)$a'(x-x_0)=-b'(y-y_0) である。互たがいに素そであることから $b^{\prime }\mid (x-x_0)$b'\mid(x-x_0) なので、ある $t\in \mathbb{Z}$t\in\mathbb Z により $x-x_0=b^{\prime }t=(b/d)t$x-x_0=b't=(b/d)t と書かける。これを差さの式しきへ戻もどすと $y-y_0=-a^{\prime }t=-(a/d)t$y-y_0=-a't=-(a/d)t を得える。よって任意にんいの解かいが上うえの形かたちに含ふくまれ、これが全解ぜんかいである。

4.55. mod 逆元ぎゃくげんとの関係かんけい

$ax\equiv 1\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$ax \equiv 1 \pmod n が解とけることと $\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)=1$\gcd(a, n) = 1 は同値どうちである。これは $ax+ny=1$ax + ny = 1（一次いちじ不定方程式ふていほうていしき）が解とけることと同値どうちだからである。互除法ごじょほうは mod 逆元ぎゃくげんの計算けいさん（中国ちゅうごく剰余定理じょうよていりの中核ちゅうかく）を支ささえる。