Rakuten infoseek

辞書

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

デジタル大辞泉

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

出典:小学館
監修:松村明
編集委員:池上秋彦、金田弘、杉崎一雄、鈴木丹士郎、中嶋尚、林巨樹、飛田良文
編集協力:田中牧郎、曽根脩
(C)Shogakukan Inc.
それぞれの用語は執筆時点での最新のもので、常に最新の内容であることを保証するものではありません。

世界大百科事典 第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)。

出典:株式会社平凡社
Copyright (c) Heibonsha Limited, Publishers, Tokyo. All rights reserved.

大辞林 第三版

ユークリッドのごじょほう【ユークリッドの互除法】
二つの自然数または整式 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 の最大公約数。互除法。

出典:三省堂
(C) Sanseido Co.,Ltd. 編者:松村明 編 発行者:株式会社 三省堂 ※ 書籍版『大辞林第三版』の図表・付録は収録させておりません。 ※ それぞれの用語は執筆時点での最新のもので、常に最新の内容であることを保証するものではありません。

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

ユークリッドの互除法
ユークリッドのごじょほう
Euclidean algorithm
二つの自然数 a1a2の最大公約数(→約数)を求めるための一つの方法。a1a2として,次の割り算を実行する。

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


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

出典:ブリタニカ国際大百科事典 小項目事典
Copyright (c) 2014 Britannica Japan Co., Ltd. All rights reserved.
それぞれの記述は執筆時点でのもので、常に最新の内容であることを保証するものではありません。

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

ユークリッドの互除法
ゆーくりっどのごじょほう
最大公約数を求める方法。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[寺田文行]

出典:小学館 日本大百科全書(ニッポニカ)
(C)Shogakukan Inc.
それぞれの解説は執筆時点のもので、常に最新の内容であることを保証するものではありません。

精選版 日本国語大辞典

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

出典:精選版 日本国語大辞典
(C)Shogakukan Inc.
それぞれの用語は執筆時点での最新のもので、常に最新の内容であることを保証するものではありません。

ユークリッドの互除法」の用語解説はコトバンクが提供しています。

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

他サービスで検索

(C)The Asahi Shimbun Company /VOYAGE MARKETING, Inc. All rights reserved.
No reproduction or republication without written permission.