Ahoj,
Xarezmi
V.V. уже писал, что достаточно рассмотреть по модулю 8. Правая часть сравнима с 6 по модулю 8, а сумма квадратов может быть сравнима только с 0,1,2,4 и 5.
А вот предложенный Вами вариант

показался интереснее. Рванул было считать, ... ошибся, исправляюсь: сходу только сведение получается.
Факторизуем: 2006=2*17*59. Далее пользуемся спуском: если x^2 + z^2 делится на простое

, то

и

оба делятся на

... Здесь думал и конец, ан нет.
Можно ещё по двойке спуститься, но это ничего не даст. В итоге двух спусков получится лишь сведение к уравнению:
Похоже сейчас придёт Ольга и скажет:
- Ой, извините, я просто случайно 2006 дважды набрала.
