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

Теорема Лагранжа о сумме четырёх квадратов утверждает, чтоВсякое натуральное число можно представить в виде суммы четырехквадратов целых чисел. Доказательство теоремы предоставляет собойалгоритм, позволяющий находить такое представление для числа 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 году.