= Solution
For $p\nmid n$, the reduction of the <cyclotomic polynomial> $\Phi_n$ has precisely the primitive $n$th roots as its roots. If $p\mid\Phi_n(x)$, the residue class of $x$ has multiplicative order $n$ in $\mathbb F_p^\times$, so <Lagrange's theorem> gives $n\mid p-1$. Conversely, if $n\mid p-1$, cyclicity of the multiplicative group supplies an element of order $n$, which is a root of $\Phi_n$; any integer representative supplies $x$. Hence
$$
\boxed{p\mid\Phi_n(x)\text{ for some integer }x\iff p\equiv1\pmod n.}
$$
Three explicit examples are $\Phi_3(X)=X^2+X+1$ with $x=2,p=7$; $\Phi_4(X)=X^2+1$ with $x=2,p=5$; and $\Phi_6(X)=X^2-X+1$ with $x=3,p=7$. Each prime is coprime to the relevant $n$ and has the stated congruence.
Back to article page
