2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Полная система вычетов
Сообщение20.11.2015, 18:36 


24/12/13
351
Вот такой вот интересный результат из сборов Индии

Натуральные числа $a$ и $n$ таковы, что $n|a^n-1$ .
Докажите, что все числа $a+1,a^2+2,a^3+3,...,a^n+n$ дают различные остатки при делении на $n$ .

 Профиль  
                  
 
 Re: Полная система вычетов
Сообщение21.11.2015, 10:03 
Заслуженный участник


08/04/08
8556
Прикольная задача. Здесь работает бесконечный спуск (превращаемый в индукцию). Натуральность $a$ не нужна, все работает для $a\in\mathbb{Z}$.

Пусть $n:n|a^n-1, n>0$.
Кроме того, $v=\varphi(n): n|a^v-1, 0<v<n$. Значит существует порядок $d:d|a^d-1, 0<d<n$, кроме того $d|n$
Предположим, что есть 2 различных числа $k,m: a^k+k\equiv a^m+m \pmod n$. Разделим их с остатком на $d$:
$k=qd+r, m=sd+t$. (upd: ясно, что если $r=t$, то $a^k\equiv a^m \pmod n$ и тогда $k=m$, а $k\neq m$. Значит $r\neq t$).
Подставим, возьмем сравнение по модулю $d$:
$a^r+r\equiv a^t+t \pmod d$
(upd: Поскольку $r\neq t$, то снова получаем 2 разных числа)
Получается, что если хотя бы 2 числа вида $a^k+k$ совпадают по модулю $n$, то существуют хотя бы 2 числа вида $a^k+k$, которые совпадают по модулю $d:d<n,d|n$. По контрапозиции получаем, что если все числа вида $a^k+k$ по модулю $d$ различны, то все числа вида $a^k+k$ по модулю $n$ различны.
Таким образом, задача для данных $a,n$ свелась к задаче для данных $a,d$, причем $d<n$.
Получаем убывающую последовательность неотрицательных целых $n_j: n_0=n, n_1=d=d_0, d_j=d(n_j)$.
Продолжаем спуск до тех пор, пока $d_j>0$ (upd: ошибка, имелось ввиду $d_j>1$). Как только на каком-то шаге получим $d_j=0$ (upd: конечно же $d_j=1$), это будет означать, что $a\equiv 1\pmod {n_j}$, а в этом случае утверждение о различности чисел $a^k+k$ по модулю $n_j$ тривиально.

Просьба проверить - могу тупить.

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


19/12/10
1546
Sonic86 в сообщении #1075403 писал(а):
Как только на каком-то шаге получим $d_j=0$

$d_j$ это порядок? Который по определению положительное число?

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


08/04/08
8556
whitefox в сообщении #1075408 писал(а):
Sonic86 в сообщении #1075403 писал(а):
Как только на каком-то шаге получим $d_j=0$

$d_j$ это порядок? Который по определению положительное число?
Да, согласен.
Значит надо просто условие выхода из цикла $d_j=0$ заменить на $d_j=1$, на рассуждение это не влияет.
Исправил пост - правки синим цветом.

 Профиль  
                  
 
 Re: Полная система вычетов
Сообщение21.11.2015, 17:42 
Заслуженный участник


16/02/13
4105
Владивосток
Sonic86 в сообщении #1075403 писал(а):
$v=\varphi(n): v|a^v-1, 0<v<n$
А вот это, не поясните, откуда? Если это намёк на Малую Ферма, то там, помнится, $n|a^v-1$.

 Профиль  
                  
 
 Re: Полная система вычетов
Сообщение21.11.2015, 18:00 
Заслуженный участник


08/04/08
8556
iifat в сообщении #1075488 писал(а):
Sonic86 в сообщении #1075403 писал(а):
$v=\varphi(n): v|a^v-1, 0<v<n$
А вот это, не поясните, откуда? Если это намёк на Малую Ферма, то там, помнится, $n|a^v-1$.
Упс, да, опечатка. Исправил. Спасибо! (а теорема вроде называлась теоремой Эйлера)

 Профиль  
                  
 
 Re: Полная система вычетов
Сообщение21.11.2015, 18:13 


24/12/13
351
а можно и так (может быть для некоторых понятнее станет):
фиксируем $a$ и предположим что $n$- наименьшее такое число для которых условие задачи не обязательно выполняется. Тогда находим , что $d<n$ удовлетворяет сравнениям $a^t+t\equiv a^r+r (mod d)$ и $a^d\equiv 1(modd)$ - противоречие тому, что $d$ наименьшее.

 Профиль  
                  
 
 Re: Полная система вычетов
Сообщение21.11.2015, 19:56 
Заслуженный участник


08/04/08
8556
Точно! Так сильно короче. А у меня просто спуск дополнительно развернут.

 Профиль  
                  
 
 Re: Полная система вычетов
Сообщение01.12.2015, 14:37 
Заслуженный участник


12/08/10
1608
$r=t,k\neq m$ :?:

 Профиль  
                  
 
 Re: Полная система вычетов
Сообщение02.12.2015, 08:40 
Заслуженный участник


08/04/08
8556
Null в сообщении #1078577 писал(а):
$r=t,k\neq m$ :?:
изначально предполагается, что $k\neq m$, а относительно $r,t$ не предполагается ничего.

М.б. мне численный пример написать? Рассуждение правда очень простое, Вы сможете из примера все понять.

 Профиль  
                  
 
 Re: Полная система вычетов
Сообщение02.12.2015, 08:42 
Заслуженный участник


12/08/10
1608
Если $r=t$ у вас нет противоречия. И вообще вы могли сразу $d=1$ брать.

 Профиль  
                  
 
 Re: Полная система вычетов
Сообщение04.12.2015, 09:57 
Заслуженный участник


08/04/08
8556
Null в сообщении #1078764 писал(а):
Если $r=t$ у вас нет противоречия.
Если $r=t$, то $a^k\equiv a^m \pmod n$ и тогда $k=m$, а $k\neq m$. Но я забыл это дописать. Допишу.

Null в сообщении #1078764 писал(а):
И вообще вы могли сразу $d=1$ брать.
Тут пока думаю...

 Профиль  
                  
 
 Re: Полная система вычетов
Сообщение04.12.2015, 10:47 
Заслуженный участник


12/08/10
1608
Sonic86 в сообщении #1075403 писал(а):
$a^k\equiv a^m \pmod n$ и тогда $k=m$


Почему?

-- Пт дек 04, 2015 10:50:54 --

Sonic86 в сообщении #1079337 писал(а):
Null в сообщении #1078764

писал(а):
И вообще вы могли сразу $d=1$ брать. Тут пока думаю...


$d=1$ редко является порядком $a \mod n$. Это моя ошибка.

 Профиль  
                  
 
 Re: Полная система вычетов
Сообщение04.12.2015, 13:51 
Заслуженный участник


08/04/08
8556
Null в сообщении #1079351 писал(а):
Sonic86 в сообщении #1075403 писал(а):
$a^k\equiv a^m \pmod n$ и тогда $k=m$


Почему?
$r=t\Rightarrow a^k+k\equiv a^m+m \pmod n , a^d\equiv 1\pmod n\Leftrightarrow$
$a^r+k\equiv a^r+m \pmod n\Leftrightarrow k\equiv m \pmod n$

 Профиль  
                  
 
 Re: Полная система вычетов
Сообщение04.12.2015, 15:10 


31/12/10
1555
$a^n\equiv 1 \pmod n \;\Rightarrow a\equiv 1\pmod n\;\Rightarrow a^n+n\equiv n+1\pmod n;$
при $n=p$

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

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



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

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


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

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