Let $a$ be an integer such that $gcd(a,n)=1$. Prove that $\displaystyle \text{ord}_n(a)=d$ if and only if $\displaystyle n| \Phi_d(a)$ ; where , $\text{ord}_n(a)$ is the order of $a$ modulo $n$ and $\Phi_n(x)$ denotes the $n$-th Cyclotomic polynomial.
From definition of $\text{ord}_n(a)$, we know that $d$ is the least positive integer such that $a^d \equiv 1\pmod n$. Then how I proceed ? Any hint. ?
Edit: I've stuck in the converse part to show $d$ is the smallest such that .....
Suppose that $n|\Phi_d(a)=a^d-1$.That is $a^d \equiv 1\pmod n$. Now I want to show that $d$ is the least positive integer satisfying this congruence.
The statement is not true if $n$ is not a prime. For example, take $n=15$. Then $$ 2^1=2, 2^2=4, 2^3=8, 2^4=1 \ \textrm{mod}\ 15. $$
Thus, $\mathrm{ord}_{15}(2) = 4$. However, $\Phi_4(2)=2^2+1 = 5$ and $15 \nmid 5$.
If $n$ is a prime, say $n=p$. We work over the field $\mathbb{Z}/p\mathbb{Z}$. It is well-known that $\mathbb{Z}/p\mathbb{Z}$ has a primitive root $g$, and by Fermat's little theorem, any $a\in \mathbb{Z}/p\mathbb{Z}-\{0\}$ is a root of $x^{p-1}-1=0$ mod $p$.
If $\mathrm{ord}_p(a)=d$, then $d|p-1$ and $a=g^j$ with $j=\frac{p-1}d k$ with $(k,d)=1$, $1\leq k \leq d$. Such $a$ is precisely the roots of $\Phi_d(x)=0$. This can be proved by $x^{p-1}-1=\prod_{d|p-1} \Phi_d(x)$. Any $a \in\mathbb{Z}/p\mathbb{Z}-\{0\}$ is a root of $\Phi_d(x)$ for some $d|p-1$. Moreover, each $\Phi_d(x)$ can have at most $\phi(d)$ roots where $\phi$ is the Euler Totient function. , Your statements is therefore true when $n$ is a prime $p$.