The prime numbers $q$ for which there exists $n \in \mathbb{N}$ such that $q \mid f(n)$

Let $p$ be a prime number and $f(x) = x^{p-1}+x^{p-2}+\cdots+x+1$. Determine the prime numbers $q$ for which there exists $n \in \mathbb{N}$ such that $q \mid f(n)$.

We can prove that if $q$ is a prime divisor of $f(n)$, then $q = p$ or $q \equiv 1 \pmod{p}$. How can we prove that for each of these primes $q$, there exists $n$ such that $q \mid f(n)$?

• More or less trivial: Note that if $n\equiv 1\pmod q$ then the sum is just $p\bmod q$ and so clearly not zero (except for the trivial case). Otherwise, the sum is $\frac{n^p-1}{n-1}$ and so you have $n^p\equiv 1\pmod q$. – Steven Stadnicki Jul 14 '17 at 22:37

Take $q=kp+1$ and let $n$ be a primitive root modulo $q$. Note that $k\ge 2$ and $n^k-1$ is coprime with $q$ (indeed, in the opposite, $\varphi(q)=kp$ would divide the exponent $k$). Then, by Fermat little theorem, $q \mid n^{kp}-1$. Hence, $$q\mid \frac{n^{kp}-1}{n^k-1}=f(n^k).$$

• In the case that $q^2 \mid f(n)$, how could we prove that $q \equiv 1 \pmod{p}$ all work? – user19405892 Jul 14 '17 at 23:06
• I am only proving that if $q\equiv 1\bmod{p}$ then there exists $x$ such that $q\mid f(x)$. – Paolo Leonetti Jul 14 '17 at 23:09

For which primes $q$ does $f(x)$ have a root mod $q$ ?

When $q= p$, we have that $1$ is a root of $f(x) \bmod q$.

When $q\ne p$, the roots of $f(x) \bmod q$ are the same as the roots of $x^p-1 \bmod q$, because $1$ is not a root of $f(x) \bmod q$ and we an write $f(x)=\dfrac{x^p-1}{x-1}$.

So, we're looking for $x$ having order $p$ mod $q$. These exist iff $p$ divides $q-1$ because $U(q)$ is cyclic.

So the primes $q\ne p$ are exactly those satisfying $q \equiv 1 \bmod p$. There are infinitely many such primes, by Dirichlet's theorem on arithmetic progressions.

I don't know whether one can say anything further.

• Indeed, cyclotomic polynomials are often used to give an elementary proof of the infinitude of primes of the form $\equiv 1\pmod{m}$. – Jack D'Aurizio Jul 14 '17 at 23:02

A partial answer: $p\mid f(1)$. But I suppose that you already knew this.