# How to simplify $\frac{n^n - 1}{n - 1} \mod (n + 1)$?

My question is how to simplify the following:

$$\frac{n^n - 1}{n - 1} \mod (n + 1)$$

I've tried a bunch of tricks (splitting into even and odd $n$ and using a difference of squares) but I can't seem to find anything that gives a clean answer.

Is there even a simplification for this?

EDIT: Apologies, I had $+$ instead of $-$

• This isn't even an integer for even values of n as far as I've tested. I can't prove it for general $2k$ but $2,4,6,8$ all don't work. – Nitin Oct 27 '16 at 0:36
• I had the wrong value - my apologies! – Cisplatin Oct 27 '16 at 0:36

You have changed your question, now it is easy.

Note that $n^n-1$ divides $n^2-1$ whenever $2 | n$. Hence, if $n$ is even, the answer is $0$, since $\frac{n^n-1}{(n+1)(n-1)}$ will be an integer.

Suppose that $n$ is odd. Note that $n \equiv -1 \mod n+1$. Hence, it is legitimate to replace $n$ by $-1$ in the modular expression, and this gives $$\frac{n^n-1}{n-1} = \sum_{i=0}^{n-1} n^i \equiv \sum_{i=0}^{n-1} (-1)^i \equiv 1 \mod n+1$$

because one factor of $1$ gets left out as $n$ is odd, so $n-1$ is even.

Hence, the answer is zero for even $n$, and $1$ for odd $n$.

Edit: You can multiply and check that $$(n-1) (1 + n + n^2 + \ldots + n^{n-1}) = n^n-1$$

it's the same as the equivalance class of $n^n+1$ by definition of modulars

• I had the wrong value up - please reconsider! – Cisplatin Oct 27 '16 at 0:38

The left-hand side is the sum of powers of $n$. Each power $n^a$ is equivalent to $(-1)^a\pmod{n+1}$

• Is there a proof for $n^a \equiv (-1)^a$? – Cisplatin Oct 27 '16 at 0:41
• $n \equiv -1 \mod (n+1)$ – Siong Thye Goh Oct 27 '16 at 0:46

$\frac {n^n-1}{n-1} = \sum_\limits{i=0}^{n-1} n^i\\ n \equiv -1\pmod{n+1}\\ n^i \equiv -1^i\pmod{n+1}\\ \frac {n^n-1}{n-1} \equiv \sum_\limits{i=0}^{n-1} (-1)^i\pmod{n+1}$

$0$ when $n$ is even. $1$ when $n$ is odd.