Sum of quotient of Euler phi functions

Let $$n$$ divide $$c$$. I would like to find a closed form for the expression $$\sum_{k \mid c} \frac{\varphi(kn)}{\varphi(k)},$$ where $$\varphi$$ is the Euler phi function. Because $$n$$ divides $$c$$, it is not always the case that $$\varphi(kn)=\varphi(k)\varphi(n)$$, so we cannot simplify it that way. The method I attempted was to use the product formula $$\varphi(k) = k \prod_{p \mid k} \left(1-\frac{1}{p}\right).$$ The sum can be rewritten as \begin{align} \sum_{k \mid c} \frac{\varphi(kn)}{\varphi(k)} &= \sum_{k \mid c} \frac{kn \prod_{p \mid kn} \left(1-\frac{1}{p}\right)}{k \prod_{p \mid k} \left(1-\frac{1}{p}\right)} \\ & = n \sum_{k \mid c} \prod_{\substack{p \mid n \\ p \not\mid k}} \left(1-\frac{1}{p}\right). \end{align}

I wasn't able to do much with this, though. How can either expression be simplified?

• Look at $\prod_{p | n} (1+f_c(p) (1-p^{-1}))$ – reuns Jun 27 at 17:52
• Should the last product be indexed by $p\mid kn$ instead of $p\mid n$? – Servaes Jun 27 at 17:55
• @Servaes The primes that divide $k$ appear in both the numerator and denominator, so I cancelled the corresponding terms. The last product is over primes dividing $n$ but not $k$. – Travis Dillon Jun 27 at 19:34
• You are right; I was thinking of all divisors, not just prime divisors. – Servaes Jun 27 at 20:28
• Are you the Travis that wrote an article about polydivisible numbers in Parabola? I did a breadth-first search for each base, and checked up to base 36, and there are no new ones. Thanks to your observation that digits alternate in parity, I have sped up my search and am going to continue with 38 today. – Madness Aug 24 at 15:18

Given $$c,n$$ with $$n\mid c,$$ you can define the above sum as $$f(c,n).$$ Now, if $$c,d$$ are relatively prime, and $$n\mid c,m\mid d$$ we can show relatively easily that $$f(cd,mn)=f(c,n)f(d,m).$$

So we can reduce to the case $$f(p^a,p^b)$$ with $$b\leq a$$ and $$p$$ prime.

But $$f(p^a,p^b)=\sum_{i=0}^{a}\frac{\phi(p^{b+i})}{\phi(p^i)}=\phi(p^b)+\sum_{i=1}^a p^{b}=\phi(p^b)+ap^{b}$$

This gives $$f(p^a,p^b)=\begin{cases}a+1&b=0\\(a+1)p^b-p^{b-1}&b>0\end{cases}$$

So, if $$c=p_1^{a_1}\cdots p_j^{a_j}$$ and $$n=p_1^{b_1}\cdots p_j^{b_j}$$ then $$f(c,n)=\prod_{i=1}^{j} f\left(p_i^{a_i},p_i^{b_i}\right)=\tau(c)\prod_{p_i\mid n}\left(p_i^{b_i}-\frac{p_i^{b_i-1}}{a_i+1}\right)$$

Where $$\tau(c)$$ is the number of positive divisors of $$c,$$ which is $$\tau(c)=(a_1+1)\cdots(a_j+1).$$

This gives the inequality:

$$\tau(c)\phi(n)\leq f(n,c) \leq \tau(c) n$$