2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Из теории чисел
Сообщение08.11.2017, 13:12 
Аватара пользователя


26/11/14
754
Доброго всем времени суток. Решаю задачу: К трёхзначному натуральному числу $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$? Или можно как-то сократить перебор?

 Профиль  
                  
 
 Re: Из теории чисел
Сообщение08.11.2017, 14:18 
Заслуженный участник


16/02/13
4105
Владивосток
А если попробовать китайскую теорему? Там вариантов-то поменьше.

 Профиль  
                  
 
 Re: Из теории чисел
Сообщение08.11.2017, 14:42 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
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$. Остальные аналогично + два тривиальных, есть и другие способы. Единица, впрочем, Вам не подходит.

 Профиль  
                  
 
 Re: Из теории чисел
Сообщение08.11.2017, 19:00 
Аватара пользователя


26/11/14
754
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$ ? Почему квадратов восемь? Когда решал по китайски натыкался на эти уравнения, но откуда они здесь? Может это какое-то следствие из китайской теоремы?

 Профиль  
                  
 
 Re: Из теории чисел
Сообщение08.11.2017, 19:04 
Заслуженный участник


20/08/14
11069
Россия, Москва
Stensen в сообщении #1263522 писал(а):
Почему квадратов восемь?
Потому что лишь 8 чисел меньше $1001$ при возведении в квадрат дают остаток $1$ при делении на $1001$.

 Профиль  
                  
 
 Re: Из теории чисел
Сообщение08.11.2017, 20:53 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
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$ решается разложением в непрерывную дробь.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Mikhail_K, tolstopuz


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group