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

This is the actual full text

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)$.

  • $\begingroup$ 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? $\endgroup$ – PhantomR Jun 27 '18 at 20:04
  • $\begingroup$ @PhantomR: $\zeta = 4$, so $\zeta \equiv 4$ because $4 \equiv 4$. $\endgroup$ – Hurkyl Jun 27 '18 at 20:04
  • $\begingroup$ @PhantomR I've included the definition of "primitive root of unity" $\endgroup$ – Hurkyl Jun 27 '18 at 20:06
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Taylor Jun 27 '18 at 20:14
  • 2
    $\begingroup$ @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}$. $\endgroup$ – Hurkyl Jun 27 '18 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.