自然数 n 以下で 1 以上の自然数全てに n 未満で n と互いに素な自然数をかけてできる数たちは、n を法とすると、0, 1, 2, 3, ・・・, n−1 のどれかの数で表わすことができます。
　これは、時計で12時から初めて時計回りに7 つずつ進みながら数字をピックアップしたときに 、7 → 2 → 9 → 4 → 11 → 6 → 1 → 8 → 3 → 10 → 5 → 12　と全ての数字をピックアップしていくことができることからも納得がいくことと思います。
　この証明は、次の剰余数に関する定理 と 背理法を用います。




（ 証 明 ）

　全体集合を自然数とする。
　Ｐ と Ｒ は ｂ 未満の異なる数で、ａ と ｂ が互いに素であるとき、
ａＰ ≡ ａＲ　( mod ｂ )　であると仮定すると、
上記の剰余数に関する定理より、 Ｐ ≡ Ｒ　( mod ｂ )　となる。
これは、Ｐ と Ｒ は ｂ 未満の異なる数であることと矛盾する。
したがって、ａＰ ≡ ａＲ　( mod ｂ )　ということはない。

　　　　　　　　　　※ 参考：　数理論 ＞ 剰余数の性質 の (11)