# Two Identities on Number Theory

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

-
Are you trying to show both equalities? And what do the square brackets mean? – Dimitrije Kostic Nov 21 '11 at 4:31
In this context, square brackets generally mean "greatest integer not exceeding." – Gerry Myerson Nov 21 '11 at 4:33
@DimitrijeKostic Yes, it represents the largest integer not exceeding x. – Kou Nov 21 '11 at 4:33

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.

-
Equation (2) is easy. Equation (1) is not too hard either, but if you have trouble in seeing it, then I can elaborate. – Srivatsan Nov 21 '11 at 4:46
You say that the OP's second identity follows from the first by Möbius inversion. I'm not convinced. What form of Möbius inversion are you using? (The usual form has a function of one variable only.) – Greg Martin Nov 21 '11 at 5:43
@Greg You're absolutely right that I am mistaken. I did something in my head and assumed that everything checks out, but that did not work out quite as I expected. Thanks. – Srivatsan Nov 21 '11 at 14:05
@Srivatsan I'm sorry that I still fail to see it, could you explain it in details? Great thanks. – Kou Nov 21 '11 at 14:27
@Kou Please be more specific: see which one? – Srivatsan Nov 21 '11 at 14:29

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

-
Then how to get the first one? – Kou Nov 21 '11 at 15:33
@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$. – Carolus Nov 21 '11 at 15:41