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?

  • 1
    $\begingroup$ Look at $\prod_{p | n} (1+f_c(p) (1-p^{-1}))$ $\endgroup$ – reuns Jun 27 at 17:52
  • $\begingroup$ Should the last product be indexed by $p\mid kn$ instead of $p\mid n$? $\endgroup$ – Servaes Jun 27 at 17:55
  • 1
    $\begingroup$ @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$. $\endgroup$ – Travis Dillon Jun 27 at 19:34
  • $\begingroup$ You are right; I was thinking of all divisors, not just prime divisors. $\endgroup$ – Servaes Jun 27 at 20:28
  • $\begingroup$ 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. $\endgroup$ – 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$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.