EuclideanEuclidean 互除法ごじょほうと一次いちじ不定方程式ふていほうていしき

date2026-03-28descriptionユークリッドの互除法を、最大公約数を余りへ落として保つ手順として説明し、一次不定方程式との関係まで丁寧に導きます。prerequisites整数の性質の基本 / 文字式の基本type講義statusactive

mathalgebrahighschoolundergraduatelecture

導入どうにゅう

この講義こうぎで最重要さいじゅうようなのは、最大公約数さいだいこうやくすうは余あまりへ落おとしても変かわらず、その事実じじつを逆向ぎゃくむきにたどると $a x + b y = d$ の形かたちの方程式ほうていしきが解とけることです。

互除法ごじょほうは「最大公約数さいだいこうやくすうを求もとめる手順てじゅん」としてだけ覚おぼえると浅あさいです。本当ほんとうは、整数せいすうの割わり算ざんの構造こうぞうと、一次いちじ不定方程式ふていほうていしきの可解条件かかいじょうけんを結むすぶ中心的ちゅうしんてきな道具どうぐです。

用語ようごと定義ていぎ

最大公約数さいだいこうやくすうGreatest common divisor とは、2 整数せいすう $a, b$ の共通きょうつう約数やくすうのうち最大さいだいのものです。

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

a x + b y = c

のように、整数解せいすうかいを求もとめる方程式ほうていしきです。

方針ほうしん

まず

[PARSE ERROR: Undefined("Command(\"gcd\")")] (a, b) = [PARSE ERROR: Undefined("Command(\"gcd\")")] (b, r) (a = b q + r)

を確認かくにんし、それを繰くり返かえして最大公約数さいだいこうやくすうを求もとめます。そのあと、逆向ぎゃくむきに代入だいにゅうして $[PARSE ERROR: Undefined("Command(\"gcd\")")] (a, b)$ を $a x + b y$ の形かたちに戻もどし、一次いちじ不定方程式ふていほうていしきの可解条件かかいじょうけんへつなげます。

data/lecture/math/algebra/整数の性質の基本-講義.n.md data/lecture/math/abstract-algebra/合同式とmod演算の基本-講義.n.md

直感的ちょっかんてきな説明せつめい

大おおきい数かずどうしの最大公約数さいだいこうやくすうを直接ちょくせつ見みるのは難むずかしいですが、割わった余あまりを見みると情報じょうほうを失うしなわずに数かずを小ちいさくできます。しかも、その余あまりをたどった計算けいさんは逆向ぎゃくむきにも読よめるので、最大公約数さいだいこうやくすうを $a x + b y$ の形かたちで表あらわせます。

厳密げんみつな説明せつめい

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

a = b q + r

とします。このとき

[PARSE ERROR: Undefined("Command(\"gcd\")")] (a, b) = [PARSE ERROR: Undefined("Command(\"gcd\")")] (b, r)

が成なり立たちます。

$a$ と $b$ の共通きょうつう約数やくすう $d$ は

r = a - b q

も割わるので、 $d$ は $b$ と $r$ の共通きょうつう約数やくすうです。逆ぎゃくに、 $b$ と $r$ の共通きょうつう約数やくすうは

a = b q + r

を割わるので、 $a$ と $b$ の共通きょうつう約数やくすうでもあります。したがって共通きょうつう約数やくすうの集合しゅうごうが一致いっちし、最大公約数さいだいこうやくすうも一致いっちします。

2. EuclideanEuclidean 互除法ごじょほう

たとえば $84$ と $30$ なら

84 = 30 \cdot 2 + 24

30 = 24 \cdot 1 + 6

24 = 6 \cdot 4 + 0

となるので、

[PARSE ERROR: Undefined("Command(\"gcd\")")] (84, 30) = 6

です。

3. なぜ逆向ぎゃくむきにたどるのか

最後さいごの 0 直前ちょくぜんに現あらわれた 6 を、前まえの式しきへ戻もどしていきます。

6 = 30 - 24

さらに

24 = 84 - 30 \cdot 2

なので

6 = 30 - (84 - 30 \cdot 2) = 3 \cdot 30 - 84

です。つまり

6 = (- 1) \cdot 84 + 3 \cdot 30

と書かけました。これで最大公約数さいだいこうやくすうが $a x + b y$ の形かたちに表あらわせることが分わかります。

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

a x + b y = c

が整数解せいすうかいを持もつための必要十分条件ひつようじゅうぶんじょうけんは

[PARSE ERROR: Undefined("Command(\"gcd\")")] (a, b) ∣ c

です。

なぜなら、 $d = [PARSE ERROR: Undefined("Command(\"gcd\")")] (a, b)$ とすると $a = d a^{'}, b = d b^{'}$ と書かけるので、

a x + b y = d (a^{'} x + b^{'} y)

は必かならず $d$ の倍数ばいすうです。したがって解かいがあるなら $c$ は $d$ の倍数ばいすうでなければなりません。

逆ぎゃくに $c = d k$ と書かけ、しかも

d = a x_{0} + b y_{0}

と表あらわせていれば、

c = k (a x_{0} + b y_{0}) = a (k x_{0}) + b (k y_{0})

なので解かいが作つくれます。

5. mod 演算えんざんとのつながり

a x \equiv 1 [PARSE ERROR: Undefined("Command(\"pmod\")")] n

が解とけるのは、 $a$ と $n$ が互たがいに素そのときでした。これは

a x + n y = 1

が解とけることと同値どうちです。したがって、mod 演算えんざんで逆元ぎゃくげんを求もとめるときにも、互除法ごじょほうが本質的ほんしつてきに使つかわれています。

別べつの見方みかた

整数論せいすうろんの見方みかた

最大公約数さいだいこうやくすうを計算けいさんする道具どうぐとして見みる見方みかたです。

線形代数的せんけいだいすうてきな見方みかた

$a x + b y$ の整数係数せいすうけいすう線形結合せんけいけつごうの中なかで最小さいしょうの正せいのものが最大公約数さいだいこうやくすうになる、と見みる見方みかたです。

構造的こうぞうてきな見方みかた

mod 演算えんざんの逆元ぎゃくげんや体たいの話はなしの背後はいごに、互除法ごじょほうがあると見みる見方みかたです。

見分みわけ方かた

最大公約数さいだいこうやくすうを求もとめたいなら、余あまりへ落おとせるかを見みます。
$a x + b y = c$ の形かたちが出でたら、まず $[PARSE ERROR: Undefined("Command(\"gcd\")")] (a, b) ∣ c$ を確認かくにんします。
mod 演算えんざんで割わり算ざんしたいなら、逆元ぎゃくげんの存在そんざいを互除法ごじょほうで調しらべます。

どこまで成なり立たつか

ここでは 2 変数へんすうの一次いちじ不定方程式ふていほうていしきに限かぎりました。より高次こうじや多変数たへんすうでも整数解せいすうかいの問題もんだいはありますが、まずは $a x + b y = c$ と互除法ごじょほうの関係かんけいが最重要さいじゅうようです。

最終形さいしゅうけい

[PARSE ERROR: Undefined("Command(\"boxed\")")] [PARSE ERROR: Undefined("Command(\"gcd\")")] (a, b) = [PARSE ERROR: Undefined("Command(\"gcd\")")] (b, r) (a = b q + r)

[PARSE ERROR: Undefined("Command(\"boxed\")")] a x + b y = c が整数解を持つ ⟺ [PARSE ERROR: Undefined("Command(\"gcd\")")] (a, b) ∣ c

一言ひとことでいうと

互除法ごじょほうは、最大公約数さいだいこうやくすうを求もとめるだけでなく、mod 演算えんざんの逆元ぎゃくげんや一次いちじ不定方程式ふていほうていしきの解かいまで支ささえる中心的ちゅうしんてきな道具どうぐです。