公約数というのは、共通の約数のことです。
そして、約数とはその整数を割りきることの出来る数です。
ですから、ですから（１８，１２）の公約数は、
１８も１２も割り切ることの出来る数のことです。
１，２，３，６
が公約数です。
そして、最大の公約数（今の例では６）のことを最大公約数というのです。
ユークリッド互除法では次のようにして最大公約数を求めます。
例えば、（４８，６６）の最大公約数は、
６６を４８で割り余りを求めます。
余りは１８です。
次に、４８を１８で割った余りを求めます。
４８を１８で割った余りは、１２です。
次に１８を１２で割った余りを求めます。
それは６です。
次に１２を６で割った余りを求めますが、余りは０です。
この余りを０にする割る数６が最大公約数というわけです。
つまり、（ａ，ｂ）の最大公約数を求めるには、
大きい方を小さい方で割ります。
そして、余りが０でない場合は、今割った割る数を余りで割ります。
そして、余りが０でないときはやはり今割った割る数（つまり一つ手前の余り）をその余りで求めます。
以降同じことを繰り返して、余りが０になるときの割る数が最大公約数というわけです。
６６÷４８＝１・・・１８
４８÷１８＝２・・・１２
１８÷１２＝１・・・６
１２÷６＝２ ・・・０
よって、（４８，６６）の最大公約数は６
割る数が割られる数になることを繰り返すので、
互除法です。
ユークリッド互除法は、
紀元前300年前に書かれた『ユークリッド原論』に記載されているそうです。
『ユークリッド原論』は、19世紀までは聖書の次ぎに読まれた世界のベストセラーです。
ではプログラミングに入る前に、
いくつか手計算で求め、
プログラムの神髄を掴んでください。
何度も述べてきましたが、
プログラムを組むために大切なことは、
自分が取り組む対象・事象の本質を掴むことです。
数独問題作成ソフトを作る場合には、数独を手で解いて数独の肝要な本質を把握する必要があります。
将棋ソフトなら、将棋を徹底的に指してどれがよい手で、どんな手が敗因になるのかを掴むことが必要です。
将棋の徹底研究なしに強い将棋ソフトは作れません。
（コンピュータ将棋選手権で優勝したことのあるBonanzaは、将棋の初心者が開発したそうですが、
これは例外です。基本的に、コンピュータ将棋選手権を制しているソフトを作っている人は将棋の上段者です。）
日産で最初にマイクロコンピュータによる自動車のエンジン自動制御を開発した人は、
車を愛し、自動車やそのエンジンの仕組みに精通していた人であるといいます。
エンジンの構造、燃焼の仕組みなどを知らずに、エネルギー効率のよい自動制御プログラムを組むことは出来ません。
燃費のよい制御プログラムを組むには、自動車のことをよく知っていなければならないのです。
プログラムを組む前に、事象の本質を研究して掴むことが必要です。
問題
これを参考にして次の組の最大公約数を求めて下さい。
① （３９６，１２６）
② （７２，１００）
③ （１８０，５８８）
