0
$\begingroup$

Let us define a complex primitive N-th root of unity, omega: $$ \omega = \cos(\theta) + i\sin(\theta) \\ = e^{\frac{2\pi}{N}} $$

By the definition of an nth root of unity, ω is the second solution to the equation x^N = 1. Can someone explain to me how I can simplify the solutions' exponents via modular arithmetic? I sort of understand the generic congruence modulo nonsense (for M > N, Q is some quotient and R is some remainder):

$$ \omega^M; \\ M = QN + R \\ \omega^{QN + R} \\ = \omega^{QN} + \omega^R \\ = ω^R \\ R \equiv M \mod N $$

I don't exactly understand this. This is how my quantum mechanics professor explained it. I need to input 6 values corresponding to ω (those values are irrelevant to the problem), however I can only use ω and ω^2, even though N = 6. How do I get rid of the other exponents if my problem includes ω^3, ω^6, ω^9, ω^12 and ω^15?

$\endgroup$
1
$\begingroup$

Your calculations should read $$ w^{QN+R} = w^{QN}\times w^R = (w^N)^Q\times w^R = (1)^Q\times w^R = w^R $$ The idea is simple - each root of unity represents a point on the unit circle $\{z\in \mathbb{Z} : |z| = 1\}$. For a fixed $N \in \mathbb{N}$, there are $N$ equidistant points, (including 1), each one at an angle of $2\pi k/N$ radians from the $X$-axis (for $1\leq k\leq N$). When you multiply two such points, you merely add these angles.

In the case $N=6$, $$ w = e^{2\pi i/6} = e^{\pi i/3} $$ corresponds to the point at 60 degrees from the $X$-axis.

To compute $w^3$, you merely add $60^{\circ}$ 3 times to get $180^{\circ}\leftrightarrow -1$ Similarly, $$ w^6 \leftrightarrow 360^{\circ} \Rightarrow w^6 = 1 $$ $$ w^9 \leftrightarrow (60*9) = 540^{\circ} \equiv 180^{\circ} \Rightarrow w^9 = -1 $$ and so on.

Hope this helps

$\endgroup$
1
$\begingroup$

Well, for this you should realize that whenever the value $M$ is greater than $N$, you're coming back to a point which you already visited earlier. But what point is it exactly is what you need to find out. For example, if $N=12$, then if you're asked to find out $\omega^{15}$, then $\omega^{15}=\omega^{12+3}$. Now we already know that $\omega^{12}=1$and the angle is $0$; hence what you're required to find out is $\omega^{3}$. Now the math notation that you've written follows this example. This is a simple consequence of Phasor rotation on a circle.

Given $M$, $M$ can be written as a multiple of $N$ and a remainder. The remainder is what is necessary because you are just moving around the circle in a complex plane whose magnitudes are all 1 but their phases are different. The phase of the required $M$ is what is given by $R$.

$\endgroup$
1
  • 1
    $\begingroup$ Great. The relationship of 15 = 12 + 3 makes a lot simpler, in addition to Prahlad's answer. $\endgroup$ – cygorx Sep 23 '13 at 2:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.