al-mahed

this is an implication "if and only if", <==>

I'll do the part <==, then you try to do the part ==>

prove that if n-1|k, then [tex](n-1)^2|n^k-1[/tex]:

proof:

first what is [tex]\varphi{([n-1]^2)}[/tex] ??

it is [tex](n-1)^{2-1}\cdot \varphi{(n-1)}=(n-1)\cdot \varphi{(n-1)}[/tex]

now, by euler, as [tex]gcd(n-1,\ n)=1[/tex] then

[tex]n^{\varphi{([n-1]^2)}}=n^{(n-1)\cdot \varphi{(n-1)}}\equiv\ 1\ mod\ (n-1)^2[/tex]

and by Lagrange we know that either [tex]k=(n-1)\cdot \varphi{(n-1)}[/tex] or [tex]wk=(n-1)\cdot \varphi{(n-1)}[/tex]

notice that [tex]\varphi{(n-1)}<n-1<k[/tex], and by hipothesis n-1|k

EDIT: conclusion is: therefore [tex]n^k\equiv\ 1\ mod\ (n-1)^2[/tex]