プログラムでは、検索とか並べ替えとかよく出てくる問題があって、それらはに定番のアルゴリズムがあります。ですから、プログラマーはすべてのアルゴリズムを自分で考えるわけではありません。既に知られているアルゴリズムはどんどん使って、さらに複雑な作業を実現するのです。つまりアルゴリズムは人類が共有する知的財産なのです。
　ユークリッドの互除法は、２つの自然数 a、b の最大公約数を求める方法です。最大公約数を求めるには２数をそれぞれ素因数分解して共通の素因数を見つけると中学校で教えられます。でも、素因数分解って面倒ですよね。結構カンが必要だったりしますから。
　ユークリッドの方法は a、b（aの方が大）に関して、a を b で割った剰余（余り）を r とすると、a と b の最大公約数は b と r の最大公約数になるという性質を使います。つまり a÷b の剰余を r₁、b÷r₁の剰余を÷r₂、r₁÷r₂の剰余をr₃というように繰り返し、剰余が0になったら除数が最大公約数になります。例えば、195 と 143 で考えてみましょう。

　・195 ÷ 143 = 1 … 52

　・143 ÷  52 = 2 … 39

　・ 52 ÷  39 = 1 … 13

　・ 39 ÷  13 = 3 …  0