# Divisibility (gcd) 9

• December 19th 2008, 12:47 PM
Sea
Divisibility (gcd) 9
$n \geq 2$ and $k \in \mathbf{Z^{+}}$

Show that:

$(n-1)^{2}|n^{k}-1 \Leftrightarrow n-1|k$
• December 19th 2008, 01:12 PM
JaneBennet
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.$