Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Let $n \gt 1$ and $$\left\lfloor\frac n 1\right\rfloor + \left\lfloor\frac n2\right\rfloor + \ldots + \left\lfloor\frac n n\right\rfloor = \left\lfloor\frac{n-1}{1}\right\rfloor + \left\lfloor\frac{n-1}{2}\right\rfloor + \ldots + \left\lfloor\frac{n-1}{n-1}\right\rfloor + 2$$ and $\lfloor \cdot \rfloor$ is the floor function. How to prove that $n$ is a prime?

Thanks in advance.

share|cite|improve this question
What does $\left \[\dfrac{a}n\right \]$ mean? – user17762 May 10 '13 at 19:38
Is this possible? Looks like the LHS is always 1 and the RHS is always greater than 2. – Narut Sereewattanawoot May 10 '13 at 19:42
@NarutSereewattanawoot: So since the assumption is always false, the conclusion follows whenever the assumption holds. ☺ – Harald Hanche-Olsen May 10 '13 at 19:52
@N.S. It was 1 before the OP edited it. – Narut Sereewattanawoot May 10 '13 at 19:59
up vote 12 down vote accepted

You know that

$$\left( \left\lfloor\frac n 1\right\rfloor - \left\lfloor\frac{n-1}{1}\right\rfloor \right)+\left( \left\lfloor\frac n2\right\rfloor - \left\lfloor\frac{n-1}{2}\right\rfloor\right) + \ldots + \left( \left\lfloor\frac{n}{n-1}\right\rfloor - \left\lfloor\frac{n-1}{n-1}\right\rfloor\right) + \left\lfloor\frac n n\right\rfloor=+2 \,.$$

You know that

$$\left( \left\lfloor\frac n 1\right\rfloor - \left\lfloor\frac{n-1}{1}\right\rfloor \right)=1$$ $$\left\lfloor\frac n n\right\rfloor =1$$ $$\left( \left\lfloor\frac n k\right\rfloor - \left\lfloor\frac{n-1}{k}\right\rfloor\right) \geq 0, \qquad \forall 2 \leq k \leq n-1 \,.$$

Since they add to 2, the last ones must be equal, thus for all $2 \leq k \leq n-1$ we have

$$ \left\lfloor\frac n k\right\rfloor - \left\lfloor\frac{n-1}{k}\right\rfloor = 0 \Rightarrow \left\lfloor\frac n k\right\rfloor = \left\lfloor\frac{n-1}{k}\right\rfloor $$

It is easy to prove that this means that $k \nmid n$. Since this is true for all $2 \leq k \leq n-1$, you are done.

share|cite|improve this answer
Empty of any defects. +1 – Babak S. May 10 '13 at 20:04
I think that in general we have $ \left\lfloor\frac n 1\right\rfloor + \left\lfloor\frac n2\right\rfloor + \ldots + \left\lfloor\frac n n\right\rfloor = \left\lfloor\frac{n-1}{1}\right\rfloor + \left\lfloor\frac{n-1}{2}\right\rfloor + \ldots + \left\lfloor\frac{n-1}{n-1}\right\rfloor + d$ where $d$ is the number of divisors of $n$...This seems to be provable exactly the same way. – N. S. May 10 '13 at 20:48

i have a question if i define the function $ \sigma (x)= \sum_{n=1}^{x}d $ and 'd' is the function divisor isn't the problem $ \sigma(x)=\sigma(x-1)+2 $

share|cite|improve this answer
You are right this is a nice solution. $\lfloor \frac{n}{k} \rfloor$ counts how many numbers between $1$ and $n$ are multiple of $k$. Reordering you get exactly $\sum_{i=1}^n d(i)$. – N. S. May 10 '13 at 20:53
To make it a formal proof: For each of the numbers between $1$ and $n$ list all the divisors. Then there are exactly $\sum_{i=1}^n d(i)$ numbers in the list.... Now, each $k$ appears exactly $\lfloor \frac{n}{k} \rfloor$ times in the list. Thus, there are exactly $\sum_{k=1}^n \lfloor \frac{n}{k} \rfloor$ numbers in the list. Thus $\sum_{k=1}^n \lfloor \frac{n}{k} \rfloor=\sum_{i=1}^n d(i)$. – N. S. May 11 '13 at 15:26

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.