0
$\begingroup$

$\sum_{d|n}f\left(\frac{x}{d},\frac{n}{d}\right)=[x],\quad f(x,n)=\sum_{d|n}\mu(d)\left[\frac{x}{d}\right]$ Let $f(x,n)$ be the number of integers less than or equal to $x$ and prime to $n$.

It seems that we could obtain the second one from the first one by the inversion formula, but I couldn't prove both of them.

  • 0
    @DimitrijeKostic Yes, it represents the largest integer not exceeding x.2011-11-21

2 Answers 2

2

Hint. For $d \mid n$, let $N_d$ denote the number of positive integers $k \leqslant x$ such that $\gcd(k, n) = d$. Prove the following pair of identities:

$f \left(\frac{x}{d}, \frac{n}{d} \right) = N_d \quad \text{ for all } d \mid n . \tag{1}$

$\sum \limits_{d \mid n} N_d = \lfloor x \rfloor . \tag{2}$

Plugging in these two observations gives the first identity. As the OP already notes, the second identity then follows by Möbius inversion. EDIT: I don't know how to obtain the second identity. (Thanks to Greg.)

Hint for $(1)$. Suppose $k \leqslant x$ is such that $\gcd(k, n) = d$. This is equivalent to the pair of conditions:

  • $d \mid k$.
  • $\gcd(\frac{k}{d}, \frac{n}{d}) = 1$.

That is, we can write $k$ as $k = d \cdot \ell$ such that $\gcd(\ell, \frac{n}{d}) = 1$; also, clearly, $\ell \leqslant \frac{x}{d}$. Thus there is a one-to-one correspondence between $\{ k \leqslant x \mid \gcd(k,n) = d \}$ and $\{ \ell \leqslant \frac{x}{d} \mid \gcd(\ell,\frac{n}{d}) = 1 \}$. Thus the number of such $k$ is equal to $f(\frac{x}{d}, \frac{n}{d})$.

Hint for $(2)$. We have $ \lfloor x \rfloor = \sum_{k \leqslant x} 1 = \sum_{d \mid n} \ \sum_{\stackrel{k \leqslant x}{\gcd(k, n) = d}} 1, $ where we have split the sum according to $\gcd(k,n)$, $k$ being the index.

  • 0
    @Srivatsan Both of them I guess...2011-11-21
4

I replace your $f$ by $\varphi$ for convenience. Notice that $\varphi(n,n)=\varphi(n)=\sum^{n}_{k=1} \ \sum_{d \mid (n,k)} \mu(d),$ we have $\varphi(x,n)=\sum^{\lfloor x \rfloor}_{k=1} \ \sum_{d \mid (n,k)} \mu(d).$ From this we get $\varphi(x,n)=\sum_{d \mid n}\sum^{\lfloor x/d \rfloor}_{q=1}\mu(d)=\sum_{d \mid n}\mu(d)\sum^{\lfloor x/d \rfloor}_{q=1}1=\sum_{d \mid n}\mu(d)\left \lfloor \frac{x}{d} \right \rfloor.$

  • 1
    @Kou: I'm not 100% sure of the details, but a _hint_ would be to look at the sum $\sum_{d \mid n} \varphi(d)=\sum_{d \mid n} \varphi(n/d)=n$.2011-11-21