整数が整数を割り切るとは、となる整数が存在することです。このときと書き、をの約数、をの倍数と呼びます。ですが（）、です（が整数にならない）。
1 除法の原理：商と余りはただ一通り
割り切れないときも、商と余りを使えば必ず整数どうしの関係に書き直せます。
整数と正の整数に対して、、を満たす整数がただ一組だけ存在します。 これを除法の原理と呼び、を「をで割った余り」と言います。存在することは、からを引けるだけ引いていけばの範囲に必ず落ち着くことから分かり、一意性は、もし2通りの表し方があったとすると差を取っての倍数どうしの差が未満になり矛盾する、という議論から出ます。
2 最大公約数と互除法
2つの整数（少なくとも一方はでない）に共通する約数のうち最大のものを最大公約数と呼び、と書きます。
素朴には両方を素因数分解して共通部分を取ればよいのですが、大きな数では素因数分解自体が重い作業です。もっと速い方法があります。ををで割った余りとすると、
が成り立ちます。これがユークリッドの互除法です。成り立つ理由は難しくありません。なので、がとの両方を割り切るならも割り切りますし、逆にがとの両方を割り切るならも割り切ります。つまり「の公約数の集合」と「の公約数の集合」はぴったり一致するので、最大値も当然一致するわけです。
この置き換えを、余りがになるまで繰り返すだけで最大公約数が求まります。を計算してみます。
余りがになった時点の割る数が答えなので、です。
素因数分解しようとすると、と手間がかかりますが、互除法なら3回の割り算で終わります。素因数分解を経由しないというのが互除法の最大の強みで、数百桁の数でも一瞬で最大公約数が求まる理由はここにあります。
閑話休題：現役最古のアルゴリズム ユークリッドの互除法は、名前の通りユークリッドの『原論』（紀元前300年頃）第7巻に載っている手続きです。計算機科学者ドナルド・クヌースは著書『The Art of Computer Programming』で、これを「今なお使われている最古の非自明なアルゴリズム」と呼びました。 2300年前に書かれた手順が、今日も皆さんの電卓やコンピュータの中で（分数の約分から暗号処理まで）現役で動き続けているのです。
では、この手順は最悪どれくらい時間がかかるのでしょうか。1844年、フランスの数学者ガブリエル・ラメは「互除法のステップ数が最も多くなるのは、隣り合うフィボナッチ数の組を入力したときである」ことを証明しました。これは、ある具体的なアルゴリズムの実行時間を数学的に解析した最初期の成果とされ、しばしば「アルゴリズム解析という分野の誕生」の一つに数えられます。直感的にも納得できる話で、フィボナッチ数列は隣り合う項の商がすべて（余り、余り、…）になるため、商が大きく余りが一気に縮む「速い」ケースとは正反対に、毎回わずかしか縮まない「一番ゆっくり進む」最悪ケースになるわけです。