rはnをmで割った余りであるので、nはm、rそしてその商qを用いて次のように書ける。
n=mq+r …(1)
今、nとmの最大公約数をpとしよう。
そうすると、n、mはpおよび、正の整数a,bを用いて次のように書ける。
n=ap
m=bp
これを使うと、(1)は次のように書きなおせる。
ap=bqp+r …(2)
(2)は次のように変形できる。
a―bq=r/p …(3)
ここで、(3)の左辺は、整数であるから、(3)の右辺も整数でなければならない。すなわち、rはpを因数に持つ。(つまり、r=cpという形で書ける。)よって題意は示された。