Two Identities on Number Theory

425 Views Asked by At

$$\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.

2

There are 2 best solutions below

6
On BEST ANSWER

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.

2
On

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.$$