Теорема Лагранжа о сумме четырёх квадратов

Теорема Лагранжа о сумме четырёх квадратов утверждает, что Всякое натуральное число можно представить в виде суммы четырех квадратов целых чисел. Доказательство теоремы предоставляет собой алгоритм, позволяющий находить такое представление для числа N с помощью O(N2log2N) арифметических операций.
 Теорема является решением проблемы Варинга для степени n=2. Поскольку числа вида 4m(8n+7),m,n=0,1,2, не представимы суммой трёх квадратов, то теорема Лагранжа даёт одно из двух известных значений функции Харди G(2)=4.

Примеры



  \{begin\{align\}
  \texttt   3 \&= 1\^2 + 1\^2 + 1\^2 + 0\^2\{\{ \\\texttt  31 \&= 5\^2 + 2\^2 + 1\^2 + 1\^2\{\{\\\texttt 310 \&= 17\^2 + 4\^2 + 2\^2 + 1\^2.
 \{end\{align\}

История


 Утверждение теоремы впервые появилось в Арифметике Диофанта, переведённой на латынь Баше в 1621 году. Важную для теоремы лемму о том, что произведение сумм четырёх квадратов есть сумма четырёх квадратов доказал Эйлер, который был близок к доказательству самой теоремы и много сделал лично для Лагранжа. Однако Лагранж опередил Эйлера и доказал теорему в 1770 году.