# Root of Unity Proof

Here is my question:

Let $\zeta$ be the first $n$-th root of unity, and let $\eta$ = $\zeta^k$ be any other $n$-th root of unity. Show that there exists an integer $m$ such that $\zeta = \eta^m$ if and only if $k$ has a multiplicative inverse in $\mathbb{Z}_n$.

Today was my first lecture in working with modular addition, subtraction, and multiplication. I know how to compute equation in $\mathbb{Z}_5$ for example (previous homework exercise based of solving an equation in $\mathbb{Z}_5$ but when I came across this proof, I got stuck. I don't even know how to begin the proof since this isn't about solving equations. It's one of those exercises that are one of the last ones before the end of a section and I even asked my friend if he knew where to start but after $30$ minutes, we had no success.

• Maybe this helps. – Masacroso Feb 17 '17 at 3:32

Note that all of the action in the numerator happens modulo $m$. The key point here is that although the roots of unity look like they're multiplicative objects, because multiplication of things of the same base adds in the exponent, the underlying structure comes from additive arithmetic.
In this case, if $\zeta^k=\eta$ and $j\equiv k^{-1}\mod m$ then $\eta^{j}=\zeta^{qm+1}=\zeta$ by definition of an inverse modulo $m$. Similarly, if $\eta^j=\zeta$ then $\zeta^{kj}=\zeta$ and by definition $m$ is the smallest positive integer for which $\zeta^m=1$, so $\zeta^{kj-1}=1$ and therefore $m|(kj-1)$ and $j$ is the required inverse.
• @i8Σπ_821 I use the division algorithm and definitions mostly, though I and the Euclidean algorithm is implicit in the fact that since $m$ is the smallest positive number for which $\zeta^m=1$ if $n>0$ such that $\zeta^n=1$ then $m|n$ since their gcd would be a smaller value otherwise. – Adam Hughes Feb 17 '17 at 3:39