First, start easy, say , a prime. Then , but by Fermat's little theorem. Thus, . Thus, certainly .
We can now prove this for prime powers. If it means using what we just proved it means , continuing we arrive at . Thus, certainly .
We will show now that if for two distinct primes then it works too, more specifically or . Say, . Then it means . Using the above results it means and . If the order of mod is the argument is complete, similarly if the order of mod is the argument is complete. Thus, we can assume the order of mod and is not . But since it means the order must be (since the order divides ). Similarly since it means the order of must be . But since and it means (by properties of orders) that . But this is impossible, for then and which would imply which is impossible.
Now we can generalize this for for three distinct primes. WLOG say . If then . By using the above results it means and . If the order of mod or or is then the proof is complete, i.e. . Thus it is safe to assume that the order of mod any of those primes is greater than . Thus, the order of mod or is , WLOG say , but then which is impossible since we said .
The last paragraph easily shows how we can generalize this argument for for distinct primes by using induction.
Thus, now we know it works for prime powers and distinct primes. We can think of as a product of distinct primes and prime powers. This is the final step that remains.