|
ユークリッドの互除法（ユークリッドのごじょほう、）は、2 つの自然数または整式の最大公約数を求める手法の一つである。 2 つの自然数（または整式） ''a'', ''b'' (''a'' ≧ ''b'') について、''a'' の ''b'' による剰余を ''r'' とすると、 ''a'' と ''b'' との最大公約数は ''b'' と ''r'' との最大公約数に等しいという性質が成り立つ。この性質を利用して、 ''b'' を ''r'' で割った剰余、 除数 ''r'' をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が ''a'' と ''b'' との最大公約数となる。 明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである。 == 例 == (問題) 1071 と 1029 の最大公約数を求める。 *1071 を 1029 で割った余りは 42 *1029 を 42 で割った余りは 21 *42 を 21 で割った余りは 0 よって、最大公約数は21である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ユークリッドの互除法」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Euclidean algorithm 」があります。 スポンサード リンク
|