# How to prove $n$ is prime?

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?

• What does $\left $\dfrac{a}n\right$$ mean?
– user17762
May 10, 2013 at 19:38
• Is this possible? Looks like the LHS is always 1 and the RHS is always greater than 2. May 10, 2013 at 19:42
• @NarutSereewattanawoot: So since the assumption is always false, the conclusion follows whenever the assumption holds. ☺ May 10, 2013 at 19:52
• @N.S. It was 1 before the OP edited it. May 10, 2013 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.

• Empty of any defects. +1 May 10, 2013 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. May 10, 2013 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$

• 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)$. May 10, 2013 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)$. May 11, 2013 at 15:26