ｒはｎをｍで割った余りであるので、ｎはｍ、ｒそしてその商ｑを用いて次のように書ける。
ｎ＝ｍｑ＋ｒ …(１)
今、ｎとｍの最大公約数をｐとしよう。
そうすると、ｎ、ｍはｐおよび、正の整数ａ，ｂを用いて次のように書ける。
ｎ＝ａｐ
ｍ＝ｂｐ
これを使うと、(１)は次のように書きなおせる。
ａｐ＝ｂｑｐ＋ｒ …(２)
(２)は次のように変形できる。
ａ―ｂｑ＝ｒ／ｐ …(３)
ここで、(３)の左辺は、整数であるから、(３)の右辺も整数でなければならない。すなわち、ｒはｐを因数に持つ。（つまり、ｒ＝ｃｐという形で書ける。）よって題意は示された。
