Elementary Number Theory proof

Question

Let $n,k$ be natural numbers, $n\geq 2$. Prove that

$(n-1)^2|(n^k-1)$ if and only if $(n-1)|k$.

I was given a hint to use $n^k=((n^k-1)+1)$ and use the Binomial Theorem but I still haven't been able to crack this proof.

Answer 1

We write $$n=(n-1)+1$$ from which we see that $$n^k= \left( (n-1)+1\right)^k=(n-1)^k+k(n-1)^{k-1}+\cdots +k(n-1)+ 1$$ $$\implies n^k-1=(n-1)^k+\cdots + k(n-1)$$

Visibly, $(n-1)^2$ divides every term in the sum except possibly the last one. Thus $(n-1)^2$ divides the left hand iff it divides $k(n-1)$ and we are done.

Answer 2

Hint: Show by induction that the remainder of the polynomial division $x^{m}+x^{m-1}+\cdots 1$ by $x-1$ is $m+1$.

$$x^{m}+x^{m-1}+\cdots 1=x(\color{red}{x^{m-1}+x^{m-2}+\cdots 1})+1$$

Then, notice $(n-1)^2|n^{k}-1\iff n-1|n^{k-1}+n^{k-2}+\cdots 1$, and use the previous