法と互いに素である整数を乗じて剰余を取る話

2017年07月03日(月)  List  Edit  New

命題
$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$である。(証明終わり)

※以下で使います。

フェルマーの小定理
https://story.hyuki.net/20170703004709/

オイラーの定理
https://story.hyuki.net/20170703010126/

参照:第200回 からみあう素数(後編)
http://bit.ly/girlnote200