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