# Roots Of Unity - Is It Primitive?

• Sane
In summary, the conversation discusses the algorithm for determining the nth roots of unity and how to test if they are primitive. The individual has found that for odd values of n, testing if (n, k) are coprime works, but for even values, it does not. They have tested a guess of (n-k-1, n) and found it to work for all known examples. There is a discussion about the accuracy of the code and if it is necessary to only calculate and return the first rotation to find a primitive nth root of unity. The end goal is to use this algorithm in the "Discrete Weighted Transform With An Irrational Base" (DWTIB). There is also a mention of a mistake where
Sane
All right, thanks to everybody's help, I've got the algorithm for determining the nth roots of unity.

However, for determining which ones are primitive, I'm still having a little trouble.

If n is odd, I can test if (n, k) are coprime. However, for even values of n, it seems that it doesn't work.

I took a guess and tried to see if (n-k-1, n) are coprime, to determine if the nth root of unity is primitive. It seems to work for all known examples I've tried.

Is that guess of mine incorrect? If not, what should I do for even values of n?

Here's some Python code, demonstrating that an even value of n, 4, yields only primitive roots of unity, by testing if (n-k-1, n) are coprime. Highlighted in blue.

Code:
import math

def resolve_limit (value):
if value < 0.00001 and value > - 0.00001:
return 0
if value > 0.49999 and value < 0.50001:
return 0.5
if value < -0.49999 and value > -0.50001:
return -0.5
return value

def polar_to_complex (r, theta):
a = math.cos (theta) * r
b = math.sin (theta) * r
a = resolve_limit (a)
b = resolve_limit (b)
return (a, b)

def gcd (a, b):
while b:
a, b = b, a % b
return a

def coprime (a, b):
if a == 0 or b == 0:
return False
return gcd (a, b) == 1

def prime_nth_roots (n):
is_even = (n%2 == 0)

for k in range (n):

if is_even:
[b][color=blue]if coprime (n-k-1, n)[/color][/b]:
angle = k * 2 * math.pi / float(n)
yield polar_to_complex (-1, angle)

else:
if coprime (k, n):
angle = k * 2 * math.pi / float(n)
yield polar_to_complex (1, angle)

print [root for root in prime_nth_roots (4)]

Last edited:
Sane said:
If n is odd, I can test if (n, k) are coprime. However, for even values of n, it seems that it doesn't work.
Why do you think that?

Here's some Python code, demonstrating that an even value of n, 4, yields only primitive roots of unity, by testing if (n-k-1, n) are coprime.

Hurkyl said:
Why do you think that?

I think that because it wasn't outputting the correct answers, as suggested for certain situations. If you move my coprime function call test to the first dimension of the conditional statements, using the call "coprime (k, n)", and let n=4, it does not get the right answers.

Hurkyl said:

Are you positive? The code outputs:

>>>
[(-1.0, 0), (1.0, 0)]

Which translates to +i and -i.

According to Wikipedia, these are the correct primitive nth roots of unity where n = 4.

Wikipedia said:
The fourth roots of unity are

$$\left\{ 1, +i, -1, -i \right\} ,$$

of which +i and -i are primitive.

(a, b)

corresponds to

a + bi.

Yeah, I smacked my forehead right after I made that post. No sooner than I made that statement, I made the connection that my conclusion wasn't even correct in the first place. :tongue:

Oh geez. Hahah. So was it correct to only test coprime(n, k)?

Furthermore, if I only need "a primitive nth root of unity", do I only need to calculate and return the first rotation, since (1, n) will always be coprime? Which reduces the algorithm to O(1) time?

I was hoping you'd see it just before you made your post.

Furthermore, if I only need "a primitive nth root of unity", do I only need to calculate and return the first rotation, since (1, n) will always be coprime? Which reduces the algorithm to O(n) time?
Why wouldn't it work?

Incidentally, isn't it much faster than O(n) time? You're just doing a couple multiplies and computing one sine and one cosine.

Last edited:
this programmed approach seems silly to me. just think about it.

I assume computing the primitive 4-th roots was merely a test of his program, not the end goal.

Hahaha, yes. I actually immediately edited it to O(1) after I made the post. I'm surprised that you managed to catch my original post. You must have been close by at the time I posted.

It's O(1) because generally mathematical computations are expressed as a constant, even though they may themselves, take linear (or even polynomial) time.

Hurkyl said:
Why wouldn't it work?
Just checking. That's great then! I just did not want to make a catastrophic mistake that could ressonate throughout my entire program!

Hurkyl said:
I assume computing the primitive 4-th roots was merely a test of his program, not the end goal.

Precisely. The "Discrete Weighted Transform With An Irrational Base" (DWTIB) requires a primitive nth root of unity in the appropriate domain, where n is the chosen run time for the Algorithm W variant of the DWT.

Last edited:
I believe I found out why I figured my algorithm to be incorrect (yet used a wrong example in my first post)...

If n = 2, the only supposed primitive root is -1, yet my algorithm yields +1.

Code:
import math

def resolve_limit (value):
if value < 0.00001 and value > - 0.00001:
return 0
if value > 0.49999 and value < 0.50001:
return 0.5
if value < -0.49999 and value > -0.50001:
return -0.5
return value

return deg * math.pi / 180.0

def complex_to_polar (a, b):
r = (a**2.0 + b**2.0)**0.5
theta = math.acos (a / r)
return (r, theta)

def polar_to_complex (r, theta):
a = math.cos (theta) * r
b = math.sin (theta) * r
a = resolve_limit (a)
b = resolve_limit (b)
return (a, b)

def gcd (a, b):
while b:
a, b = b, a % b
return a

def coprime (a, b):
if a == 0 or b == 0:
return False
return gcd (a, b) == 1

def prime_nth_roots (n):
is_even = n%2 == 0
for k in range (n):
if coprime (k, n):
angle = k * 2 * math.pi / float(n)
yield polar_to_complex ((1, -1)[is_even], angle)

def a_prime_nth_root (n):
is_even = n%2 == 0
angle = 2 * math.pi / float(n)
return polar_to_complex ((1, -1)[is_even], angle)

if __name__ == '__main__':
n = 2

print [root for root in prime_nth_roots (n)]
print a_prime_nth_root (n)

When I ran your original algorithm on 2 (after removing the "is_even" check), it gives me -1 is the only primitive root of 1.

When I run this new code, it says 1 is a primitive square root of 1.

In my second code I used a length of negative 1 for an even value of n. While in the first code, if you removed the "is_even" check, it would have used positive 1.

If a value of n is even, you need to either add pi to the angle, or set the length to negative 1.

That's not for something else is it?

That's not for something else is it?
I think you're thinking of the trick to turn a primitive n-th root into a primitive (2n)-th root. (with n odd)

Oh my... so the algorithm dumbs down to something as little as...

Code:
def a_prime_nth_root (n):
return polar_to_complex (1, 2 * math.pi / float(n))

Jesus christ, that's a lot simpler. Heh. Thanks for the help.

Sane said:
Hahaha, yes. I actually immediately edited it to O(1) after I made the post. I'm surprised that you managed to catch my original post. You must have been close by at the time I posted.

There's no way it's O(1). You're doing a division, which takes O(log(n)) absolute minimum -- and probably more like O(log(n)2).

Division and multiplication of 16-32 bit numbers is often only one operation for most 32-64 bit processors. n will never be more than 2 bytes.

Last edited:

## 1. What are roots of unity?

Roots of unity are complex numbers that, when raised to a certain power, result in the value of 1. For example, the fourth roots of unity are 1, -1, i, and -i, since (1)^4 = (-1)^4 = (i)^4 = (-i)^4 = 1.

## 2. How are roots of unity related to primitive roots?

Primitive roots are a subset of roots of unity, specifically those that generate all other roots of unity when raised to different powers. In other words, a primitive root of unity has the property that its powers are distinct from each other and cover all other roots of unity.

## 3. What is the significance of primitive roots of unity?

Primitive roots of unity are important in various mathematical fields, such as number theory, algebra, and geometry. They have applications in cryptography, coding theory, and signal processing, among others.

## 4. How can I determine if a root of unity is primitive?

A root of unity is primitive if and only if its order is equal to the totient function of its modulus. In other words, if the root of unity is raised to the power of the totient function of the modulus, the result is equal to 1.

## 5. Can all roots of unity be expressed as a power of a primitive root?

Yes, all roots of unity can be expressed as a power of a primitive root. This is known as the primitive root theorem, which states that any root of unity can be written as a primitive root raised to a certain power.

• General Math
Replies
5
Views
892
• Thermodynamics
Replies
3
Views
1K
• Programming and Computer Science
Replies
8
Views
791
• Linear and Abstract Algebra
Replies
2
Views
787
• General Math
Replies
1
Views
3K
• Engineering and Comp Sci Homework Help
Replies
10
Views
1K
• Programming and Computer Science
Replies
2
Views
2K
• Programming and Computer Science
Replies
6
Views
1K
• General Math
Replies
4
Views
2K
• Engineering and Comp Sci Homework Help
Replies
37
Views
4K