# Math Help - Divisibility (gcd) 9

1. ## Divisibility (gcd) 9

$n \geq 2$ and $k \in \mathbf{Z^{+}}$

Show that:

$(n-1)^{2}|n^{k}-1 \Leftrightarrow n-1|k$

2. This is the same as saying that $n^2\mid (n+1)^k-1\ \Leftrightarrow\ n\mid k$ for all $n,k\in\mathbb{Z}^+.$

Note that $(n+1)^k-1\equiv kn\pmod{n^2}.$

Hence $n^2\mid(n+1)^k-1\ \Leftrightarrow\ n^2\mid kn\ \Leftrightarrow\ n\mid k.$