7
$\begingroup$

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.

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

2 Answers 2

12
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Empty of any defects. +1 $\endgroup$
    – Mikasa
    May 10, 2013 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, 2013 at 20:48
3
$\begingroup$

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 $

$\endgroup$
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, 2013 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, 2013 at 15:26

You must log in to answer this question.

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