# Is $every$ prime factor of $\frac{n^{163}-1}{n-1}$ either $163$ or $1\;\text{mod}\;163$?

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

• 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$? – abiessu Apr 2 '16 at 19:32
• @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$ – Will Jagy Apr 2 '16 at 19:34
• @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. – Tito Piezas III Apr 2 '16 at 19:36
• 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$ – Tito Piezas III Apr 2 '16 at 19:44
• 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. – Wojowu Apr 2 '16 at 20:14

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$

• @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$. – Tito Piezas III Apr 2 '16 at 19:59
• @TitoPiezasIII If $n$ mod $q$ has order $1$ then $n=1+\lambda\color{Red}{q}$... – arctic tern Apr 2 '16 at 20:03
• @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.$ – Will Jagy Apr 2 '16 at 20:04
• @arctictern: He did say $q=p$, which I assume for the "otherwise" case. – Tito Piezas III Apr 2 '16 at 20:09
• @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 – Will Jagy Apr 2 '16 at 20:12

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.$