Полная система вычетов

[rightways]

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

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

[Sonic86]

Прикольная задача. Здесь работает бесконечный спуск (превращаемый в индукцию). Натуральность $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$ тривиально.

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

[whitefox]

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

Как только на каком-то шаге получим $d_j=0$

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

[Sonic86]

whitefox в сообщении #1075408 писал(а):

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

Как только на каком-то шаге получим $d_j=0$

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

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

[iifat]

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

$v=\varphi(n): v|a^v-1, 0<v<n$

А вот это, не поясните, откуда? Если это намёк на Малую Ферма, то там, помнится, $n|a^v-1$.

[Sonic86]

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

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

$v=\varphi(n): v|a^v-1, 0<v<n$

А вот это, не поясните, откуда? Если это намёк на Малую Ферма, то там, помнится, $n|a^v-1$.

Упс, да, опечатка. Исправил. Спасибо! (а теорема вроде называлась теоремой Эйлера)

[rightways]

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

[Sonic86]

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

[Null]

$r=t,k\neq m$

[Sonic86]

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

$r=t,k\neq m$

изначально предполагается, что $k\neq m$, а относительно $r,t$ не предполагается ничего.

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

[Null]

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

[Sonic86]

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

Если $r=t$ у вас нет противоречия.

Если $r=t$, то $a^k\equiv a^m \pmod n$ и тогда $k=m$, а $k\neq m$. Но я забыл это дописать. Допишу.

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

И вообще вы могли сразу $d=1$ брать.

Тут пока думаю...

[Null]

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$. Это моя ошибка.

[Sonic86]

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$

[vorvalm]

$a^n\equiv 1 \pmod n \;\Rightarrow a\equiv 1\pmod n\;\Rightarrow a^n+n\equiv n+1\pmod n;$
при $n=p$