# Prove that $(n - 1)^2 \mid n^k -1$ if and only if $(n - 1) \mid k$ [duplicate]

I need help!

I need to prove that for any $2 \le n,k$ positive integers $(n - 1)^2 \mid n^k -1$ if and only if $(n - 1) \mid k$

Thanks!

## 3 Answers

Hint: $n^k - 1 = (n-1)\left(1 + n + n^2 + \cdots + n^{k-1}\right)$

• Continuing on the hint: $1+n+ \dotsb + n^{k-1} = (1+n-1)^0+ (1+n-1)^1 + \dotsb + (1+n-1)^{k-1} \equiv k \pmod{n-1}$, since there are $k$ terms indexed by $0, 1, \ldots, k-1$. – Catalin Zara May 8 '17 at 21:31

By a preexisting theorem, the formula for the sum of geometric series is $$n^0+n^1+...+n^k=\frac{n^{k+1}-1}{n-1}$$ Since the sum is an integer, so is the ratio on the right, showing that $n-1$ divides $n^k-1$. Now, because of this formula, we know that $$(n-1)^2 \mid n^k-1$$ if and only if $$n-1 \mid \frac{n^{k}-1}{n-1}$$ or $$n-1 \mid n^0+n^1+...+n^{k-1}$$ Now we just need to prove that $$n-1 \mid n^0+n^1+...+n^{k-1}$$ if and only if $n-1 \mid k$.

It can be proven using induction that the quotient $$\frac{n^0+n^1+...+n^{k-1}}{n-1}$$ is equal to $$n^{k-2}+2n^{k-3}+3n^{k-4}+...+(k-2)n^{1}+(k-1)n^{0}+\frac{k}{n-1}$$ Which is an integer whenever the fractional part at the end is integral. That fractional part $$\frac{k}{n-1}$$ is only an integer when $n-1 \mid k$, proving the statement. QED.

• An easier way to understand divisibility of $n^0 + n^1 + \cdots + n^{k-1}$ by $n-1$ is to note that $n$ is congruent to $1$ mod $n-1$ so $n^r$ is always congruent to $1$ as well. – Erick Wong May 8 '17 at 21:52
• Yeah... I'm new to modular arithmetic, though. – Franklin Pezzuti Dyer May 8 '17 at 21:53

Equivalently, for any positive integers $m, k$: $$m^2 \mid (m + 1)^k - 1 \iff m \mid k.$$

But $(m + 1)^k - 1 = km + lm^2$, where $l = \sum_{j=2}^k \binom{k}{j}m^{j - 2}$ (the sum is zero if $k = 1$, and is always an integer), so $m^2 \mid (m + 1)^k - 1$ if and only if $m^2 \mid km$, i.e. $m \mid k$, as required.