N^2+8=(3k+a)^2+8=9k^2+6ak+a^2+8=3(3k^2+2ak)+a^2+8.
Видно, что 3(3k^2+2ak) делится на 3. Докажем, что a^2+8 тоже делится на 3.
При a=1 a^2+8=9 делится на 3.
При a=2 a^2+8=12 делится на 3.
Следовательно, вся сумма делится на 3, если n не делится на 3.
Чёт тип такого...