- #1

Sane

- 221

- 0

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.

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: