8
$\begingroup$

This was inspired by this question. More generally, given prime $p$ and any integer $n>1$, define,

$$F(n) = \frac{n^p-1}{n-1}=n^{p-1}+n^{p-2}+\dots+1$$

Q: Is every prime factor of $F(n)$ either $p$, or $1\;\text{mod}\;p$?

$\endgroup$
  • $\begingroup$ Is it reasonable to assume that a good portion of the numbers $n$ have been checked up to some limit for $p=163$? Have any $n$ been checked for other primes $p$? $\endgroup$ – abiessu Apr 2 '16 at 19:32
  • 1
    $\begingroup$ @abiessu I just ran modest runs for $p=5,7,11,$ seems to work for any prime. I also have ways to have the program be more careful, not having to check each factor by eye. Obvious for $p=5,$ the last digit of a prime factor is $1$ unless the factor is $5$ $\endgroup$ – Will Jagy Apr 2 '16 at 19:34
  • 1
    $\begingroup$ @abiessu: I used Mathematica to check for a higher range than Jagy's. I'm assuming it's true for all prime $p>2$ and just threw in $p=163$ as it is my favorite number. $\endgroup$ – Tito Piezas III Apr 2 '16 at 19:36
  • 1
    $\begingroup$ For the special case $n=2$, I think it's been established that every prime factor of $2^p-1$ has form $1\mod p$ $\endgroup$ – Tito Piezas III Apr 2 '16 at 19:44
  • 3
    $\begingroup$ There is a more general result: Every prime divisor of $\Phi_d(n)$ (cyclotomic polynomial) either divides $d$ or is $1\pmod d$. This result is in pretty much every paper on cyclotomic polynomials. $\endgroup$ – Wojowu Apr 2 '16 at 20:14
6
$\begingroup$

Yes: suppose $q$ divides $(n^p-1)/(n-1)$. Then $q$ divides $n^p-1$ so $n$ has order either $1$ or $p$ modulo $q$. In the second case $p$ divides $q-1$, so $q \equiv 1$ mod $p$. Otherwise $n = 1 + \lambda q$ for some $\lambda \in \mathbb{N}$ and we have

$$ \frac{n^p-1}{n-1} = \frac{(1+\lambda q)^p-1}{\lambda q} = \sum_{r=0}^{p-1} \lambda^r q^r \binom{p}{r+1}. $$

The first summand is $p$ and all the rest are divisible by $q$. Since $q$ divides the left-hand side, we have $q=p$.

Generalization. $(n^p-1)/(n-1) = \Phi_{p}(n)$, where $\Phi_d(x) \in \mathbb{Z}[x]$ is the $d$th cyclotomic polynomial. In a comment on the question Wojowu mentioned the following generalization: if $d \ge 2$ and $q$ is a prime dividing $\Phi_d(n)$, then either $q$ divides $d$, or $q \equiv 1$ mod $d$. Since it's a nice result, and could be more widely known, I've added a proof below. In particular, it can be used to show that any arithmetic progression $1,1+d,1+2d,1+3d,\ldots $ contains infinitely many primes.

Proof. Since $\Phi_d(x) \mid x^d-1$, we have $q \mid n^d-1$. Take $s$ maximal such that $q^s$ divides $n^d-1$. Suppose that $n$ has order $t$ modulo $q^s$. If $t=d$ then, since the group of units of $\mathbb{Z}/q^s\mathbb{Z}$ has order $\phi(q^s) = q^{s-1}(q-1)$, it follows from Lagrange's Theorem that $d \mid q^{s-1}(q-1)$. Hence either $d \mid q-1$ (and so $q \equiv 1$ mod $d$), or $d$ has a common factor with $q^{s-1}$, so $q \mid d$.

We now rule out the remaining case, where $t$, the order of $n$ modulo $q^s$, properly divides $d$. Since the polynomials $x^t-1$ and $\Phi_d(x)$ are coprime, and $x^t-1 \mid x^d-1$, we have

$$x^d-1 = (x^t-1)\Phi_d(x)f(x) $$

for some $f(x) \in \mathbb{Z}[x]$. Substituting $n$ for $x$ we get $n^d-1 = (n^t-1)\Phi_d(n)f(n)$. Since $q^s \mid n^t-1$ and $q \mid \Phi_d(n)$, it follows that $q^{s+1} \mid x^d-1$, contrary to the choice of $s$. $\Box$

$\endgroup$
  • $\begingroup$ @Mark: Is this result only valid for the special case when $n=p\lambda+1$? Kindly clarify the case $n \neq p\lambda+1$, as the question asks for arbitrary $n$. $\endgroup$ – Tito Piezas III Apr 2 '16 at 19:59
  • $\begingroup$ @TitoPiezasIII If $n$ mod $q$ has order $1$ then $n=1+\lambda\color{Red}{q}$... $\endgroup$ – arctic tern Apr 2 '16 at 20:03
  • 1
    $\begingroup$ @TitoPiezasIII his wording is kind of inside out, but it is worth checking word by word. The order business is that there is some positive integer $t$ such that $n^t \equiv 1 \pmod q,$ taking minimal $t$ means either $t = 1$ ot $t=p.$ At the same time, the order $\pmod q$ must divide $q-1,$ because Fermat's Little Theorem says $n^{q-1} \equiv 1 \pmod q$ as soon as $n$ is not a multiple of $q.$ $\endgroup$ – Will Jagy Apr 2 '16 at 20:04
  • $\begingroup$ @arctictern: He did say $q=p$, which I assume for the "otherwise" case. $\endgroup$ – Tito Piezas III Apr 2 '16 at 20:09
  • $\begingroup$ @TitoPiezasIII He is likely busy, check his MO profile. I think I will write out an expanded version as a CW answer. Red card Sergio Ramos in El Clasico $\endgroup$ – Will Jagy Apr 2 '16 at 20:12
5
$\begingroup$

Community Wiki answer, expanding that by Mark Wildon.

We have a fixed prime $p=163,$ but we will keep the symbol $p.$ The main tool here is Fermat's Little Theorem, which says that, for a prime $q$ that does not divide $n,$ we get $$ n^{q-1} \equiv 1 \pmod q. $$ Furthermore, there is some minimal positive integer $t,$ sometimes called the "order," such that $n^t \equiv 1 \pmod q.$ Manipulations using the gcd show that this $t |(q-1).$

We have some $q$ dividing $n^p - 1.$ So $n^p \equiv 1 \pmod q.$ We have some order $t.$ This says that $t | p.$ Either $t=1$ or $t=p.$

If the order $t=p,$ this means $p | (q-1).$ This is main conclusion asked about.

If the order $t=1,$ this means $n \equiv 1 \pmod q.$ We begin by expanding $n=1 + \lambda q.$ But then Mark gives $$ \frac{n^p-1}{n-1} = \frac{(1 + \lambda q)^p - 1}{\lambda q} $$ This is further expanded as $$ (1/\lambda q) (1 + p \lambda q + \binom{p}{2} \lambda^2 q^2 + \cdots + p \lambda^{p-1} q^{p-1} + \lambda^p q^p - 1 ) $$ or $$ p + \binom{p}{2} \lambda q + \binom{p}{3} \lambda^2 q^2 + \cdots + p \lambda^{p-2} q^{p-2} + \lambda^{p-1} q^{p-1}. $$ All but the first term of this have an explicit $q$ factor. The missing item is the first term, $p.$ If $q$ divides the whole thing, then $q$ divides $p$ and $q=p.$

$\endgroup$

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.