On counting number pairs having a specific greatest common divisor.

61 Views Asked by At

I wanted to count natural numbers $k$ not exceeding the fixed $n \in \mathbb{N}$ and having a greatest common divisor $\gcd(n,k) = d$ naturally for some $d \mid n$. In more mathematical terms: $$ \phi_d(n) = \left| \{\, k \mid 1 \le k \le n,\ \gcd(n,k) = d \,\} \right|. $$

Two obvious cases are $\phi_n(n) = 1$ and $\phi_1(n) = \phi(n)$ - Euler's totient function. I have s strong feeling that I am not the first one who came up with this idea, it's just that "generalization of Euler's $\phi$ function" brings very different results... Do you know any sources?

Let's say it's interesting how the sequences $(\phi_d(n))$ behave. Some semi relevant facts can be easily conceived like $$ \sum_{d \mid n} \phi_d(n) = n. $$ But, for example, maybe for two distinct divisors of $n$ namely $d_1,\ d_2$ the fact $d_1 < d_2$ implies $\phi_{d_1}(n) \ge \phi_{d_2}(n)$ ?