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

デジタル大辞泉の解説

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

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

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

世界大百科事典 第2版の解説

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

二つの自然数の最大公約数を見つける方法。二つの自然数a,bが与えられているとする。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)。

出典 株式会社平凡社世界大百科事典 第2版について 情報

大辞林 第三版の解説

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

二つの自然数または整式 a 1, a 2 の最大公約数を求める手続き。a 1 a 2 で割った余りを a 3 とする。順次 a n a n +1 で割った余りを a n +2 とする。a k =0 となったとき、a k -1 a 1 a 2 の最大公約数。互除法。

出典 三省堂大辞林 第三版について 情報

ブリタニカ国際大百科事典 小項目事典の解説

ユークリッドの互除法
ユークリッドのごじょほう
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の最大公約数である。(→整数論ユークリッド

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

日本大百科全書(ニッポニカ)の解説

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

最大公約数を求める方法。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[寺田文行]

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

関連語をあわせて調べる

今日のキーワード

トランスジェンダー

性別違和をもつ人々の総称。性別違和とは,体の性的特徴,出生時の体に基づいて判別された性別や,その役割に課される性役割,性別表現など,すなわちジェンダーへの違和感である。トランスジェンダーには,他方の性...

続きを読む

コトバンク for iPhone

コトバンク for Android

ユークリッドの互除法の関連情報