# Root of unity belongs to Z/qZ. How?

EDIT: Really sorry for not posting this initially.. maybe it's easier to understand now. Source, page 6.

I've stubled upon a statement similar to this:

"Let $m,q$ be two integers such that $\mathbb{Z}/q\mathbb{Z}$ contains a primitive $m$-th root of unity and denote one such primitive $m$-th root by $\zeta$. Recall that the $m$-th cyclotomic polynomial splits into linear terms modulo $q$, $\Phi_n(X)=\displaystyle\prod_{i\in (\mathbb{Z}/m\mathbb{Z})^*}(X-\zeta^i) \mod q$. "

I'd like some help understanding according to what definition we can say that a primitive root of unity (except for $\pm 1$ for $m=1$ and $2$) can be said to "belong" to $Z_q$. It's clear for me that the $Z_q$ in question is not the usual $Z_q$. Also, I'd appreciate a name of/link to a result that presents that factorization modulo $q$.

Consider $m=2$, $q=15$, and $\zeta = 4$.

Then (the class of) $\zeta$ is a primitive $m$-th root of unity of $\mathbb{Z} / q \mathbb{Z}$, because it satisfies the definition (wikipedia reference):

• It is an $m$-th root of unity: $\zeta^2 \equiv 1 \bmod 15$
• It is not a $k$-th root of unity for any $1 \leq k < m$: $\zeta^1 \equiv 4 \bmod 15$

Note, however, that the quoted passage is wrong, since in this case:

• $\Phi_m(X) = X + 1$
• $(X - \zeta^1) = X - 4$

and these polynomials are not equivalent modulo $q$.

If you additionally require that $q$ be prime, the quoted passage is true. In this case the factorization is "obvious" in this case, since $\mathbb{Z} / q \mathbb{Z}$ is a field and the $\zeta^i$ are distinct roots of $\Phi_m(X)$.

If I recall correctly, another way for the quoted passage to be true without assuming $q$ is prime is if $\zeta$ is chosen to be one of the roots (in $\mathbb{Z} / q \mathbb{Z}$) of $\Phi_m(X)$.

• Whoa! I apologize, but I do not understand how a non-integer (not even real) like that $\zeta$ can be $\equiv$ to 4 mod 15. That's probably why I don't understand how a root of unity can be part of $Z_q$. Could you shed some light on this, please :D? – PhantomR Jun 27 '18 at 20:04
• @PhantomR: $\zeta = 4$, so $\zeta \equiv 4$ because $4 \equiv 4$. – Hurkyl Jun 27 '18 at 20:04
• @PhantomR I've included the definition of "primitive root of unity" – Hurkyl Jun 27 '18 at 20:06
• It's not 100% clear that the cyclotomic polynomial of the question is the standard cyclotomic polynomial over the integers - although if the source of the quote is using it to mean the minimal polynomial of the primitive roots then it runs into a different problem. – Peter Taylor Jun 27 '18 at 20:14
• @PhantomR: The Wikipedia article says when the ring is not specified, the complex numbers are implicitly assumed. Your problem specifies a ring: $\mathbb{Z} / q \mathbb{Z}$. So when we talk about primitive roots of unity in $\mathbb{Z} / q \mathbb{Z}$, we don't mean primitive roots of unity of $\mathbb{C}$. Also, I'm following the usual practice of denoting an element of $\mathbb{Z} / q \mathbb{Z}$ by specifying an integer representing an equivalence class. If you write elements of this ring as cosets, when I write $4$ I mean $4 + q \mathbb{Z}$. – Hurkyl Jun 27 '18 at 20:21