a-bq と b がともに整数 c の倍数とする。
つまり， a-bq=cm,  b=cn なる整数 m, n が存在する。
すると，a= bq+cm = cnq+cm = c(m+nq)
となり a も c の倍数である。
したがって，a-bq と b が1より大きい公約数をもつならば， a と b も1より大きい公約数をもつ。

逆に， a, b がともに c の倍数であるならば， a-bq も c の倍数である。

よって，証明された。