Are you asking to prove Euler's theorem? Do you know group theory? Note that forms a group whose order is and since any element of a group to it's order is the identity element the conclusion follows.

If you're just trying to apply it merely notice that if then by virtue of 's primality in which case Fermat's theorem applies. If then either in which case the theorem is a triviality.