互除法とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > デジタル大辞泉 > 互除法の意味・解説 

ごじょ‐ほう〔ゴヂヨハフ〕【互除法】

読み方:ごじょほう

ユークリッドの互除法


ユークリッドの互除法

(互除法 から転送)

出典: フリー百科事典『ウィキペディア(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) をもつことが分かる。


一般に、


「互除法」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


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

辞書ショートカット

すべての辞書の索引

「互除法」の関連用語











互除法のお隣キーワード
検索ランキング

   

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



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

   
デジタル大辞泉デジタル大辞泉
(C)Shogakukan Inc.
株式会社 小学館
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのユークリッドの互除法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS