Пусть n² + 1 делится на 1000001. Тогда n² + 1 = k 1000001, где k - целое число.
n² = k 1000001 - 1 = 1000001 * (k-1) + 1000000.

Заметим, что 1000001 = 11 91 101. Пусть n не делится ни на 11, ни на 91, ни на 101. Тогда n² сравнимо с 1000000 по модулю каждого из этих чисел. Так как n² сравнимо с 1000000 модулю 1000001, то n² сравнимо с 1000000 модулю НОК(11, 91, 101, 1000001) = 1000001. Значит, n сравнимо с 1000 по модулю 1000001.

Таким образом, n равномерно распределено по остаткам при делении на 1000001.

Если найдется такое n, что n делится на 1000001, то n² + 1 обязательно не будет делиться на 1000001. Это значит, что среди чисел 1, 2, ..., 1000000 будет 1000000/2 = 500000 чисел, для которых n² + 1 делится на 1000001.