Одно свойство вычетов по модулю 2^n

[diwert]

Пусть $x,y\in\{1,3,5,7,9,\ldots,2^n-1\}$

Доказать что: $x^x\equiv y^y\mod 2^n \Leftrightarrow x\equiv y \mod 2^n$

Вроде бы должно очень просто доказываться. Не найду идею.

[chessar]

diwert в сообщении #637055 писал(а):

$x,y\in\{1,3,5,7,9,\ldots,2^n-1\}$

Это я так понимаю - множество натуральных нечётных чисел до $2^n-1$ включительно?

А при каких вообще $x,y$ может быть выполнено сравнение $x\equiv y\!\pmod{2^n}$ , если $0<x,y<2^n$ ? Очевидно при $x=y$. Так? Или я что-то упустил?

[Sonic86]

ничего себе: $x\to x^x$ - инъекция оказывается...
Проверил для $n\leqslant 6$ - правда.
По индукции пробовали? Т.е. если $x^x\equiv y^y\pmod{2^{n+1}}$, то и $x^x\equiv y^y\pmod{2^n}$ - выражаем, подставляем, упрощаем...

-- Вс окт 28, 2012 18:53:08 --

chessar в сообщении #637074 писал(а):

Очевидно при $x=y$. Так? Или я что-то упустил?

Да, но тут другое просят.

[chessar]

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

Да, но тут другое просят.

Честно говоря не понимаю, что другое тут просят. Вроде бы там знак $\Leftrightarrow$ стоит. Если можете, то сформулируйте задачу иначе.

[Sonic86]

chessar в сообщении #637084 писал(а):

Честно говоря не понимаю, что другое тут просят. Вроде бы там знак $\Leftrightarrow$ стоит. Если можете, то сформулируйте задачу иначе.

Доказать, что все числа $x^x\mod 2^n$ при $x=1;3;...;2^n-1$ различны. $a\mod b$ - операция взятия остатка от $a$ на $b$, где $a,b\in\mathbb{N}$ (поскольку $x,y$ там - не классы вычетов).

[chessar]

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

Доказать, что все числа $x^x\mod 2^n$ при $x=1;3;...;2^n-1$ различны. $a\mod b$ - операция взятия остатка от $a$ на $b$, где $a,b\in\mathbb{N}$ (поскольку $x,y$ там - не классы вычетов).

Всё понял, я только $\Leftarrow$ доказал. Что означает запись $a\mod b$ я знаю и $x,y$ за классы вычетов совсем не принял.

[nnosipov]

diwert в сообщении #637055 писал(а):

Пусть $x,y\in\{1,3,5,7,9,\ldots,2^n-1\}$

Доказать что: $x^x\equiv y^y\mod 2^n \Leftrightarrow x\equiv y \mod 2^n$

Вроде бы должно очень просто доказываться. Не найду идею.

Вот идея: $\mathbb{Z}_{2^n}^*=\langle [-1] \rangle_2 \times \langle [5] \rangle_{2^{n-2}}$ при $n \geqslant 3$. Однако по индукции (см. выше) попроще будет.

[diwert]

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

По индукции пробовали?

Ага, спасибо. Получается, только несколько громоздко. Для $n+1$ приходится отдельно рассматривать случай $y = x + 2^n$.

[nnosipov]

diwert в сообщении #637737 писал(а):

Получается, только несколько громоздко.

Да нет, там в одну строчку.

[diwert]

nnosipov в сообщении #637739 писал(а):

Да нет, там в одну строчку.

Туплю наверно,но в упор не вижу "в одну строчку"

[nnosipov]

Пусть $x^x \equiv y^y \pmod{2^{n+1}}$. По индукции $x=y+2^nm$. Имеем $x^x=(y+2^nm)^{y+2^nm} \equiv (y+2^nm)^y \equiv y^y+2^nmy \pmod{2^{n+1}}$, т.е. $m$ чётно и $x \equiv y \pmod{2^{n+1}}$.

Да, забыл сказать. Лучше доказывать Ваше утверждение в такой форме: если $x$ и $y$ нечётны и $x^x \equiv y^y \pmod{2^n}$, то $x \equiv y \pmod{2^n}$.

[diwert]

Ага так красивее и проще. Спасибо!