The result is actually stronger, it goes that: .

Where, .

We will prove this by induction.

When there is nothing to prove.

So say that, .

We will prove it for .

Here is a useful result: if *.

With this result we get, .

However, ... [1]

Here is another result: if then divides .**

Thus every term in sum of [1] for is divisble by notice that .

Therefore, each term for is divisible by . For the last term ( ) in sum of [1] we have . But since . And so we have shown that divides each term for in the sum of [1]. Thus, the sum is equivalent to 0 mod .

Thus, .

*)Argue by induction. If it means for some . Now raise both sides to the power and apply the binomial theorem again. I think the result that appears in ** (just below) will be useful in this proof.

**)Because is an integer, since for we have that divides . Thus, it leaves a factor of . Thus, divides .

------

We can now prove a stronger result. That the order of is mod . Where .

Okay we have shown . This implies, . But, (use binomial theorem). However, since . The rest follows.