extend to non prime power moduli

[jacksonwalters]

when $N = 1, 2, 4, p^k, 2p^k$, the mult. group of $Z/NZ$ is cyclic.

since n is a power of 2, this forces us to work mod $p^k$ so that n is invertible.

however, (Z/NZ)* is generally a finite abelian group of size \phi(N). this group contains cyclic subgroups of various sizes.

if there is a subgroup C such that n | |C|, then given a generator $g$ we can find an $n^{th}$ root of unity $\omega = g^{|C|/n}$.

one method to compute this generator is by using the decomposition $(Z/NZ)^\ast$ and the Chinese remainder theorem.

[jacksonwalters]

https://en.wikipedia.org/wiki/Root_of_unity_modulo_n