# 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?

• "...If GCD=2..." of whom ? – DonAntonio May 25 '13 at 15:27
• @DonAntonio: The OP is asking for the function counting the numbers $k$ with $1\leq k\leq n$ for which $\gcd(k,n)=2$. – Zev Chonoles May 25 '13 at 15:32
• I think he means how many numbers m<n are there so that GCD(n,m)=2 or 3 or... – CODE May 25 '13 at 15:32
• Yes, that seems to be so, Zev...perhaps. – DonAntonio May 25 '13 at 15:32
• You can use Inclusion-Exclusion principle.. – Inceptio May 25 '13 at 15:46

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.
• @Kostek, $\varphi(7/2)$ makes no sense, Euler's function is only defined for integers. And I am only considering the case when $d$ divides $n$, otherwise $\gcd(a, n) = d$ has no solution $a$. – Andreas Caranti May 25 '13 at 15:50