原始乗根の和

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

[0]$\omega$が原始$n$乗根であるとすると、${\omega }^n-1=(\omega -1)({\omega }^{n-1}+{\omega }^{n-2}+\cdots \omega +1)=0$より、
$${\omega }^{n-1}+{\omega }^{n-2}+\cdots \omega +1=0$$
以下$\omega =e^{i\frac{2\pi }{n}}$とする。
[1]$n=p\in \mathbb{P}$の場合は$Primitive=\{\omega ,{\omega }^2,...,{\omega }^{n-1}\}$かつ$q=1$の場合のみを考えればいい事が分かる。
ゆえに、下記の式を得る。
$$\begin{array}{rcl}\sum _{\omega \in Primitive}{\omega }^q& =& ({\omega }^{n-1}+{\omega }^{n-2}+\cdots +\omega +1)-1\\ & =& -1\end{array}$$
[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<p$の場合：補題1より$\{q1(modp),q2(modp),...,q(p-1)(modp)\}=\{1,2,...,p-1\}$が成り立つ。
これを用いれば下記の式が成り立つ。
$$\begin{array}{rcl}\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{array}$$
(2)$q=p$の場合は次式が成り立つ。
$$\begin{array}{rcl}\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{array}$$
[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{array}{rcl}\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{array}$$
[4]$n=p_1^{e_1}{p}_2^{e_2}\cdots p_k^{e_k}$の場合は
$$\begin{array}{r}\{\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<k_2<\cdots <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}\end{array}$$
今の場合、$Primitive=S_0(\omega )-S_1(\omega )$。
この場合は次の二つの場合で場合分けが必要。
(1)$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}$の場合
$gcd(q,n)=1$の場合は補題を、$gcd(q,n)=d\ne 1$の場合は$\mathrm{\Omega }={\omega }^q$が原始$\frac{n}{d}$乗根になる事を用いればいい。
$$\begin{array}{rcl}\sum _{\omega \in Primitive}{\omega }^q& =& \sum _{m=0}^k(-1{)}^k\left(\begin{array}{c}k\\ m\end{array}\right)\sum _{\omega \in S_m({\omega }^q)}{\omega }^q\\ & =& \sum _{m=0}^k(-1{)}^k\left(\begin{array}{c}k\\ m\end{array}\right)(\sum _{\mathrm{\Omega }\in S_m({\omega }^q)}\mathrm{\Omega }+1-1)\\ & =& -\sum _{m=0}^k\sum _{m=0}^k(-1{)}^k\left(\begin{array}{c}k\\ m\end{array}\right)\\ & =& -(1-1{)}^k\\ & =& 0\end{array}$$
(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{array}{rcl}\sum _{\omega \in Primitive}{\omega }^q& =& \sum _{m=0}^k(-1{)}^k\left(\begin{array}{c}k\\ m\end{array}\right)\sum _{\omega \in S_m({\omega }^q)}{\omega }^q\\ & =& \sum _{m=0}^k(-1{)}^k\left(\begin{array}{c}k\\ m\end{array}\right)\sum _{\mathrm{\Omega }\in S_m({\omega }^q)}\mathrm{\Omega }\\ & =& \sum _{m=0}^{k-1}(-1{)}^k\left(\begin{array}{c}k\\ m\end{array}\right)\sum _{\mathrm{\Omega }\in S_m({\omega }^q)}\mathrm{\Omega }+(-1{)}^k\sum _{\mathrm{\Omega }\in S_k({\omega }^q)}\mathrm{\Omega }\\ & =& \frac{(-1{)}^{k}n}{p_1{p}_2\cdots p_k}\end{array}$$