Какие числа из одних троек являются суммой двух квадратов?

[gipokrat]

Найдите все числа вида 33…3, которые можно представить в виде суммы двух точных квадратов.

[ex-math]

Суммой двух квадратов представляются те и только те числа, в разложение которых все простые вида $4n-1$ входят в четных степенях. Ваша последовательность - это утроенные репьюниты так что надо смотреть разложение репьюнитов. Очевидное необходимое условие - число разрядов должно быть кратно трём. Из первых чисел подходит только 333. Если число разрядов вдобавок четно, то такие числа делятся на 11, но не на 121, а значит не подходят (впрочем если, например, 22 разряда, то и на 121 будет делиться - надо ещё подумать). А вот если число разрядов делится на 3 и нечетно, то там закономерности как будто нет и непонятно как быть.

[lel0lel]

ex-math в сообщении #1729659 писал(а):

впрочем если, например, 22 разряда

Число разрядов должно быть кратно трём, чтобы само число было кратно девяти. Пусть $n=a^2+b^2$. Так как $3\mid n$, то, рассматривая по модулю $3$, получается, что и $a$, и $b$ кратны 3. Сокращая $n$ на девять: $37\cdot 100100100...1001$. Второй множитель сравним с единицей по модулю 4. Остаётся вопрос о его представимости суммой квадратов, то есть, числа $(10^{3k}-1)/999$.

[ex-math]

Так я то же самое и написал. Число разрядов кратно трём, и даже скорее имеет вид $6k+3$, но дальше упираемся в факторизацию и результат неясен.

[lel0lel]

ex-math в сообщении #1729693 писал(а):

Так я то же самое и написал

Да, моя невнимательность.

[wrest]

ex-math в сообщении #1729659 писал(а):

Суммой двух квадратов представляются те и только те числа, в разложение которых все простые вида $4n-1$ входят в четных степенях.

Тогда имеем следующее.
Все репьюниты, начиная с 11, дают остаток 3 при делении на 4. Это следует из того, что репьюнит с $k$ единицами это $R_k=\dfrac{10^k-1}{9}$ - тут числитель даёт остаток 3 от деления на 4 начиная с $k=2$ (т.к. 100 делится на 4), а 9 даёт остаток 1.

Таким образом, в разложение на простые множители любого репьюнита обязательно входит хотя бы одно простое $p=4n+3$ в нечётной степени.

Если это простое $p \ne 3$, то и в разложение $N=3R_k$ оно входит в нечётной степени - тогда $N$ не представимо суммой квадратов.

Допустим, что наше простое $p=3$ вошло в репьюнит $R_k$ в нечётной степени.

Выше показано, что $k$ должно быть кратно 3:

ex-math в сообщении #1729659 писал(а):

Очевидное необходимое условие - число разрядов должно быть кратно трём.

Положим $k=3t$ и посмотрим на репьюнит $R_{3t}$

$R_{3t}=\dfrac{10^{3t}-1}{9}$

вспомним, что $a^3-1=(a-1)(a^2+a+1)$

То есть, $10^{3t}-1=(10^t-1)(10^{2t}+10^t+1)$

Запишем
$R_{3t}=\dfrac{10^{3t}-1}{9}=\dfrac{(10^t-1)(10^{2t}+10^t+1)}{9}=\dfrac{10^t-1}{9}\cdot (10^{2t}+10^t+1)$
То есть $R_{3t}=R_tQ_t$ где $Q_t=10^{2t}+10^t+1$

Это было так же сделано тут:

lel0lel в сообщении #1729680 писал(а):

Сокращая $n$ на девять: $37\cdot 100100100...1001$. Второй множитель сравним с единицей по модулю 4. Остаётся вопрос о его представимости суммой квадратов, то есть, числа $(10^{3k}-1)/999$.

Рассмотрим $Q_t=10^{2t}+10^t+1$
Это число, очевидно делится на 3, т.к. все слагаемые дают остаток 1
Но оно ре делится на 9, т.к. все слагемые дают остаток 1 и следовательно $Q_t \equiv 3 \mod{9}$
Значит, тройка входит в разложение $Q_t$ в степени 1 (нечётной).

Но тогда тройка не может являться "плохим делителем", и наше предположение

Цитата:

Допустим, что наше простое $p=3$ вошло в репьюнит $R_k$ в нечётной степени.

неверно.

Значит, мы всегда имеем случай

Цитата:

Если это простое $p \ne 3$, то и в разложение $N=3R_k$ оно входит в нечётной степени - тогда $N$ не представимо суммой квадратов.

[lel0lel]

wrest в сообщении #1729730 писал(а):

Но тогда тройка не может являться "плохим делителем", и наше предположение

Разрешите напишу немного другими словами.

Нужно показать, что число $(10^{3k}-1)/3$ при $k>1$ не представимо суммой двух квадратов. Разность кубов даёт $(10^k-1)\cdot(10^{2k}+10^k+1)/3$. Здесь оба множителя целые и взаимнопростые. Кроме того, оба множителя при $k>1$ сравнимы с $3$ по модулю $4$. Следовательно, в разложении числа $(10^{2k}+10^k+1)/3$ есть простое вида $4m+3$ в нечётной степени и, при этом, такого простого нет у числа $10^k-1$. Поэтому число $(10^{3k}-1)/3$ представимо суммой квадратов только при $k=1$. Итого: единственное число из одних троек, которое представимо, это $333$.

[wrest]

lel0lel в сообщении #1729756 писал(а):

Разрешите напишу немного другими словами.

Спасибо! Мне никак не залезала в голову очевидность взаимной простоты множителей, но теперь я её увидел

[ex-math]

wrest
У вас непонятное рассуждение. Ну допустим репьюнит делится на 3 в первой степени, и что? И чем выделен случай 333?
lel0lel
Очень красиво, спасибо!

[wrest]

ex-math в сообщении #1729760 писал(а):

У вас непонятное рассуждение. Ну допустим репьюнит делится на 3 в первой степени, и что?

С непонятностью согласен, объяснять долго :) У lel0lel очень ясно написано. Он же делит второй множитель на 3 и сразу становится ясно, что тут и сказке конец. Ну может надо былотпару слов добавить о взаимной простоте, но вроде бы и очевидна она. А я не догадался это сделать.

.

-- добавлено через 10 минут --

ex-math в сообщении #1729760 писал(а):

И чем выделен случай 333?

Он выделен тем, что

wrest в сообщении #1729730 писал(а):

Все репьюниты, начиная с 11, дают остаток 3 при делении на 4.

А при разложении $R_{3t}=R_tQ_t$ при $t=1$ имеем $R_3=R_1Q_1$ это не так, ибо получается
$R_{3\cdot 1}=\dfrac{10^1-1}{9}(10^2+10+1)$ и первый множитель (дробь $R_1=\dfrac{10^1-1}{9}$) равен единице - даёт остаток 1 от деления на 4, а не 3 как все последующие репьюниты начиная с $R_2=11$.

[ex-math]

wrest
Нет, я понял вас так, что вы предполагаете, что в $R_{3t}$ тройка входит в нечетной степени. И как-то получаете противоречие. Из чего делаете вывод, что значит другое простое вида $4n-1$ входит в нечетной степени в $R_{3t}$, а значит и в наше число. Но как получается противоречие - непонятно. Да оно и не может получиться, потому что 3 вполне в нечетной степени бывает в репьюнитах.

[wrest]

ex-math
Там немножко запутанней, прошу ещё раз прощения за это.
Сперва я говорю, что в любом репьюните $R_k$ есть простое вида 4n+3 в нечётной степени.
Тут два случая - это простое тройка и не тройка.
Если это тройка, то она умножится на три (т.к. нас интересуют числа $3\cdot 111\dots 11$) и станет входить в исследуемые числа $333\dots 33$ в чётной степени, что не дает нам ответа.
Дальше я разлагаю репьюнит $R_k=R_{3t}=R_tQ_t$ и выясняется что тройка обязательно входит в разложение $Q_t$ в нечётной степени. Но тогда она должна входить в $R_t$ в чётной степени (или нулевой), при том, что мы выяснили, что в любом репьюните есть какое-то простое вида 4n+3 в нечётной степени, значит в $R_t$ оно тоже есть и это простое - не тройка (вот тут и возникает противоречие).

[ex-math]

wrest
Нет, всё-таки не выходит. Простое есть в $R_t$, но оно может быть и в $Q_t$. Так что без апелляции к взаимной простоте не получается

[wrest]

ex-math в сообщении #1729798 писал(а):

Нет, всё-таки не выходит. Простое есть в $R_t$, но оно может быть и в $Q_t$. Так что без апелляции к взаимной простоте не получается

Конструкция $R_{3t}=R_tQ_t$ интересует нас только по вопросу: может ли быть так, что единственное простое вида $4k+3 $ в нечётной степени в $R_{3t}$ ("плохое простое") это тройка. Если это невозможно, и там всегда (для $t>1$) есть какое-то ещё плохое, то задача не имеет решений при $t>1$ и вопрос закрыт. И вот выясняется, что это не только тройка, потому что как в $R_{3t}$ так и в $R_t$ должно быть какое-то плохое простое. Тройка в нечётной степени всегда есть в $Q_t$ (это установлено), но тогда, если бы тройка была единственным плохим простым в $R_{3t}$, то в $R_t$ она обязана была бы быть в чётной степени и стала бы "хорошим", а мы установили что в любом $R_t$ есть "плохое" простое, и значит это не только тройка.

[ex-math]

wrest
Извините, наверно со стороны выглядит, что я занудствую. Но если вы нашли "плохое" простое, не равное 3, в $R_t$, это не значит, что оно останется "плохим" в $R_{3t}$, так как умножение на $Q_t$ может сделать степень этого простого чётной. Поэтому без явного использования взаимной простоты $R_t$ и $Q_t$ рассуждение не проходит.