Sum of Powers of Primitive Complex Roots of Unity

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \Z_{>0}$ be a (strictly) positive integer.

Let $U_n$ denote the complex $n$th roots of unity:

$U_n = \set {z \in \C: z^n = 1}$

Let $\alpha = \exp \paren {\dfrac {2 k \pi i} n}$ denote a primitive complex $n$th root of unity.

Let $s \in \Z_{>0}$ be a (strictly) positive integer.


Then:

\(\ds \sum_{j \mathop = 0}^{n - 1} \alpha^{j s}\) \(=\) \(\ds 1 + \alpha^s + \alpha^{2 s} + \cdots + \alpha^{\paren {n - 1} s}\)
\(\ds \) \(=\) \(\ds \begin {cases} n & : n \divides s \\ 0 & : n \nmid s \end {cases}\)


where:

$n \divides s$ denotes that $n$ is a divisor of $s$
$n \nmid s$ denotes that $n$ is not a divisor of $s$.


Proof

First we address the case where $n \divides s$.

Then:

\(\ds s\) \(=\) \(\ds q n\) for some $q \in \Z_{>0}$
\(\ds \leadsto \ \ \) \(\ds \alpha^{j s}\) \(=\) \(\ds \alpha^{j q n}\)
\(\ds \) \(=\) \(\ds \paren {\alpha^n}^{j q}\)
\(\ds \) \(=\) \(\ds 1^{j q}\)
\(\ds \) \(=\) \(\ds 1\)


Hence:

\(\ds \sum_{j \mathop = 0}^{n - 1} \alpha^{j s}\) \(=\) \(\ds \sum_{j \mathop = 0}^{n - 1} 1\)
\(\ds \) \(=\) \(\ds n\)


Now let $n \nmid s$.

Then:

\(\ds s\) \(=\) \(\ds q n + r\) for $0 < r < 1$ \(\quad\) Division Theorem
\(\ds \leadsto \ \ \) \(\ds \alpha^s\) \(=\) \(\ds \alpha^{q n + r}\)
\(\ds \) \(=\) \(\ds \paren {\alpha^n}^q \alpha^r\)
\(\ds \) \(=\) \(\ds 1^q \alpha^r\)
\(\ds \) \(=\) \(\ds \alpha^r\)
\(\ds \) \(\ne\) \(\ds 1\)


Hence:

\(\ds \sum_{j \mathop = 0}^{n - 1} \alpha^{j s}\) \(=\) \(\ds \sum_{j \mathop = 0}^{n - 1} \alpha^{j r}\)
\(\ds \) \(=\) \(\ds \dfrac {\alpha^{n r} - 1} {\alpha^r - 1}\) valid because $\alpha^r \ne 1$ \(\quad\) Sum of Geometric Sequence
\(\ds \) \(=\) \(\ds \dfrac {\paren {\alpha^n}^r - 1} {\alpha^r - 1}\)
\(\ds \) \(=\) \(\ds \dfrac {1^r - 1} {\alpha^r - 1}\)
\(\ds \) \(=\) \(\ds \dfrac {1 - 1} {\alpha^r - 1}\)
\(\ds \) \(=\) \(\ds 0\)

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Sum_of_Powers_of_Primitive_Complex_Roots_of_Unity&oldid=630593"