tex記法のテスト。
割られる数を、割る数を
とする（
）。
商を、余りを
とする（
）。
また、としておく。
このとき、
…(1)
であり、
である。また、、
に対し、
、
はただ一つ定まる。
、
の共通の約数のうち最大のものを最大公約数と呼び、
であらわす。なお、となるような2数は「互いに素である」と言う。
との関係で
、
を以下のように書きなおす。
同様に、として、
の別の表現
を得、を以下のように書きなおす。
今得た表現を式(1)に代入すると、
となる。よって、は
の約数である。また、
は
の約数でもあったので、結局
は
と
の公約数でもあることがわかった。
と
の最大公約数は
であったので、以下の関係を得る。
…(2)
ここで式(1)を変形し、
さらに、
を代入すると、
となる。よって、は
の約数である。
は
の約数でもあったので、
は
と
の公約数である。
と
の最大公約数は
であったので、以下の関係を得る。
…(3)
ここで(2)と(3)を比べると、結局
であることがわかる。すなわち、
であり、文章で表現すると、「2数、
の最大公約数は、
を
で割った余り
と
の最大公約数に等しい」ということである。
またここで今の、
を新たな
、
として同様の手順を繰り返すこともできる。
、
をスタートにして繰り返してみよう。
（
）
（
）
（
）
（中略）
（
）
この時、余りは正の整数であり、一つ前のステップの余りより必ず小さくなるため、有限回の繰り返しで0になり、繰り返しが終了するというのが重要である。
であるので（全ての数は0の約数である）、
である。
実際の手順としては、
（中略）
と、余りが0になるまで割り算を繰り返す（剰余を求る）ことで最大公約数を求めることができる。
これをユークリッドの互除法と呼ぶ。
