I am trying to prove a little modification on Euler's theorem

, for all a, and where n is the product of two distinct primes say p and q.

I am having problems with the for all a part as the above is easy to show.

I need to show that if q or p is a factor of a, then it still yields the same result, as Euler's theorem says that the gcd(a, n) must be 1. But I am not sure how to show that in the modification it doesn't matter. Any ideas?

Thanks!