В теории чисел есть такая очень известная очень простая задача:

Для любого простого p>3 доказать, что p^2+2 делится на 3. У этой задачи есть не менее известное (и очень простое и очевидное решение): любое такое простое число имеет вид 3х+1 или 3х+2 для некого натурального х. Теперь для каждого из этих случаев возводим в квадрат сумму, прибавляем двойку и получаем число явно делящееся на 3.

Одна моя зайка сегодня мне нашла решение, которое, к моему стыду, мне в голову не пришло. В зайкином решении не нужно разбивать решение на два случая: p^2+2 сравнимо с p^2-1 по модулю 3, а p^2-1=(р-1)(р+1), причем очевидно, что одно из р+1 и р-1 обязательно делится на 3. Все. Просто и элегантно