Из теории чисел

[Stensen]

Доброго всем времени суток. Решаю задачу: К трёхзначному натуральному числу $x=\overline{abc}$ дописали его же, а к полученному числу прибавили 1 и получили точный квадрат. Найдите все такие числа.

Т.к.: $x=\overline{abc}=100a+10b+c $ , тогда:

$\overline{abcabc}+1=10^5a+10^4+10^3c+100a+10b+c +1=1001(100a+10b+c)+1=k^2$ , где: $k \in\mathbb{N}$ , отсюда видно, что: $317 \leqslant k \leqslant 1000$ , тогда:

$1001(100a+10b+c)=k^2 - 1 =(k-1)(k+1)$ или

$7\cdot 11 \cdot 13 \cdot x=(k-1)(k+1)$ . Отсюда видно, что : $(k-1)(k+1) \, \vdots \, 7 \cdot 11 \cdot 13$ . А дальше ступор. Неужели нужно тупо перебрать все $317 \leqslant k \leqslant 1000$ в этом диапазоне и проверить делимость $k^2-1$ на $1001$? Или можно как-то сократить перебор?

[iifat]

А если попробовать китайскую теорему? Там вариантов-то поменьше.

[Andrey A]

Stensen в сообщении #1263382 писал(а):

Неужели нужно тупо перебрать все $317 \leqslant k \leqslant 1000$ в этом диапазоне...

$k^2\equiv 1\mod1001.$ Все такие квадраты (их ровно восемь $<1001$) вычисляются однозначно и вовсе не тупо. Например так: решить уравнение $7\cdot 11x-13y=\pm 1$. Тогда $k_1=7\cdot 11x+13y;\ k_2=1001-k_1$. Остальные аналогично + два тривиальных, есть и другие способы. Единица, впрочем, Вам не подходит.

[Stensen]

iifat в сообщении #1263415 писал(а):

А если попробовать китайскую теорему? Там вариантов-то поменьше.

Решил по китайски, получил: $k^2= 2003 \equiv 1 (\bmod 1001) $ вроде с этого и начинал. Что делать дальше, пояснил Andrey A:

Andrey A в сообщении #1263430 писал(а):

$k^2\equiv 1\mod1001.$ Все такие квадраты (их ровно восемь $<1001$) вычисляются однозначно и вовсе не тупо. Например так: решить уравнение $7\cdot 11x-13y=\pm 1$. Тогда $k_1=7\cdot 11x+13y;\ k_2=1001-k_1$. Остальные аналогично + два тривиальных, есть и другие способы. Единица, впрочем, Вам не подходит.

но не понимаю, откуда взялись эти уравнения, что такое $k_1, k_2$ ? Почему квадратов восемь? Когда решал по китайски натыкался на эти уравнения, но откуда они здесь? Может это какое-то следствие из китайской теоремы?

[Dmitriy40]

Stensen в сообщении #1263522 писал(а):

Почему квадратов восемь?

Потому что лишь 8 чисел меньше $1001$ при возведении в квадрат дают остаток $1$ при делении на $1001$.

[Andrey A]

Stensen в сообщении #1263522 писал(а):

что такое $k_1, k_2$

$k_1,k_2$ это пара возможных решений задачи, которую Вы свели к нахождению квадратов, сравнимых с единицей по модулю $1001$. Одно из решений уравнения $7\cdot 11x-13y=\pm 1$ для примера такое: $x=1,y=6$. Из него получаем $7\cdot 11\cdot 1+13\cdot 6=155$. $k_1=155,k_2=1001-155=846$. Второе подходит по величине: $(846^2-1)/1001=715.$ Отсюда $715715+1=846^2$.
Китайская теорема имеет, конечно, отношение к делу, но это слишком общий случай. Нахождение квадратов, сравнимых с единицей по заданному модулю - отдельная стандартная задача. Обоснование тут такое: если $77x-13y=1$, то $77x=13y+1$, $13y=77x-1$.
Тогда $k=77x+13y=77x+77x-1=13y+1+13y=2\cdot 77x-1=2\cdot 13y+1. Т.е. $(k+1)\ \vdots\ 77,\ (k-1)\ \vdots\ 13$ и $(k^2-1)\ \vdots\ 1001.$ Уравнение $ax-by=1$ решается разложением в непрерывную дробь.