Представим число n в виде 3k+a, где k-некоторое целое число, а число a принимает значения 1 и 2 - остатки от деления n на 3, если n не кратно 3.
Тогда 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.