I have number written as factors for instance: n = 2 * 3 * 3 * 5. What I have to do is find how many numbers between <1, n) are co-prime to n, which means GCD = 1. It can simply be done using Euler's Totient. But what if GCD = 2 or more? Is there any totient-like function?
I seeking how many numbers between ai = <1, n) will return GCD(ai,n) = 2. For GCD(ai, n) = 1. It's Euler Totient, what about higher GCD's?