ユークリッドの互除法

ユークリッドの互除法（-ごじょほう）は、2つの自然数または整式の最大公約数を求める手法の一つである。2つの自然数（または整式）a、bについて、aのbによる剰余をrとすると、aとbとの最大公約数はbとrとの最大公約数に等しいが、この性質に基き、bのrによる剰余を求め、rをさらにbのrによる剰余で割った剰余を求め、と同様の手続きを繰り返すと、剰余が0になった時の除数がすなわちaとbとの最大公約数である、というもの。明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第7巻、命題1から3がそれである。