Как представить произвольное число суммой квадратов.

[Побережный Александр]

Теорема Пифагора позволяет представить квадрат числа через сумму квадратов.
А есть ли алгоритм позволяющий произвольное натуральное число больше 2 представить в виде суммы квадратов?
А если такой алгоритм существует, то можно ли одно и тоже число представить несколькими способами?

[Dragon27]

Однёрки - квадраты однёрок.

А если без единиц, то как представить, например, число 3 в виде суммы квадратов?

[Побережный Александр]

Вынужден уточнить: меня интересует представление натурального числа в виде суммы двух квадратов.

[gris]

не в своё дело лезу, ну да ладно.
Таких пар можно много напридумывать: $1^2+8^2=4^2+7^2$. Если приравнять две суммы двух квадратов, потом посмотреть на разности, разложить число на два сомножителя несколькими способами...
Если квадратов только два, то не всякое число можно разложить в подобную сумму.
Если квадратов сколько угодно, то всякое.
Вы, наверное, имели в виду не теорему Пифагора, а формулу для пифагоровых троек.

[Побережный Александр]

Видимо снова некорректно выразился.
Пример: число $13=3^2+2^2$ или $74=7^2+5^2$.
Можно ли известное натуральное число представить суммой двух квадратов?

[Dragon27]

Вам же уже сказали - не всякое.

[Побережный Александр]

Что не всякое я и так знаю. Меня интересует алгоритм, чтобы это можно было определить.

[gris]

Может быть тут есть подобное?
http://dxdy.ru/topic5700.html

[VAL]

Натуральное число представляется суммой двух натуральных квадратов тогда и только тогда, когда в его каноническое разложение не входят простые числа вида $4k+3$ в нечетных степенях.
Простые числа вида $4k+1$ и двойка представляются в виде суммы двух квадратов единственным способом.
То что у составных имеется более одного представления легко понять из следующих простых соображений:
Пусть $a=x^2+y^2 , \ b=z^2+t^2$.
Тогда $ab=(xz+yt)^2+(xt-yz)^2=(xz-yt)^2+(xt+yz)^2$.

[apriv]

VAL в сообщении #569452 писал(а):

То что у составных имеется более одного представления легко понять из следующих простых соображений:
Пусть $a=x^2+y^2 , \ b=z^2+t^2$.
Тогда $ab=(xz+yt)^2+(xt-yz)^2=(xz-yt)^2+(xt+yz)^2$.

Было бы преступлением не сообщить, что это называется «модуль произведения комплексных чисел равен произведению их модулей».

[VAL]

apriv в сообщении #569487 писал(а):

VAL в сообщении #569452 писал(а):

То что у составных имеется более одного представления легко понять из следующих простых соображений:
Пусть $a=x^2+y^2 , \ b=z^2+t^2$.
Тогда $ab=(xz+yt)^2+(xt-yz)^2=(xz-yt)^2+(xt+yz)^2$.

Было бы преступлением не сообщить, что это называется «модуль произведения комплексных чисел равен произведению их модулей».

И сколько мне светит по этой (кстати, какой?) статье?

[Побережный Александр]

VAL в сообщении #569452 писал(а):

Натуральное число представляется суммой двух натуральных квадратов тогда и только тогда, когда в его каноническое разложение не входят простые числа вида $4k+3$ в нечетных степенях.
Простые числа вида $4k+1$ и двойка представляются в виде суммы двух квадратов единственным способом.
То что у составных имеется более одного представления легко понять из следующих простых соображений:
Пусть $a=x^2+y^2 , \ b=z^2+t^2$.
Тогда $ab=(xz+yt)^2+(xt-yz)^2=(xz-yt)^2+(xt+yz)^2$.

Ваша информация очень убедительна, но вопрос состоял в нахождении алгоритма поиска такого разложения в сумму двух квадратов. Ведь вы и $a$ и $b$ должны тоже представить в виде суммы двух квадратов. Понятное дело, если знаем как разложить и $a$ и $b$, то сможем разложить и их произведение.
К примеру, как разложить на сумму двух квадратов число 1001 без перебора?

[bot]

Побережный Александр в сообщении #569600 писал(а):

К примеру, как разложить на сумму двух квадратов число 1001 без перебора?

Никак

VAL в сообщении #569452 писал(а):

Натуральное число представляется суммой двух натуральных квадратов тогда и только тогда, когда в его каноническое разложение не входят простые числа вида $4k+3$ в нечетных степенях

$1001=7\cdot 11\cdot 13$

[Побережный Александр]

Согласен, серьезное замечание! Тогда другой пример, разложить на сумму двух квадратов число $1261=13\cdot97$ без перебора.

[Sonic86]

Я точно не знаю, но вот такое нашел:
В Бухштабе есть способ представления числа $N$ квадратичной формой (в том числе формой $x^2+y^2$), но для его работы надо уметь решать сравнение $t^2\equiv -1\pmod N$. Алгоритм решения сравнений $t^2\equiv a \pmod p$ для простого $p$ есть в Василенко Теоретико-числовые методы в криптографии. Значит, наверное, надо делать так: факторизовать $N$, затем раскладывать каждое простое в сумму квадратов с помощью решения сравнения в $\mathbb{Z}_p$, а потом разложения комбинировать.

А еще в Гэри Джонсоне я нашел, что к уравнению $ax^2+by=c$ для $a,b,c>0$ сводится задача 3-выполнимости, что не утешает