Let $\Phi\_n(x)$ be the $n$ th cyclotomic polynomial. I've checked the values of $\Phi\_n(2)$ for some small $n\geq 2$ and noticed that there is always a divisor of $\Phi\_n(2)$ of the form $kn+1$ (regardless of $\Phi\_n(2)$ being a prime or not) with the only exception of $n=6$. Does anyone know any counterexample to this or a proof for its validity? 



Is it true that $\Phi_n(2)$ has a divisor of the form $kn+1$ for all $n\neq 6$?
Note that $\Phi\_{21}(2)$ is a multiple of 7. The actual divisibility criterion can be found in notes of G. J. O. Jameson mentioned here [Cyclotomic polynomials: $\Phi\_n(p)$ is like $p^{\phi(n)}$ for big enough $p$, right?](https://mathoverflow.net/questions/221357) . In particular, non-Zsigmondy primes $q$ divide $\Phi\_n(a)$ only if they are coprime to $a$ and $n=mq^k$ where m is the order of $a \bmod q$.


The original question is answered by Zsigmondy and Bang, and the notes of Jameson give a nice brief account. Yes, with the exceptions noted, such prime divisors exist.


Gerhard "Divisibility Is Not So Simple" Paseman, 2016.04.27.


