From my previous post here we know that when .

If for some then by Fermat's Little Theorem. Otherwise, for which is not divisible by we get where is the remainder of upon division by . So again we obtain . In conclusion:

For , we have , and otherwise .