Олимпиадная математика, 6 класс.

Элементарно.
Случай, когда n делится на 3, очевиден.
Если же n не делится на 3, то на 3 делится число n^2 – 1 = (n – 1)*(n + 1), поскольку одно из чисел n – 1, n + 1 делится на 3. Следовательно, в этом случае n^2 + 1 ≡ 2 (mod 3) (для особо тупых: остаток от деления числа n^2+1 на 3 равен 2).