Ботал что-то как обычно и наткнулся опять на данную задачу:
Докажите что любое простое число вида 4k+1 представимо в виде суммы двух квадратов
Пункт шел со звездочкой и решения поэтому не приводилось. Заниматься олимпиадами перестал давно, но помню что в свое время брали утверждение просто за данность. Не знает ли кто олимпиадного решения(о красоте наверное не стоит 
) ну или хотя бы ссылки на решение?
Заранее всем спасибо)
там в доказательстве какой-то ужас творится
Для доказательства, нам понадобится одна лемма
Лемма 1. Для любого p = 4k +1, \exist m \in \mathbb N : p \mid m^2 + 1
Доказательство:
Достаточно положить m = ((p-1)/2)!
Заметим что
m^2 = (1 \ast 2 \ast \ldots \ast ((p-1)/2))^2 = (1 \ast 2 \ast \ldots \ast ((p-1)/2)) \ast ((p-1) \ast (p-2) \ast \ldots \ast ((p+1)/2) = (p-1)! \pmod p
Но по теорема Вильсона p \mid (p-1)! + 1 \implies p \mid m^2 + 1 Лемма доказана
Перейдем к решению
Рассмотрим всевозможные целые пары (s,t): 0 \leq s, t \leq \lfloor \sqrt p \rfloor
Несложно, понять что их количество равно (\lfloor \sqrt p \rfloor + 1 )^2 > (\sqrt p)^2 = p
По лемме 1 существует m: p \mid m^2 + 1
Рассмотрим числа вида s + mt их более p штук, тогда по принципу Дирихле
\exist s_1, s_2, t_1, t_2 : s_1 + mt_1 \equiv s_2 + mt_2 \pmod p так как остатков \pmod p ровно p штук
\iff s_1 - s_2 \equiv m(t_2 - t_1) \implies (s_1 - s_2)^2 \equiv m^2(t_2 - t_1)^2 \equiv -(t_2 - t_1)^2
\implies p \mid (s_1 - s_2)^2 + (t_1 - t_2)^2
Но вспомним что 0 \leq s, t \leq \lfloor \sqrt p \rfloor \implies (s_1 - s_2)^2 + (s_2 - t_2)^2 \leq 2\lfloor \sqrt p \rfloor^2 < 2p ,
а также (s_1, t_1) \neq (s_2, t_2) \implies (s_1 - s_2)^2 + (s_2 - t_2)^2 > 0
Тогда p \mid (s_1 - s_2)^2 + (s_2 - t_2)^2 при этом 0 < (s_1 - s_2)^2 + (s_2 - t_2)^2 < 2p
\implies (s_1 - s_2)^2 + (s_2 - t_2)^2 = p при этом (s_1 - s_2)^2, (s_2 - t_2)^2 \in \mathbb N Теорема доказана