原始乗根の和

背理法を用いて示す。
仮に$\exists j\in [n],\exists i\in [n]-\{j\}s.t. ki\equiv ki\quad (mod\ n)$が成り立つとする。
左辺に移行して$k(i-j)\equiv 0\quad(mod\ n)$
このとき、仮定より$\gcd{(k,n)}=1$であるから$i-j\equiv 0\quad(mod\ n)$を得る。
しかし、これは仮定に反する。
ゆえに、与えられた補題は証明された。

[0]$\omega$が原始$n$乗根であるとすると、$\omega^{n}-1=(\omega-1)(\omega^{n-1}+\omega^{n-2}+\cdots \omega+1)=0$より、
\begin{equation} \omega^{n-1}+\omega^{n-2}+\cdots \omega+1=0 \end{equation}
以下$\omega=e^{i\frac{2\pi}{n}}$とする。
[1]$n=p\in\mathbb{P}$の場合は$Primitive=\{\omega,\omega^{2},...,\omega^{n-1}\}$かつ$q=1$の場合のみを考えればいい事が分かる。
ゆえに、下記の式を得る。
\begin{eqnarray} \sum_{\omega\in Primitive}\omega^{q}&=&(\omega^{n-1}+\omega^{n-2}+\cdots+\omega+1)-1\\ &=&-1 \end{eqnarray}
[2]$n=p^{2}$の場合は$Primitive=\{\omega^{1},\omega^{2},...,\omega^{n-1}\}-\{\omega^{p},\omega^{2p},...,\omega^{(p-1)p}\}$。
今の場合は次の二つの場合分けが必要：
(1)$\mathbb{N}\ni q\lt p$の場合：補題1より$\{q1\ (mod\ p),q2\ (mod\ p),...,q(p-1)\ (mod\ p)\}=\{1,2,...,p-1\}$が成り立つ。
これを用いれば下記の式が成り立つ。
\begin{eqnarray} \sum_{\omega\in Primitive}\omega^{q}&=&(\omega^{n-1}+\omega^{n-2}+\cdots+\omega)\\ &-&(\omega^{p(p-1)}+\omega^{{p}(p-2)}+\cdots+\omega^{p})\\ &=&(\omega^{n-1}+\omega^{n-2}+\cdots+\omega+1)\\ &-&(\omega^{p(p-1)}+\omega^{{p}(p-2)}+\cdots+\omega^{p}+1)\\ &=&0 \end{eqnarray}
(2)$q=p$の場合は次式が成り立つ。
\begin{eqnarray} \sum_{\omega\in Primitive}\omega^{q}&=&\sum_{k=1}^{n}\omega^{kp}-(\omega^{p^{2}}+\omega^{2p^{2}}+\cdots +\omega^{(p-1)p^{2}}+1)\\ &=&-p \end{eqnarray}
[3]$n=pq$の場合は$Primitive=\{\omega,\omega^{2},...,\omega^{n-1}\}-\{\omega^{p},\omega^{2p},...,\omega^{(q-1)p}\}-\{\omega^{q},\omega^{2q},...,\omega^{(p-1)q}\}$。
この場合は、$q=1$の場合のみ考えればいい。
\begin{eqnarray} \sum_{\omega\in Primitive}\omega^{q}&=&\sum_{k=1}^{n}\omega^{k}-\sum_{k=1}^{q}\omega^{kp}-\sum_{k=1}^{p}\omega^{kq}+1\\ &=&1 \end{eqnarray}
[4]$n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}$の場合は
\begin{eqnarray} \left\{ \begin{array}{l} S_{0}(\omega)=\{\omega^{r}|r=1,2,...,n-1\}\\ S_{m}(\omega)=\{\omega^{p_{k_{1}}p_{k_{2}}\cdots p_{k_{m}}r}|k_{1}\lt k_{2}\lt \cdots \lt k_{m},k_{1},k_{2},...,k_{m}\in\{1,2,...,k\},r=1,2,...,\frac{n}{p_{k_{1}}p_{k_{2}}\cdots p_{k_{m}}}-1\} \end{array} \right. \end{eqnarray}
今の場合、$Primitive=S_{0}(\omega)-S_{1}(\omega)$。
この場合は次の二つの場合で場合分けが必要。
(1)$q\lt\frac{n}{p_{1}p_{2}\cdots p_{k}}=p_{1}^{e_{1}-1}p_{2}^{e_{2}-1}\cdots p_{k}^{e_{k}-1}$の場合
$\gcd{(q,n)}=1$の場合は補題を、$\gcd{(q,n)}=d\neq 1$の場合は$\Omega=\omega^{q}$が原始$\frac{n}{d}$乗根になる事を用いればいい。
\begin{eqnarray} \sum_{\omega\in Primitive}\omega^{q}&=&\sum_{m=0}^{k}(-1)^{k}\begin{pmatrix}k\\m\end{pmatrix}\sum_{\omega\in S_{m}(\omega^{q})}\omega^{q}\\ &=&\sum_{m=0}^{k}(-1)^{k}\begin{pmatrix}k\\m\end{pmatrix}(\sum_{\Omega\in S_{m}(\omega^{q})}\Omega+1-1)\\ &=&-\sum_{m=0}^{k}\sum_{m=0}^{k}(-1)^{k}\begin{pmatrix}k\\m\end{pmatrix}\\ &=&-(1-1)^{k}\\ &=&0 \end{eqnarray}
(2)$q=\frac{n}{p_{1}p_{2}\cdots p_{k}}=p_{1}^{e_{1}-1}p_{2}^{e_{2}-1}\cdots p_{k}^{e_{k}-1}$の場合
\begin{eqnarray} \sum_{\omega\in Primitive}\omega^{q}&=&\sum_{m=0}^{k}(-1)^{k}\begin{pmatrix}k\\m\end{pmatrix}\sum_{\omega\in S_{m}(\omega^{q})}\omega^{q}\\ &=&\sum_{m=0}^{k}(-1)^{k}\begin{pmatrix}k\\m\end{pmatrix}\sum_{\Omega\in S_{m}(\omega^{q})}\Omega\\ &=&\sum_{m=0}^{k-1}(-1)^{k}\begin{pmatrix}k\\m\end{pmatrix}\sum_{\Omega\in S_{m}(\omega^{q})}\Omega+(-1)^{k}\sum_{\Omega\in S_{k}(\omega^{q})}\Omega\\ &=&\frac{(-1)^{k}n}{p_{1}p_{2}\cdots p_{k}} \end{eqnarray}