とおくとはとの公倍数なので
とおける。
次にととの積は、の倍数、かつの倍数なので、との公倍数。よって
とおける。
式()を式()に代入して、
この式から
を得る。これらの式からがとの約数であることが分かる。よってはとの公約数。二つ以上の整数の公約数はそれらの整数の最大公約数の約数なので、とすると
とおける。
はで割り切れるので、はで割り切れる。同様にもで割り切れる。よって
を得る。これらの式を式()に代入して
を得る。
と仮定するとはとの公倍数となるが、となりの最小性に矛盾。
よって
を得る。つまり、つまり式()から
を得る。
つぎに両辺にを掛けて
を得る。
ここで、最大公約数と最小公倍数は
という性質を持つので、
から
ゆえに、
を得て、公式が示された。