の最大公約数をと置く. このとき, 素数がの約数だとすると次が成立する.
はの約数ではない.
がでないなら, はの約数ではない.
がの約数であり, の約数でもあるとすれば, は互いに素だから, はを割り切らない. すると, はも割り切らないのでを割り切らない. これはがの約数であり, の約数でもあることに反する.
がではなく, の約数だとすると, は互いに素だから, はの約数ではない. すると, はを割り切らないから, はの約数ではないことになるが, これはがの約数であり, の約数であることに反する.
がを何回割り切るかを考える.
のとき, はのいずれも割り切らないから, の共通因数であり, この差も割り切るはずだが, はもも割り切らないから, を割り切るはずで, でなければならず, しかも高々回しかを割り切らない.
次に, かのいずれかがで割り切れないことを示す. 今, は互いに素だから, のいずれかがで割り切れないときにがで割り切れないことが言えれば十分. のいずれかがの倍数のとき, もう一方は3の倍数ではなく, かは3では割り切れない. いずれもの倍数でないとき, は互いに素で, で割った余りを考えれば, を考えれば十分. 考えられる全てのの組は,であるが, いずれの場合もはでは割り切れないので,はで高々回しか割り切れない.
のとき, が奇数だとすると, も奇数だから, はで割り切れない. 次に, が偶数だとすると, は奇数であり, はで回以上割り切れるが, はでちょうど回だけ割り切れるから, はで高々回しか割り切れない.
以上により, は高々で回, で回しか割り切れないので, はの約数である.