Эта сумма равна $1\,000\,009=3^2+1000^2$. Докажем такой общий факт. Если число $m$ вида $4k+1$ ($k$ — натуральное) можно представить в виде суммы двух квадратов не менее чем двумя разными способами, то $m$ — составное.
Пусть
$$m=x^2+y^2=u^2+v^2,\tag1$$
где можно считать числа $x\gt u$ нечётными, а $y\lt v$ — чётными. Тогда наибольший общий делитель чисел $x-u$ и $v-y$ — чётное число; обозначим его $2d$. Пусть
$$x=u-2da,\quad v=y-2db,\tag2$$
где $a$ и $b$ взаимно просты. Подставив выражения (2) в (1), получим после сокращений
$$au+da^2=by+db^2=abc.\tag3$$
Это число делится на $a$ и на $b$, а значит, и на их произведение; частное мы обозначили через $c$. Таким образом, как следует из (3), $u=bc-ad$, $y=ac-bd$, откуда $x=u+2ad=bc+ad$ (здесь $a$, $b$, $c$, $d$ — некоторые натуральные числа) и $$m=x^2+y^2=(bc+ad)^2+(ac-bd)^2=(a^2+b^2)(c^2+d^2).$$
Проделав эти выкладки для данных чисел, нетрудно найти соответствующее разложение и для числа $10^6+9$.
Можно доказать и более сильное утверждение: число $m=4k+1$ простое в том и только в том случае, если оно представляется в виде суммы двух квадратов единственным образом. Эйлер заметил, что этот признак удобен для проверки простоты больших чисел (перебор существенно сокращается, если использовать информацию о том, какие остатки могут давать квадраты при делении на небольшие числа).
