コトバンクはYahoo!辞書と技術提携しています。

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

6件 の用語解説(ユークリッドの互除法の意味・用語解説を検索)

ASCII.jpデジタル用語辞典の解説

ユークリッドの互除法

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

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

デジタル大辞泉の解説

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

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

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

世界大百科事典 第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 na 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[寺田文行]

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

今日のキーワード

稀勢の里寛

1986- 平成時代の力士。昭和61年7月3日生まれ。中学卒で鳴戸部屋に入門し,平成14年3月初土俵。16年5月新十両,同年11月には18歳4ヵ月で新入幕をはたす。18年7月新三役小結,21年3月新関...

続きを読む

コトバンク for iPhone

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