Is $X = (n-1)^n + n$ always composite for $n \geq 4 \in \Bbb Z$?

Question

$$\textit{Proposition}: \text{Given} \ X = (n-1)^n + n,\ \forall \ n \in \Bbb Z, \ n \geq 4, X \ \text{is composite.}$$

---

This came up sort of at random on a mailing list and it's jammed its way into being stuck in my brain. It's easy to test that it's true for the first few hundred thousand integers, suggesting it's likely true.

There are a few things that are easy to prove:

1. $X$ is always odd: if $(n-1)^n$ is odd, $n$ is even and vice versa.

2. $(n - 1) \equiv -1 \pmod n $. Since $n \equiv 0 \pmod n$, we can see that $X \equiv (-1)^n \pmod n $. Therefore, $X \equiv -1 \pmod n$ for odd $n$, and $X \equiv 1 \pmod n $ for even $n$.

3. If $n \equiv 2 \pmod 3$, then $n-1 \equiv 1 \pmod 3$, so $(n-1)^n \equiv 1 \pmod 3$. If we add $n \equiv 2 \pmod 3$, we have $0 \pmod 3$, so $3 \mid X$. So a third of possible values for $n$ are easily shown to be composite, namely $n = 3m + 2$.

4. If $n \equiv \{4,13\} \pmod {20}$, then $5 \mid X$, as follows:

   If $n \equiv 4 \pmod {20}$ , then $4 \mid n$, $n \equiv 4 \pmod{10}$, and $(n - 1) \equiv 3 \pmod{10}$. Then we have $4^3+4 \equiv 5 \pmod{10}$

   If $n \equiv 13 \pmod {20}$, then $4 \mid (n-1)$, $(n-1) \equiv 12 \pmod{20}$, and $(n-1) \equiv 2 \pmod {10}$.

   Additionally, $n \equiv 1 \pmod 4$ and $n \equiv 3 \pmod{10}$.

   Therefore, in decimal, $(10k + 2)^{4m+1} \equiv 2 \pmod{10}$. Adding $n \equiv 3 \pmod{10}$ gives $X \equiv 5 \pmod{10}$.

That takes care of 40% of the integers. But (1) I feel like we ought not to have to go through the integers modulus by modulus, and (2) well, we have a lot of integers left.

Some other interesting tidbits that may or may not help:

1. For $n$ even and $n \not\equiv 2 \pmod 3$, $X$ is often divisible by $(n+1)$, or by $p$ if $(n+1) = p^2$, $p$ prime. Up to $n = 72$, this fails for $n = 34, 54, 64$.
2. For $n \not\equiv 2 \pmod 3$, $X$ is sometimes divisible by $(2n-1)$. Again up to $n = 72$, this is true for even $n = 6, 10, 22, 30, 34, 42, 54, 66, 70$. (Interesting, for all of those, $n \equiv 2 \pmod 4$. Just noticing that.) It's true for odd $n = 9, 21, 37, 45, 49, 57$... which are all $n \equiv 1 \pmod 4$.

Of course, being sometimes divisible by those numbers doesn't tell us why they're divisible by them. I tried using partial binomial expansions (learning about Stirling numbers along the way) but couldn't get anything useful. Has anyone seen or worked with this proposition before? Is it proven and I just can't find it anywhere?

Answer 1

I wanted to follow up on this a bit as I've done some more... research? Trial and error? One or the other. In case anyone is still following this!

First, I want to acknowledge René Gy above, for this lovely use of Fermat's Little Theorem, showing that if $n + 1$ is prime, $n + 1 \mid X$:

$$ (n-1)^n + n = ((n+1) - 2)^{((n+1) - 1)} + (n+1) -1 $$

For $n+1 = p$ prime, this is:

$$ (p-2)^{p-1} + p - 1 \equiv (-2)^{p-1} - 1 \pmod p$$

If this expression is $0$, that is, if $(n+1) = p \mid X$--then we have

$$ (-2)^{p-1} \equiv 1 \pmod p$$

This is Fermat's Little Theorem, indicating that it is true for all primes coprime to $2$, that is, all odd primes. This clears up the abundance of $p+1$ in our factorizations, and also indicates that if $n+1$ is prime, then X is composite.

---

The abundance of divisibility by $2n -1$ is, I suspect, explainable in the same way. It looks like for all numbers of the form $4k+1$ or $4k+2$, $2n-1 \mid X$ iff $2n-1$ is prime.

---

I've also done some trial and error following up on the modulo $20$ results I described originally. My thought was "Hey, $20$ is a pronic number (i.e., $n(n+1)$), I wonder what I can do with other pronics!" And it turns out that for each pronic number where $n+1$ is prime, we can find a set of residues modulo $p(p-1)$ that are divisible by $p$. These will obviously include $p-1$, but each set includes quite a few more. I don't think listing all of them here is really necessary, but I'll list a few. Sage/Python code if you wish to mess around with it is here: https://pastebin.com/Y24BmLs6

Divisible by $p$ for $5 \leq p \leq 13$ with modulus $M$:

$$p = 5; M = 20 \implies 5 \mid \{\mathbf{4}, 13\} \pmod{20}\\ p = 7; M = 42 \implies 7 \mid \{\mathbf{6}, 25\} \pmod{42}\\ p = 11; M = 110 \implies 11 \mid \{6, \mathbf{10}, 18, 61, 65, 74, 97\} \pmod{110}\\ p = 13; M = 156 \implies 13 \mid \{\mathbf{12}, 85, 94, 95, 99\} \pmod{156}$$

Residues covered by $n = p-1$ are in bold. The abundance of residues a bit above half the modulus is intriguing, and continues for larger moduli.

---

Edit: OK, now this is the sort of pattern I hadn't expected to find at all...

All those cases where $n \equiv 2 \pmod 3$ and therefore we can just kinda skip them? I noticed that all of them have squares in their factorizations. But it turns out they're not just any squares, they're the squares of the [centered] hexagonal numbers $3m^2 + 3m + 1$. More specifically:

$$ k \in \mathbb{N}, n = 3k + 2 \iff (3k^2 + 3k + 1)^2 \mid X = (n-1)^n + n $$

So far as I can tell, (1) almost all other $X$ are squarefree (the exceptions being $6, 64, 73$ so far), and (2) I have no clue why or how or what's going on here. It's baffling.