# Divisibility problem

• December 8th 2011, 04:23 PM
wsldam
Divisibility problem
Let n $\geq$ 2 and k be any positive integer. Prove that $(n-1)^{2} \mid n^{k}-1$ if and only if $(n-1) \mid k$. I've tried considering $(n-1) \mid (n^{k}-1)/(n-1)$ but it still got me no where.

I'm looking more for a hint than an actual answer as I do want to figure this out mostly on my own.
• December 8th 2011, 06:20 PM
I-Think
Re: Divisibility problem
Use the factorization $n^k-1=(n-1()n^{k-1}+n+n^{k-2}+...+n+1)$
So it reduces to $(n-1)|(n^{k-1}+n^{k-2}+...+n+1)$

then use the fact that $n\equiv{1}$ $(mod$ $n-1)$
P.S. Remember the multiplication of congruences
• December 8th 2011, 06:24 PM
MonroeYoder
Re: Divisibility problem
you can factor $(n^k-1)$ into $(n-1)(1+n+n^2+\ldots +n^{k-1})$