1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Nitin Oct 27 '16 at 0:36
  • $\begingroup$ I had the wrong value - my apologies! $\endgroup$ – Cisplatin Oct 27 '16 at 0:36
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.