Totient-like function 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? UPDATE: 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?

Let $n > 1$, and let $d < n$ be a positive divisor of $n$. You want to count the number of elements of the set $$ A = \\{ a : 0 \le a < n, \gcd(a, n) = d \\}. $$ Note that if $a \in A$, then $\gcd\left(\dfrac{a}{d}, \dfrac{n}{d}\right) = 1$, so $\dfrac{a}{d} \in B$, where $$ B = \left\\{ b : 0 \le b < \frac{n}{d}, \gcd\left(b, \frac{n}{d}\right) = 1 \right\\}, $$ and $B$ has $\varphi(n/d)$ elements. Conversely, if $b \in B$, then $b d \in A$, as $$ \gcd(b d, n) = \gcd \left(b d, \frac{n}{d} d \right) = \gcd \left( b, \frac{n}{d} \right) d = d. $$

So $A$ has $\varphi(n/d)$ elements.