My teacher once said, for any positive number $\ n, $ $\ n^k - 1 $ would always have $\ n-1 $ as a factor for all positive odd values of $\ k $. Could anyone tell me the proof? I have written my approach below.

Assuming $n-1$ to be a factor.

$n^k - 1 = (n-1)x $

$n^k = (n-1)x + 1 $

$k = \lg( (n-1)x + 1 ) / \lg (n) $ 

If my approach is right could you tell me where should I go from here?

Edit : [This](https://math.stackexchange.com/questions/188657/why-an-bn-is-divisible-by-a-b) clears my doubt.

Edit 2 : My question is "why for any positive number $\ n, $ $\ n^k + 1 $ would always have $\ n+1 $ as a factor for all positive odd values of $\ k $ ".