If $n$ is a positive integer, does $n^3-1$ always have a prime factor that's 1 more than a multiple of 3?

It appears to be true for all $n$ from 1 to 100. Can anyone help me find a proof or a counterexample?

If it's true, my guess is that it follows from known classical results, but I'm having trouble seeing it.

In some cases, the prime factors congruent to 1 mod 3 are relatively large, so it's not as simple as "they're all divisible by 7" or anything like that.

It's interesting if one can prove that an integer of a certain form must have a prime factor of a certain form without necessarily being able to find it explicitly.

EDITED TO ADD: It appears that there might be more going on here!

$n^2-1$ usually has a prime factor congruent to 1 mod 2 (not if n=3, though!)

$n^3-1$ always has a prime factor congruent to 1 mod 3

$n^4-1$ always has a prime factor congruent to 1 mod 4

$n^5-1$ appears to always have a prime factor congruent to 1 mod 5.

Regarding $n^2-1$: If $n>3$, then $n^2-1=(n-1)(n+1)$ is a product of two numbers that differ by 2, which cannot both be powers of 2 if they are bigger than 2 and 4. Therefore at least one of $n-1,n+1$ is divisible by an odd prime.

Regarding $n^4-1$: If $n>1$, we factor $n^4-1$ as $(n+1)(n-1)(n^2+1)$. We claim that in fact, every prime factor of $n^2+1$ is either 2 or is congruent to 1 mod 4. If $p$ is an odd prime that divides $n^2+1$, then $-1$ is a square mod $p$, but the odd primes for which $-1$ is a square mod $p$ are precisely the primes congruent to 1 mod 4. It remains just to show that $n^2+1$ cannot be a power of 2. If $n$ is even this is obvious, and if $n=2k+1$ is odd, then $n^2+1=(2k+1)^2+1=4k^2+4k+2$ is 2 more than a multiple of 4.

Regarding $n^5-1$, I don't have a proof, but based on experimenting with a few dozen numbers, I conjecture that in fact, every prime factor of $n^4+n^3+n^2+n+1$ is either 5 or is 1 more than a multiple of 5.

Solution 1:

The case $n=1$ is uninteresting, so let $n\gt 1$. We show that $n^2+n+1$ has a prime factor congruent to $1$ modulo $3$, by showing that $4(n^2+n+1)$ has such a prime factor.

Note that $n^2+n+1$ is odd. We first show that $3$ is not the only odd prime that divides $n^2+n+1$. For suppose to the contrary that $(2n+1)^2+3=4\cdot 3^k$ where $k\gt 1$. Then $2n+1$ is divisible by $3$, so $(2n+1)^2+3\equiv 3\pmod{9}$, contradiction.

Now let $p\gt 3$ be a prime divisor of $(2n+1)^2+3$. Then $-3$ is a quadratic residue of $p$. A straightforward quadratic reciprocity argument shows that $p$ cannot be congruent to $2$ modulo $3$.

Remark: By considering $n$ of the form $q!$ for possibly large $q$, we can use the above result to show that there are infinitely many primes of the form $6k+1$.

Solution 2:

For $p\equiv 1\pmod 3$, there exist three distinct solutions of $x^3\equiv 1\pmod p$, and if $n$ is congruent modulo $p$ to such $x$ then $n^3-1$ is a multiple of $p$. Heuristically, this solves the problem affirmatively for a fraction $\frac 3p$ of all possible $n$.

Let's make this a bit less hand-wavy: Let $p_1=7, p_2=13, p_3=19,\ldots$ denote the sequence of prime $\equiv 1\pmod 3$. Then of the $M:=p_1p_2\cdots p_m$ residue classes modulo $M$, there are only $(1-\frac3{p_1})(1-\frac3{p_2})\cdots(1-\frac3{p_m})M=(p_1-3)(p_2-3)\cdots(p_m-3)$ residue classes $x$ for which $n\equiv x\pmod M$ does not imply that $n^3-1$ has a prime factor $\in\{p_1,\ldots,p_m\}$. As we let $m\to \infty$, the product $(1-\frac3{p_1})(1-\frac3{p_2})\cdots(1-\frac3{p_m})$ can be shown to tend to $0$. So at least the density of $n$ that do not work must be zero.