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