  |
(i) a と b1, a と b2 とが互いに素であるとき、a と b1b2 も互いに素である。
a と b1b2 が互いに素でないとすると、a と b1b2 を割り切る素数 p が存在する。 b1b2 が p で割り切れるとき、b1 か b2 が p で割り切れることになるが、これは a と b1、 a と b2 が互いに素であることと矛盾する。
(ii) a と b が互いに素であるとき、a, 2a, 3a ... (b - 1)a を b で割った余りは互いに異なる。
ia, ja (i ＜ j) を b で割った結果が同じになるとすると、(j - i)a は b と倍数になるが、 (j - i) ＜ b であるので、これは矛盾。
(i) より、m と nm(j) は互いに素
9
