\(p\)を素数とし、\(X\)を\(p\)未満の正整数全体の集合、すなわち、 \[ X = \{1,2,\ldots,p-1\} \] とする。\(p\)と互いに素である任意の整数\(n\)に対して、集合\(X_n\)を、 \[ X_n = \{\,nx\bmod p \,|\, x \in X\,\} \] と定義したとき、 \[ X_n = X \] が成り立つ。
\(p = 3\)としたとき、\(X = \{1,2\}\)である。\(p\)と互いに素である整数の例として\(n = 1,2,4,5,7\)を考えると、以下に示す通り\(X_n = X\)が成り立っている。 \[ \begin{align*} X_1 &= \{ 1\cdot1 \bmod 3, 1\cdot2 \bmod 3 \} = \{1, 2 \} = X \\ X_2 &= \{ 2\cdot1 \bmod 3, 2\cdot2 \bmod 3 \} = \{2, 1 \} = X \\ X_4 &= \{ 4\cdot1 \bmod 3, 4\cdot2 \bmod 3 \} = \{1, 2 \} = X \\ X_5 &= \{ 5\cdot1 \bmod 3, 5\cdot2 \bmod 3 \} = \{2, 1 \} = X \\ X_7 &= \{ 7\cdot1 \bmod 3, 7\cdot2 \bmod 3 \} = \{1, 2 \} = X \\ \end{align*} \]
\(X \supset X_n\)であるから、あとは\(X \subset X_n\)を示せばいい。そのためには、\(X\)から\(X_n\)への写像\(f:x \mapsto nx \bmod p\)が単射であることを示せばいい。\(X\)の二要素\(x,x'\)に対して、 \[ f(x) = f(x') \] とすると、 \[ nx \equiv nx' \pmod p \] である。\(p\)と\(n\)は互いに素なので、 \[ x \equiv x' \pmod p \] が成り立つ。\(x,x'\)はいずれも\(p\)未満の非負整数であるから\(x = x'\)がいえ、\(f\)は単射である。したがって\(X_n = X\)である。（証明終わり）
※以下で使います。
