Proving in different ways that $n^{n-1}-1$ is divisible by $(n-1)^2$.

Question

I have this amazing exercise which explicitly says prove in at least six different way that $n^{n-1}-1$ is divisible by $(n-1)^2$ where $n$ is an integer.

So far I have only prove it as follows: By geometric sum we have

$$\sum_{k=0}^{n-2}n^k=\frac{n^{n-1}-1}{n-1}$$ However, since $n\equiv 1\mod (n-1)$ we have $$\frac{n^{n-1}-1}{n-1}=\sum_{k=0}^{n-2}n^k\equiv \sum_{k=0}^{n-2}1^k\mod(n-1)$$ that is $$\frac{n^{n-1}-1}{n-1}=\sum_{k=0}^{n-2}n^k\equiv n-1\mod(n-1)\Longleftrightarrow \frac{n^{n-1}-1}{n-1} \equiv 0\mod(n-1)$$

and this prove that $(n-1)^2$ divides $n^{n-1}-1$.

Does anyone have another approach different from mine.? Note that I do necessary need one to give all six approaches as was asked in the exercise one or two is plainly enough for me.

Answer 1

Expanding by the binomial theorem, $$(k+1)^{n-1}-1=k^{n-1}+\binom{n-1}1k^{n-2}+\cdots+\binom{n-1}2k^2+\binom{n-1}1k\ .$$ Now substitute $k=n-1$.

• The last term on the RHS is $(n-1)k=(n-1)^2$ which is obviously a multiple of $(n-1)^2$.

• Every other term is a multiple of $k^2$, which is $(n-1)^2$.

Answer 2

Note that

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

then dividing

$$\frac{n^{n-2}+n^{n-3}+...+n+1}{n-1}$$

it can be shown that at each step the remainder is

$$2n^{n-3}+n^{n-4}+...+n+1$$ $$3n^{n-4}+n^{n-3}+...+n+1$$ $$...$$ $$(n-2)n+1$$ $$(n-1)\cdot1$$

Answer 3

Write $n^{n-1}-1$ in base $n$. It consists of $n-1$ digits that are all the digit $n-1$.

So we can divide by $n-1$ once. The quotient is obviously also a repdigit, consisting of $n-1$ ones.

Now, a number in base $n$ is divisible by $n-1$ exactly if its digital sum is divisible by $n-1$. But the repunit from the previous step has digital sum $n-1$. So we can divide by $n-1$ once more!

---

In some sense this is the same as what you're already doing, but it is arguably a different way of thinking about it, so it may qualify as a different proof.

Answer 4

$$ \begin{align} n^{n-1}-1 &= (n-1) ( n^{n-2} \color{red}{- 1} + n^{n-3} \color{red}{- 1} +\ldots + n^2 \color{red}{- 1} + n \color{red}{- 1} + 1 \color{red}{+n-2}) \\ &= (n-1) \big(\,(n-1)(\ldots) + (n-1)(\ldots)+ \ldots + (n-1)(n+1)+ (n-1)+ (n-1))\,\big) \end{align} $$

Answer 5

Binomial theorem:

$$n^{n-1}=(1+(n-1))^{n-1}=1+\binom{n-1}{1}(n-1)^1+\binom{n-1}{2}(n-1)^2\cdots\equiv 1\pmod{(n-1)^2}$$

More generally:

If $a\equiv 1\pmod m$ then $a^m\equiv 1\pmod{m^2}.$

Answer 6

Set $P(x)=x^{n-1}-1$.

• We have $P(1)=1^{n-1}-1=0$, so $P(x)=(x-1)Q(x)$ for some polynomial $Q(x)\in\mathbb Z[x]$.
• We also have $P'(1)=(n-1)1^{n-2}=n-1$ i.e. $n-1$ is the remainder of division of $P'(x)$ by $x-1$, i.e. $(x-1)Q'(x)+Q(x)=P'(x)=(x-1)R(x)+n-1$ for some polynomial $R(x)\in\mathbb Z[x]$.

Now, by multiplying by $x-1$, we get: $(x-1)^2Q'(x)+P(x)=(x-1)^2R(x)+(x-1)(n-1)$. Now set $x=n$ and we get: $n^{n-1}-1=P(n)=(n-1)^2(R(n)-Q'(n)+1)$ - divisible by $(n-1)^2$.