I was exploring some sum when I came across this sum which I have no idea the value, here is the sum

Let $ N $ be an integer with the prime decomposition $ N = p_1^{k_1} p_2^{k_2} ... p_m^{k_m} $.

Let $ a $ be another integer such that $ 0 < a < N $. Consider the sum

\begin{align} \sum_{1 \leq i \leq m} \left \{ \frac{a}{p_i} \right \} - \sum_{1 \leq i < j \leq m} \left \{ \frac{a}{p_i p_j} \right \} + ... + (-1)^m \left \{ \frac{a}{p_1 p_2 ... p_m} \right \} \end{align} where $ \{ x \} = x - \lfloor x \rfloor $ is the factional part function.

I did some numerical calculations and found that the sum is generally small. For some values of $ a $, the sum may get large, but its absolute value seems to be bounded by $ m - 1 $, where $ m $ is the number of distinct prime factors of $ N $ as above.

My question is, is there currently a known formula/estimate/bound (in terms of $ a $ and $ N $) for the sum above?

(Realize that I did not really phrase the original question that well, so I edited some part of the post)

  • $\begingroup$ Looks mighty like an error term in some formula for the quantity of numbers below $a$ and coprime to $N$. $\endgroup$ Jul 5, 2017 at 14:44
  • $\begingroup$ Yes, pretty close actually, I could only get a rough bound so far. $\endgroup$ Jul 5, 2017 at 15:57

2 Answers 2


First observation: the fractional part of the result stays the same if you take the fractional part at the end (only the whole part may change).

Second observation: taking the fractional part of a quotient is the same as taking the remainder of division.

You can rewrite this as

$$\sum \frac{a\mod p_i}{p_i}-\sum \frac{a \mod p_i p_j}{p_i p_j}+\cdots$$

Now observe what happens when you keep adding one more prime to the set of primes $p_i$. With a single prime it's trivial. Adding more, it starts looking like you'll be able to use the Chinese Remainder Theorem once you take them to the common denominator. Can you continue?

  • $\begingroup$ I don't see what you mean. $\endgroup$
    – reuns
    Jul 5, 2017 at 15:11
  • $\begingroup$ I see, this does give a way to evaluate if we know the value of a and N. What if we are only given a general N? (Note that I have rephrase the original post) $\endgroup$ Jul 5, 2017 at 15:59

For $n \ge 1$ look at $\mu(n)$ the Möbius function, $\text{Lpf}(n), \text{lpf}(n)$ the largest and least prime factor of $n$.

For a given $M = p_m$ and $a$ your sum is

$$-\sum_{n\ge \color{red}{2}} \mu(n) 1_{\text{Lpf}(n) \le M} \left(\frac{a}n-\left\lfloor \frac{a}n \right\rfloor \right)$$

  • Since $\displaystyle \frac{\mu(n)1_{\text{Lpf}(n) \le M}}{n}$ is multiplicative we have the Euler product $$\sum_{n\ge 1} \frac{\mu(n)1_{\text{Lpf}(n) \le M}}{n} = \prod_{p} (1+\sum_{k \ge 1} \frac{\mu(p^k)1_{\text{Lpf}(p^k) \le M}}{p^k}) = \prod_{p \le M} \left(1-\frac{1}{p}\right)$$

  • Then we look at the other sum

$$\sum_{n \ge 1} \mu(n)1_{\text{Lpf}(n) \le M} \left\lfloor \frac{a}n \right\rfloor = \sum_{n \le a, r \le a/n} \mu(n)1_{\text{Lpf}(n) \le M} = \sum_{r \le a} \sum_{n | r} \mu(n)1_{\text{Lpf}(n) \le M} = \sum_{r \le a} 1_{\text{lpf}(r) > M}$$ With the convention $1_{\text{lpf}(1) > M} = 1$, and I used that $ \sum_{n | r} \mu(n)1_{\text{Lpf}(n) \le M}$ is multiplicative to deduce it is $ = 1_{\text{lpf}(r) > M}$

Overall you get

$$-\sum_{n\ge \color{red}{2}} \mu(n) 1_{\text{Lpf}(n) \le M} \left(\frac{a}n-\left\lfloor \frac{a}n \right\rfloor \right)= a-\lfloor a\rfloor - a\prod_{p \le M} \left(1-\frac{1}{p}\right)+ \sum_{r \le a} 1_{\text{lpf}(r) > M}$$

And I don't see any good reason for it being small in general. The first sum can be approximated with the Mertens theorem, and the second one is trivial when $M \ge a$.

  • $\begingroup$ May I know how you get the first sum? $\endgroup$ Jul 6, 2017 at 14:03
  • $\begingroup$ @Humourprince This is the definition of the Möbius function $\mu(\prod_{i=1}^j p_i) = (-1)^j$ and $\mu(p^2 n) = 0$ $\endgroup$
    – reuns
    Jul 6, 2017 at 17:08
  • $\begingroup$ But having the term $ 1_{Lpf (n)} \leq M $ means you add in extra primes that are less than $ M = p_m $ and not equal to one of the $ p_i $, i.e. do not divide $ N $, do they actually cancel out? $\endgroup$ Jul 7, 2017 at 12:50
  • $\begingroup$ @Humourprince Then for a set of primes $S$ with complementary $S^\perp$ and $e^S,e^{S^\perp}$ the integers they generate, replace $p \le M, Lpf(n) \le M,lpf(r) > M$ by $p \in S, r \in e^S, n \in e^{S^\perp}$. $\endgroup$
    – reuns
    Jul 7, 2017 at 13:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .