Fermat's Little Theorem has a very nice proof ...

Take is prime and . (You have already stated that does not divide ).

You can easily prove that (a basic proof by contradiction should do the trick).

Hence it must be the case that .

You can then collect the terms and observe that .

From this it follows that as required

Hope that helps

Paul