Теория чисел, док-во.

[belo4ka]

Докажите, что существует бесконечно много натуральных чисел, которые нельзя представить в виде суммы квадратов.
1) двух натуральных чисел
2) трех натуральных чисел

У меня была такая идея:
Квадрат натурального числа может оканчиваться на $1,4,6,9,0$. Но уже сумма квадратов двух натуральных чисел может оканчиваться на $0,1,2,3,4,5,6,7,8,9$, то есть это тупиковый вариант.
В какую сторону тут думать, подскажите, пожалуйста.

[Shadow]

Можно ли представить число 3 в виде суммы двух квадратов?
Можно ли представить число 7 в виде суммы трех квадратов?
Думайте в направлении обощения.

[ИСН]

Если это видеть впервые, то оно слишком сложно. С двумя квадратами можно из банальных плотностных соображений (сколько у нас всего квадратов между 1 и $N^2$? а сколько их попарных сумм, если бы даже они все сюда попали?), с тремя так не выйдет.

[belo4ka]

Shadow в сообщении #898715 писал(а):

Можно ли представить число 3 в виде суммы двух квадратов?
Можно ли представить число 7 в виде суммы трех квадратов?
Думайте в направлении обощения.

$3+4n$?

[Xaositect]

belo4ka в сообщении #898713 писал(а):

Квадрат натурального числа может оканчиваться на $1,4,6,9,0$. Но уже сумма квадратов двух натуральных чисел может оканчиваться на $0,1,2,3,4,5,6,7,8,9$, то есть это тупиковый вариант.

С помощью этой идеи можно решить, только рассматривайте остатки не по модулю $10$, а подберите какое-нибудь другое основание.

[gris]

Нвскидку для смеха, а вдруг пройдёт?
Можно подойти со стороны количества. Посмотреть, сколько места занимают суммы квадратов на ограниченном отрезке натуральных чисел.
Скажем, до 20 это $0,1,4,9,16,2,5,10,17,8,13,20,18$ 12 штук. Маловато будет. Ну и как-то это обобщить. Аддитивность сложения на руку.

Ничего себе натолкали, пока писал. И гораздо более умными словами. Плотностные соображения. Надо запомнить.

[belo4ka]

ИСН в сообщении #898718 писал(а):

Если это видеть впервые, то оно слишком сложно. С двумя квадратами можно из банальных плотностных соображений (сколько у нас всего квадратов между 1 и $N^2$? а сколько их попарных сумм, если бы даже они все сюда попали?), с тремя так не выйдет.

между 1 и $N^2$ находится $N-1$ квадратов. А попарных сумм $C_{N-1}^2$?

-- 23.08.2014, 13:48 --

Xaositect в сообщении #898720 писал(а):

belo4ka в сообщении #898713 писал(а):

Квадрат натурального числа может оканчиваться на $1,4,6,9,0$. Но уже сумма квадратов двух натуральных чисел может оканчиваться на $0,1,2,3,4,5,6,7,8,9$, то есть это тупиковый вариант.

С помощью этой идеи можно решить, только рассматривайте остатки не по модулю $10$, а подберите какое-нибудь другое основание.

А какое именно выбрать?

[Nemiroff]

belo4ka в сообщении #898724 писал(а):

А какое именно выбрать?

Подумайте. Вам Shadow подсказал.
Попробуйте четвёрку.

[belo4ka]

Nemiroff в сообщении #898725 писал(а):

belo4ka в сообщении #898724 писал(а):

А какое именно выбрать?

Подумайте. Вам Shadow подсказал.
Попробуйте четвёрку.

По моему числа вида $4n+3$ нельзя представить в виде суммы двух квадратов...

[Nemiroff]

Угу.
Потому что по модулю $4$ квадраты имеют остаток $1$ или $0$. Когда их два, их сумма по модулю $4$ имеет остаток $0$, $1$ или $2$. Вот так все $4n+3$ за бортом и остаются.

[belo4ka]

Nemiroff в сообщении #898734 писал(а):

Угу.
Потому что по модулю $4$ квадраты имеют остаток $1$ или $0$. Когда их два, их сумма по модулю $4$ имеет остаток $0$, $1$ или $2$. Вот так все $4n+3$ за бортом и остаются.

Спасибо, а почему по модулю $4$ квадраты натур. чисел имеют остаток $1$ или $0$? Как это можно доказать можно?

А с суммой трех квадратов такой трюк теперь понятно почему не пройдет. (т.к. сумма трех квадратов по модулю $4$ имеет остаток $0$, $1$ или $2$ или $3$, что не поможет выделить какую-то особенность).
А может там по другому модулю посмотреть или здесь лучше использовать другой подход?

[Nemiroff]

belo4ka в сообщении #898737 писал(а):

Как это можно доказать можно?

Ну не знаю даже.
Нуль в квадрате --- нуль.
Один в квадрате --- один.
Два в квадрате --- четыре, то бишь нуль.
Три в квадрате --- девять, то бишь один.
Четыре в квадрате --- это нуль в квадрате.
Пять в квадрате --- это один в квадрате.
Дальше лень, там еще бесконечно много строчек.

-- Сб авг 23, 2014 15:07:56 --

belo4ka в сообщении #898737 писал(а):

А может там по другому модулю посмотреть или здесь лучше использовать другой подход?

Я бы посмотрел по другому модулю, воспользовавшись подсказкой Shadow.

[belo4ka]

Nemiroff в сообщении #898740 писал(а):

belo4ka в сообщении #898737 писал(а):

Как это можно доказать можно?

Ну не знаю даже.
Нуль в квадрате --- нуль.
Один в квадрате --- один.
Два в квадрате --- четыре, то бишь нуль.
Три в квадрате --- девять, то бишь один.
Четыре в квадрате --- это нуль в квадрате.
Пять в квадрате --- это один в квадрате.
Дальше лень, там еще бесконечно много строчек.

Ахах) Ну это понятно. но разве это можно считать доказательством?)

[Nemiroff]

Вы не осознали? Вы перебираете конечное число вариантов. Чем полный перебор не доказательство?
На самом деле не нужно проверять числа от $4$ и далее --- они по модулю $4$ сводятся к $0,1,2$ или $3$.

[belo4ka]

Натур числа, которые нельзя представить в виде суммы трех квадратов натуральных чисел:

$1,2,4,5,7,8, 10, 13,15,16, 19, 20$ Пока что не вижу закономерности(