Доказательство по индукции.
База. 
![$[\frac{1}{1}]+[\sqrt{1}]=2\equiv 0$ $[\frac{1}{1}]+[\sqrt{1}]=2\equiv 0$](https://dxdy-04.korotkov.co.uk/f/3/8/4/384663fb75292b32a305dc123512165182.png)
(все сравнения идут по модулю

, если не оговорено иное)
Переход. Пусть утверждение верно для

, т. е.
![$[\frac{n}{1}] + \dots + [\frac{n}{n}] + [\sqrt{n}] \equiv 0$ $[\frac{n}{1}] + \dots + [\frac{n}{n}] + [\sqrt{n}] \equiv 0$](https://dxdy-03.korotkov.co.uk/f/6/d/9/6d9ed1313d6d667718ec320bea5ea5e382.png)
А нам нужно доказать
![$[\frac{n+1}{1}]+\dots+[\frac{n+1}{n}]+[\frac{n+1}{n+1}]+[\sqrt{n+1}] \equiv 0$ $[\frac{n+1}{1}]+\dots+[\frac{n+1}{n}]+[\frac{n+1}{n+1}]+[\sqrt{n+1}] \equiv 0$](https://dxdy-02.korotkov.co.uk/f/d/f/8/df8a4a19a70a49b28e057358b9d8d25482.png)
Посмотрим, что произойдет при переходе к

. Заметим, что
![$[\frac{n}{m}]\neq[\frac{n+1}{m}]$ $[\frac{n}{m}]\neq[\frac{n+1}{m}]$](https://dxdy-04.korotkov.co.uk/f/7/d/5/7d5a3f2de1fe8849bb20687c1f0dde5e82.png)
возможно только в случае

В этом случае слагаемое увеличивается на

. Всего тогда к сумме прибавится

(где

- кол-во положительных делителей

).

появился потому, что не был задействован делитель

(в исходной сумме из утверждения для

его нет). Еще к сумме добавилось слагаемое
![$[\frac{n+1}{n+1}]=1$ $[\frac{n+1}{n+1}]=1$](https://dxdy-04.korotkov.co.uk/f/f/9/0/f903d5c6171d177401544f95db5cb5ee82.png)
. И наконец, могло изменится последнее слагаемое, это возможно только если

- точный квадрат. Тогда разберем два случая:
1. 
-
не точный квадрат.
Тогда нужно доказать, что

Это очень легкое утверждение: если

делится на какое-то число

и

, то

делится на

, причем

(иначе число

было бы квадратом). То есть у каждого делителя числа есть пара, причем одно из этих чисел всегда строго меньше

, другое - строго больше. Таким образом, если мы будем перебирать все делители меньше

, мы всегда будем находить сразу пару делителей. То есть число делителей четно.
2. 
- точный квадрат.
Теперь нужно, наоборот

То же самое, что и в предыдущем случае, только один делитель

не будет иметь пары - это

:

. И количество делителей получается нечетным.