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.

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

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.

  • $\begingroup$ Empty of any defects. +1 $\endgroup$ – mrs May 10 '13 at 20:04
  • 2
    $\begingroup$ 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. $\endgroup$ – 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 $

  • $\begingroup$ 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)$. $\endgroup$ – N. S. May 10 '13 at 20:53
  • $\begingroup$ 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)$. $\endgroup$ – N. S. May 11 '13 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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