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

• From the factorization you can get a factor that's $\equiv 1 \mod 3$, but not necessarily a prime one – MCT Apr 1 '16 at 15:38
• Ran a code for the for all such numbers less than $10^7$. Seems ok. I am addin a list of the first few numbers and their prime factors. (7, 7) (26, 13) (63, 7) (124, 31) (215, 43) (342, 19) (511, 7) (728, 7) (999, 37) (1330, 7) (1727, 157) (2196, 61) (2743, 13) (3374, 7) (4095, 7) (4912, 307) (5831, 7) (6858, 127) (7999, 19) (9260, 463) (10647, 7) (12166, 7) (13823, 601) (15624, 7) (17575, 19) (19682, 13) (21951, 271) (24388, 7) (26999, 7) (29790, 331) (32767, 7) (35936, 1123) (39303, 397) (42874, 13) (46655, 7) (50652, 7) (54871, 37) (59318, 7) (63999, 13) (68920, 1723) (74087, 13) (79506, 7) – Banach Tarski Apr 1 '16 at 15:49
• Ran the code again. This statement seems to be true for all such numbers smaller than $2 * 10^8$ – Banach Tarski Apr 1 '16 at 15:56
• @idmercer: For prime powers $p>2$, you can generalize it neatly. Define $$F(n) = \frac{n^p-1}{n-1}$$ Conjecture: "If $F(n)$ is not divisible by $p$, then every odd prime factor of $F(n)$ is $1\mod 2p$." I'm not sure this is a proven result though, because otherwise the guys who answered would have used it. Maybe you can ask the general case for primes separately. – Tito Piezas III Apr 1 '16 at 22:01

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

• Is there a general result for the odd prime factors of $\displaystyle F(n)=\frac{n^p-1}{n-1}$ for prime $p$? (The OP was just focusing on the case $p=3$.) In other words, is every odd prime factor of $F(n)$ either $p$ or $1\mod p$? – Tito Piezas III Apr 2 '16 at 18:51
• Analysis is pretty simple (Fermat's Theorem) for $n$ and $p$ such that $n$ is not congruent to $1$ mod $p$. But there can be funny prime divisors otherwise. There should be a complete easy answer in general, but I looked and am missing something. That's why the appeal to reciprocity in the answer. – André Nicolas Apr 2 '16 at 18:54
• Yes, Fermat's little theorem occurred to me as well. I may ask the general prime case in the forum. Do you think you'll figure out the answer to the general case? :) – Tito Piezas III Apr 2 '16 at 18:57
• @TitoPiezasIII: Someone will. Conceivably me, but probably not. Would likely not be in any case, but also today is a massive cooking day. – André Nicolas Apr 2 '16 at 19:00
• Ok, Bon appetit. (P.S. The question is here.) – Tito Piezas III Apr 2 '16 at 19:20

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.