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)$?

  • 1
    $\begingroup$ 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$. $\endgroup$ – 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).$$

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

Your question is equivalent to:

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.

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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.