Thread: Number Theory View Single Post
P: 258
 Quote by popitar How do I check it?
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 $$(n-1)^2|n^k-1$$:

proof:

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

it is $$(n-1)^{2-1}\cdot \varphi{(n-1)}=(n-1)\cdot \varphi{(n-1)}$$

now, by euler, as $$gcd(n-1,\ n)=1$$ then

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

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

notice that $$\varphi{(n-1)}<n-1<k$$, and by hipothesis n-1|k

EDIT: conclusion is: therefore $$n^k\equiv\ 1\ mod\ (n-1)^2$$