On $\lfloor\sqrt n \rfloor+ \sum_{j=1}^n \lfloor n/j\rfloor$

Question

How do we prove that $\Big[\sqrt n \Big]+ \sum_{j=1}^n \bigg[ \dfrac nj\bigg]$ is an even integer for all $ n \in \mathbb N$ ? (where $\Big[ \space \Big]$ denotes the "greatest integer" function)

Answer 1

$\left[\frac{n}{j}\right]$ is the number of positive integers $k$ such that $k\cdot j \leqslant n$. Thus

$$\sum_{j=1}^n \left[\frac{n}{j}\right] = \sum_{j\cdot k \leqslant n} 1 = \sum_{m = 1}^n \left(\sum_{j\cdot k = m} 1\right) = \sum_{m=1}^n \tau(m),$$

where $\tau(m)$ is the number of divisors of $m$. Every positive integer that is not a perfect square has an even number of divisors, while a perfect square has an odd number of divisors. There are $\left[\sqrt{n}\right]$ perfect squares $\leqslant n$. Hence

$$\sum_{j=1}^n \left[\frac{n}{j}\right] \equiv \left[\sqrt{n}\right] \pmod{2}.$$