2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Задача про делимость
Сообщение22.11.2022, 00:57 
Заслуженный участник
Аватара пользователя


26/01/14
4601
Эту олимпиадную задачу я придумал много лет назад, когда сам был школьником.
Я её нигде больше не встречал, но вполне допускаю, что она может оказаться хорошо известной или даже классической. С задачами на делимость я в целом не очень хорошо знаком.
Как бы вы стали её решать? Возможно, моё решение слишком экзотическое, хотя и простое.

Пусть $k,l\in\mathbb{N}$, $k\geq 2$. Докажите, что найдутся такие целые неотрицательные $m>n$, что число $k^m-k^n$ делится на $l$.

 Профиль  
                  
 
 Re: Задача про делимость
Сообщение22.11.2022, 01:18 


20/04/10
1776
$k^n(k^{m-n}-1)$
Если $k,l$ взаимнопростые, то выберем $m-n=\varphi(l)$. Если $(k,l)=d<l$, то, возможно, что $l=td^s$, $s\geq 1$ и $k=ud$, причём $(t,u)=1$. В таком случае положим $n=s$, $m-s=\varphi(t)$.

 Профиль  
                  
 
 Re: Задача про делимость
Сообщение22.11.2022, 01:33 
Заслуженный участник
Аватара пользователя


26/01/14
4601
lel0lel в сообщении #1570803 писал(а):
В таком случае положим $n=s$, $m-s=\varphi(t)$
Верно ли я понимаю, что Вы используете здесь теорему Эйлера и взаимную простоту $k$ и $t$?
Но, кажется, $k$ и $t$ не обязательно взаимно просты.

 Профиль  
                  
 
 Re: Задача про делимость
Сообщение22.11.2022, 01:39 
Заслуженный участник
Аватара пользователя


16/07/14
8341
Цюрих
Я чего-то не понимаю, видимо. Среди чисел $k^1, k^2, \ldots, k^{l + 1}$ у хотя бы двух одинаковые остатки по модулю $l$, их разность на $l$ делится.

 Профиль  
                  
 
 Re: Задача про делимость
Сообщение22.11.2022, 01:42 


20/04/10
1776
Да. Мы предварительно, выбрав $m$ сократили в $l$ всё то, что мешало взаимной простоте $k, l$. Поэтому $k,t$ взаимнопростые

 Профиль  
                  
 
 Re: Задача про делимость
Сообщение22.11.2022, 01:48 
Заслуженный участник
Аватара пользователя


26/01/14
4601
mihaild в сообщении #1570809 писал(а):
Среди чисел $k^1, k^2, \ldots, k^{l + 1}$ у хотя бы двух одинаковые остатки по модулю $l$, их разность на $l$ делится.

:facepalm: Да, не получилось из меня автора олимпиадной задачи. Конечно, Вы правы.
lel0lel в сообщении #1570812 писал(а):
Да. Мы предварительно, выбрав $m$ сократили в $l$ всё то, что мешало взаимной простоте $k, l$. Поэтому $k,t$ взаимнопростые
Не думаю. Если $k=12$, $l=18$, то $d=6$, $t=3$ и $k,t$ не взаимно просты.

 Профиль  
                  
 
 Re: Задача про делимость
Сообщение22.11.2022, 01:58 


20/04/10
1776
Mikhail_K в сообщении #1570814 писал(а):
Если $k=6$, $l=18$, то $d=6$, $t=3$ и $k,t$ не взаимно просты.
Да, стоило поаккуратнее, но в целом почти очевидно, что выбрав большое $m$, после сокращения от $l$ остаётся либо единичка, либо взаимнопростое число с $k$.

 Профиль  
                  
 
 Re: Задача про делимость
Сообщение22.11.2022, 02:23 
Заслуженный участник
Аватара пользователя


26/01/14
4601
Моё школьное доказательство основывалось на представлении числа $1/l$ в виде периодической дроби в $k$-ичной системе счисления и использовании формулы суммы бесконечной геометрической прогрессии.
Жаль, что у задачи нашлось гораздо более простое решение.

 Профиль  
                  
 
 Re: Задача про делимость
Сообщение23.11.2022, 11:05 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
С тех пор, как эта задача стала важна для приложений, школьники стали встречаться с ней в довольно раннем возрасте.

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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