ユークリッドの互除法(読み)ユークリッドのごじょほう(英語表記)Euclidean algorithm

精選版 日本国語大辞典 「ユークリッドの互除法」の意味・読み・例文・類語

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

二つ整数最大公約数を求める方法一つユークリッドの「幾何学原本」に記載されているもの。互除法

出典 精選版 日本国語大辞典精選版 日本国語大辞典について 情報

デジタル大辞泉 「ユークリッドの互除法」の意味・読み・例文・類語

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

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

出典 小学館デジタル大辞泉について 情報 | 凡例

ブリタニカ国際大百科事典 小項目事典 「ユークリッドの互除法」の意味・わかりやすい解説

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

二つの自然数 a1a2の最大公約数(→約数)を求めるための一つの方法。a1a2として,次の割り算を実行する。

a1a2q1a3 q1は商,a3余り
a2a3q2a4 q2は商,a4は余り
………… …………
an-1anqn-1an+1 qn-1は商,an+1は余り
anan+1qn qnは商,余りはなし


最後に余りがなかったならば,この an+1最初の 2数 a1a2の最大公約数である。(→整数論ユークリッド

出典 ブリタニカ国際大百科事典 小項目事典ブリタニカ国際大百科事典 小項目事典について 情報

改訂新版 世界大百科事典 「ユークリッドの互除法」の意味・わかりやすい解説

ユークリッドの互除法 (ユークリッドのごじょほう)
Euclidean algorithm

二つの自然数の最大公約数を見つける方法。二つの自然数abが与えられているとする。abとして,abで割ったときの余りをa1とする。ba1で割り,その余りをb1とおく。b1a1を割り,余りをa2とする。このようにして,aba1b1a2b2>……となる整数の列が定まっていくが,どこかで0になる。そのすぐ前の自然数がabの最大公約数である。例えば,a=63,b=49ならば,a=63,b=49,a1=14,b1=7,a2=0となり7が最大公約数である(図1)。この方法は1変数の多項式にも有効である。1変数の多項式の大きさを次数で比べて,割って余りを取る方法を繰り返せばよい。例えばfx4x3x+1,g=2x3+5x2+4x+1の場合g1=0となり,最大公約式はx2+2x+1である(図2)。この方法は《ストイケイア》に書かれているので,ユークリッドの互除法といわれるようになった。
執筆者:


出典 株式会社平凡社「改訂新版 世界大百科事典」改訂新版 世界大百科事典について 情報

日本大百科全書(ニッポニカ) 「ユークリッドの互除法」の意味・わかりやすい解説

ユークリッドの互除法
ゆーくりっどのごじょほう

最大公約数を求める方法。a1、a2を自然数あるいは整式とする。自然数のときは、a1≧a2で、整式のときは、a1の次数のほうがa2の次数以上であるとする。

  a1=a2q1+a3 (a3は剰余)
  a2=a3q2+a4 (a4は剰余)
    …………
  an-1=anqn-1+an+1
         (an+1は剰余)
  an=an+1qn
となるとき、an+1がa1とa2の最大公約数である。an+1=1のときは、a1とa2は互いに素である。3553と2584の最大公約数は323であるが、これは次のようにして求める。

  3553=2584×1+969
  2584=969×2+646
  969=646×1+323
  646=323×2
[寺田文行]

出典 小学館 日本大百科全書(ニッポニカ)日本大百科全書(ニッポニカ)について 情報 | 凡例

ASCII.jpデジタル用語辞典 「ユークリッドの互除法」の解説

ユークリッドの互除法

自然数の最大公約数を効率よく求める方法。世界で最初のアルゴリズムといわれている。

出典 ASCII.jpデジタル用語辞典ASCII.jpデジタル用語辞典について 情報

今日のキーワード

青天の霹靂

《陸游「九月四日鶏未鳴起作」から。晴れ渡った空に突然起こる雷の意》急に起きる変動・大事件。また、突然うけた衝撃。[補説]「晴天の霹靂」と書くのは誤り。[類語]突発的・発作的・反射的・突然・ひょっこり・...

青天の霹靂の用語解説を読む

コトバンク for iPhone

コトバンク for Android