Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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.$$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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