TITLE: Does the order of $a$ in $\left(\mathbb{Z}/ \Phi_n(a) \mathbb{Z} \right )^{\times}$ equal $n$?
QUESTION [1 upvotes]: Here, $\Phi_n(a)$ is the nth cyclotomic polynomial evaluated at a.
It's obvious that the multiplicative order of $a$ modulo $\Phi_n(a)$ divides $n$, because $a^n \equiv (a^n-1)+1 \equiv P(a)\cdot \Phi_n(a)+1 \equiv 1 \pmod{\Phi_n(a)}$ for some polynomial $P(x)$. But numerical data suggests that not only does the order of $a$ divide $n$, but actually the order of $a$ always equals $n$.
I have no idea how to approach this, and any hints or solutions are appreciated.

REPLY [2 votes]: I think that apart from the cases (1) and (2) 
(1) $n=6$, $a=2$, where $ord_{\Phi_6(2)}(2)=2$ 
(2) $n=2$, $a=2^s-1$, $s\ge2$, where $ord_{\Phi_2(2^s-1)}(2^s-1)=1$
it is true that $ord_{\Phi_n(a)}(a)=n$.
This is a corollary from Zsygmondi's theorem: when neither (1) nor (2) holds, there exists some prime $q$ so that $n=ord_q(a)$. 
$q$ must be a divisor of $\Phi_n(a)$, because $q$ divides $a^n-1$, and no other $a^m-1$ where $m\lt n$. 
Since $\Phi_n(a)$ divides $a^{ord_{\Phi_n(a)}(a)}-1$, then $q$ also divides $a^{ord_{\Phi_n(a)}(a)}-1$, then $ord_{\Phi_n(a)}(a)$ must be a multiple of $ord_q(a)$, 
that is $ord_{\Phi_n(a)}(a)$ is multiple of $n$, but since you have shown that it is obvious that  $ord_{\Phi_n(a)}(a)$ divides $n$, then we have $ord_{\Phi_n(a)}(a)=n$.
{"set_name": "stack_exchange", "score": 1, "question_id": 930447}