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

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

• $n=7$ gives $271\times1033$ so there may not be a good reason, and so it may not be true. On the other hand, the probability a case is prime may be in a handwaving sense $O\left(\frac{1}{n \log n}\right)$ so the first counter example may be for very large $n$ Commented Nov 7, 2020 at 0:45
• The result "composite" is usually $100$% true. I were somewhere above $10k$ as well with PFGW and found not further prime either, so I can approve your computation. Commented Nov 10, 2020 at 21:32
• $(n-1)^n+n=((n+1)-2)^{n+1-1}+(n+1)-1 \equiv (-2)^{(n+1)-1}-1 \bmod (n+1)$, then $n+1$ divides $(n-1)^n+n$ iff $n+1$ is prime or $n+1$ is composite pseudoprime to base $2$. Commented Nov 10, 2020 at 23:12
• @EricSnyder A generalization of Fermat's little theorem is Euler's theorem : If $a$ and $n$ are coprime , then $$a^{\varphi(n)}\equiv 1\mod n$$ holds where $\varphi(n)$ denotes the totient function.For $p^k$ , we have $\varphi(p^k)=p^{k-1}\cdot (p-1)$ Commented Nov 12, 2020 at 14:13
• According to my calculations, no such prime for $n\le 15\ 000$. We can expect $1$ prime in the range $[15\ 000, 1\ 000\ 000]$ for $n$ Commented Nov 18, 2020 at 12:31

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.

• Note on the last edit: I checked up to $k = 500000$ and the pattern remains true. But polynomial division isn't enough to explain it. $(3k-1)^{3m+2}$ is always divisible by $3k^2 + 3k + 1$, but only when $k=m$ is $X$ divisible by the square. Part of the issue of course is that (expression in x)^(expression in x) is just trouble to work with. Also, a bit better code for the pronic number pattern above (so you don't have to change the prime each time: pastebin.com/K0QmjetZ Commented Dec 2, 2020 at 23:17
• New: almost all of the n for which X has a relatively large smallest factor are $\equiv 3 \pmod 4$. Exceptions at $n = 76, 160, 165, 186$. I went ahead and found all factors $<10^6$, or the smallest factor, up to $n=200$, except for 115 (days of computation and no factor) and 165 (but only tried for a few minutes). Commented Dec 4, 2020 at 20:52