What is the remainder when $ n^n $ is divided by $ (n-1) $?

Question

I want to find out the remainder if $ n^n $ is divided by $(n-1)$ . I have tried investigating a number of examples for small $n$:

• $ 2^2 $ is divided by $1$ gives remainder $0 $
• $ 3^3 $ is divided by $2$ gives remainder $1$
• $ 4^4 $ is divided by $3$ gives remainder $1$
• $ 5^5 $ is divided by $4$ gives remainder $1$
• $ 6^6 $ is divided by $5$ gives remainder $1$

But I can't identify any pattern to find out the remainder. So please help me to find out the remainder if $ n^n $ is divided by $ n-1 $.

Answer 1

The other answers are all correct. But since you posted such an elementary problem, I guess it would be better if you learnt how to attack this problem rather than only the solution of it.

See, you need to find out $n^n \pmod{n-1}$ where $n>2$. Whenever you need to find mod of such products, the first thing to try is finding out the mod of individual terms (the others being some manipulation or Euler's/Fermat's little theorem if it's a power etc.). Now, in this case, it is evident that $n \equiv (n-1)+1 \equiv 1 \pmod{n-1}$.

We know that, taking mod is multiplicative. So, $n^n \equiv (1)^n \pmod{n-1} \equiv 1 \pmod{n-1}$.

Please comment if you need further clarifications.

Answer 2

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

Answer 3

$n^n = (n^{n-1} + n^{n-2} +\ldots + 1)(n-1) + 1$. Its a telescope sum.

Answer 4

For n>2:

Binomial expansion:

$(1+(n-1))^n=$

$\sum_{k=1}^{n}\binom{n}{k}(n-1)^k+1;$

The first term is divisible by $(n-1)$, the remainder is $1$.