ユークリッドの互除法とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > デジタル大辞泉 > ユークリッドの互除法の意味・解説 

ユークリッド‐の‐ごじょほう〔‐ゴヂヨハフ〕【ユークリッドの互除法】

読み方:ゆーくりっどのごじょほう

二つ整数最大公約数求め算法大きい方の数を小さい方の数で割り、その剰余小さい方の数を割る演算繰り返す最後に残る除数求め最大公約数となる。二つ整式についても成り立つ。ユークリッド著書ストイケイア」に記載互除法


ユークリッドの互除法

「A を B で割ったときの余りを R とすると、A, B 2数の最大公約数は、B, R の最大公約数等しい」という性質をを利用して、2数の最大公約数を、より小さな2数の最大公約数求めることに置き換える方法をいう。


ユークリッドの互除法

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/01/28 04:37 UTC 版)

252と105のためのユークリッドの互除法のアニメーション。
クロスバーは、最大公約数(GCD)である21の倍数を表す。
それぞれのステップにおいて、1つの番号がゼロになるまで、より少ない数はより大きな数から引かれる。
残りの数は、GCD。

ユークリッドの互除法(ユークリッドのごじょほう、: Euclidean Algorithm)は、2 つの自然数最大公約数を求める手法の一つである。

2 つの自然数 a, b (ab) について、ab による剰余r とすると、 ab との最大公約数は br との最大公約数に等しいという性質が成り立つ。この性質を利用して、 br で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が ab との最大公約数となる。

明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである[注釈 1]

(問題) 1071 と 1029 の最大公約数を求める。

  • 1071 を 1029 で割った余りは 42
  • 1029 を 42 で割った余りは 21
  • 42 を 21 で割った余りは 0

よって、最大公約数は21である。

証明

a, b は自然数で a ≠ 0 とする。 ba で割った商を q、剰余を r とすると

b = qa + r

今、d0ar の両方を割り切る自然数とする。

このとき d0 は積 qa を割り切るから、和 qa + r も割り切るが、qa + rb に等しい。したがって、d0ab を割り切る。すなわち ar公約数はすべてbaの公約数である。

逆に、d1ba の両方を割り切る自然数とする。

d1qa を割り切るから差 b - qa を割り切るが、b - qar に等しい。したがって、d1arを割り切る。言い換えると ba の公約数はすべてar の公約数である。

したがって、ba の公約数全体の集合は ar の公約数全体の集合に等しく、特に ba の最大公約数は ar の最大公約数でなければならない。

手続き的記述

ユークリッドの互除法の仕組みは、この図のように最大公約数を求める対象の2つの整数を幅と高さに設定した長方形内での赤色の斜めの直線の描画過程によっても表現できる。 赤色の斜めの直線の描画は、はじめはその長方形内を描画範囲とし、その角から内部に向け、かつ、その辺に対して45度の差を持たせて開始する。 描画範囲の辺の途中に当たれば、その内部へ直角反射するように角度を変える。 赤色の斜めの直線が反射後に描画範囲の向かいの辺と異なる辺の途中に当たる場合、描画範囲の長辺の長さを短辺の長さで割ると余りが生じる状態となっており、直前の反射地点を足掛かりに描画範囲を垂直に区切ってその範囲を絞りこむ。 (区切られて出来た小さいほうの範囲を以後の描画範囲とする) (除数および被除数の変更に相当) 赤色の斜めの直線が描画範囲の角に到達した場合、描画範囲の長辺の長さを短辺の長さで余りなく割れる状態となっており、描画の終了となり、最後にして最小の描画範囲の短辺の長さが最大公約数となる。

手続き的に記述すると、次のようになる。

  1. 入力を m, n (mn) とする。
  2. n = 0 なら、 m を出力してアルゴリズムを終了する。
  3. mn で割った余りを新たに n とし、更に 元のnを新たにm とし 2. に戻る。

上記の手順は「n, m に対して剰余の演算を行うことができる」という仮定だけに依っているので、整数環だけではなく任意のユークリッド整域においても同様にして最大公約因子を求めることができる。

拡張された互除法

整数 m, n の最大公約数 (: Greatest Common Divisor) を gcd(m,n) と表すときに、(拡張された)ユークリッドの互除法を用いて、mx + ny = gcd(m, n) の解となる整数 x, y の組を見つけることができる。上の例の場合、m = 1071, n = 1029 のとき、

1071 = 1 × 1029 + 42
1029 = 24 × 42 + 21
42 = 2 × 21

であるから、gcd(1071, 1029) = 21 であり、

21 = 1029 − 24 × 42 
= 1029 − 24 × (1071 − 1 × 1029)
= −24 × 1071 + 25 × 1029

となるので、x = −24, y = 25 である。

特に、m, n互いに素(最大公約数が 1)である場合、mx + ny = 1 の整数解を (x, y) とすると、mx + ny = c は任意の整数 c に対して整数解 (cx, cy) をもつことが分かる。


一般に、


ユークリッドの互除法

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2018/10/03 20:59 UTC 版)

Guarded Command Language」の記事における「ユークリッドの互除法」の解説

a , b := A , B ; {\displaystyle a,b:=A,B;} do {\displaystyle {\mbox{do}}} a > b → a := a − b {\displaystyle a>b\rightarrow a:=a-b} [ ]   b > a → b := b − a {\displaystyle []\ b>a\rightarrow b:=b-a} od {\displaystyle {\mbox{od}}} この繰り返しは a = b のとき終了しその際に a と b には A と B の最大公約数格納されている。

※この「ユークリッドの互除法」の解説は、「Guarded Command Language」の解説の一部です。
「ユークリッドの互除法」を含む「Guarded Command Language」の記事については、「Guarded Command Language」の概要を参照ください。

ウィキペディア小見出し辞書の「ユークリッドの互除法」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「ユークリッドの互除法」の関連用語

ユークリッドの互除法のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



ユークリッドの互除法のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
デジタル大辞泉デジタル大辞泉
(C)Shogakukan Inc.
株式会社 小学館
数理検定協会数理検定協会
Copyright©2025 数理検定協会 All Rights Reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのユークリッドの互除法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、WikipediaのGuarded Command Language (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS