2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Как представить произвольное число суммой квадратов.
Сообщение10.05.2012, 16:26 
Теорема Пифагора позволяет представить квадрат числа через сумму квадратов.
А есть ли алгоритм позволяющий произвольное натуральное число больше 2 представить в виде суммы квадратов?
А если такой алгоритм существует, то можно ли одно и тоже число представить несколькими способами?

 
 
 
 Re: Как представить произвольное число суммой квадратов.
Сообщение10.05.2012, 16:33 
Однёрки - квадраты однёрок.

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

 
 
 
 Re: Как представить произвольное число суммой квадратов.
Сообщение10.05.2012, 16:38 
Вынужден уточнить: меня интересует представление натурального числа в виде суммы двух квадратов.

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

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

 
 
 
 Re: Как представить произвольное число суммой квадратов.
Сообщение10.05.2012, 16:55 
Вам же уже сказали - не всякое.

 
 
 
 Re: Как представить произвольное число суммой квадратов.
Сообщение10.05.2012, 17:10 
Что не всякое я и так знаю. Меня интересует алгоритм, чтобы это можно было определить.

 
 
 
 Re: Как представить произвольное число суммой квадратов.
Сообщение10.05.2012, 17:18 
Аватара пользователя
Может быть тут есть подобное?
http://dxdy.ru/topic5700.html

 
 
 
 Re: Как представить произвольное число суммой квадратов.
Сообщение10.05.2012, 17:26 
Натуральное число представляется суммой двух натуральных квадратов тогда и только тогда, когда в его каноническое разложение не входят простые числа вида $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$.

 
 
 
 Re: Как представить произвольное число суммой квадратов.
Сообщение10.05.2012, 20:32 
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$.

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

 
 
 
 Re: Как представить произвольное число суммой квадратов.
Сообщение10.05.2012, 20:47 
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$.

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

 
 
 
 Re: Как представить произвольное число суммой квадратов.
Сообщение11.05.2012, 10:28 
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 без перебора?

 
 
 
 Re: Как представить произвольное число суммой квадратов.
Сообщение11.05.2012, 10:45 
Аватара пользователя
Побережный Александр в сообщении #569600 писал(а):
К примеру, как разложить на сумму двух квадратов число 1001 без перебора?
Никак
VAL в сообщении #569452 писал(а):
Натуральное число представляется суммой двух натуральных квадратов тогда и только тогда, когда в его каноническое разложение не входят простые числа вида $4k+3$ в нечетных степенях
$1001=7\cdot 11\cdot 13$

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

 
 
 
 Re: Как представить произвольное число суммой квадратов.
Сообщение11.05.2012, 11:57 
Я точно не знаю, но вот такое нашел:
В Бухштабе есть способ представления числа $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-выполнимости, что не утешает :-(

 
 
 [ Сообщений: 17 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group