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?
1
-
$\begingroup$ To begin with, does $2^n-1$ always have a divisor of this form? $\endgroup$– Alex DegtyarevCommented Apr 27, 2016 at 17:52
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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? . 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.
answered Apr 27, 2016 at 19:51
-
1$\begingroup$ Another recent paper which may be of interest is Granville's arxiv.org/abs/1212.6306 , which contains references to further generalizations/relations of Zsigmondy's theorem. Gerhard "Where One Learns Primitive Factors" Paseman, 2016.04.27. $\endgroup$ Commented Apr 27, 2016 at 23:17
-
$\begingroup$ Thanks for the link maths.lancs.ac.uk/~jameson/cyp.pdf . Theorem 2.5 there answers my question, hence the question asked by @Alex. In fact not only one but all divisors of $\Phi_n(2)$ greater than $n$ are of the form $kn+1$ according to that theorem. It also characterizes the divisors less than $n$. Actually my question is $a=2$ case of that theorem. $\endgroup$ Commented Apr 28, 2016 at 17:07
$\begingroup$
$\endgroup$
2
In point of fact, it is well-known that if $p$ is a prime number and $a, n$ are integers that are not divisible by $p$, then $p \mid \Phi_{n}(a)$ implies $p\equiv 1 \pmod{n}$.
answered Apr 27, 2016 at 17:52
-
1$\begingroup$ Can't be iff; there are infinitely many primes $p\equiv1\bmod n$, and they can't all divide $\Phi_n(a)$. Unless those dots at the end are hiding something. $\endgroup$ Commented Apr 27, 2016 at 23:00
-
1$\begingroup$ @GerryMyerson: You are absolutely right! $\endgroup$ Commented Apr 28, 2016 at 0:32