Сравнимы $\mod n$

[xmaister]

Доказать, что для $n>2$
$\underbrace{2^{2^{.^{.^2}}}}\limits_{n\text{штук}}\equiv \underbrace{2^{2^{.^{.^2}}}}\limits_{n-1\text{штук}}\mod n$.

[bnovikov]

xmaister в сообщении #499170 писал(а):

Доказать, что для $n>2$
$\underbrace{2^{2^{.^{.^2}}}}\limits_{n\text{штук}}\equiv \underbrace{2^{2^{.^{.^2}}}}\limits_{n-1\text{штук}}\mod n$.

Индукцией, индукцией!

[Sonic86]

Гы! Прикольно!
Вообще утверждение слабовато будет. Хотя если брать $2^a \equiv 2^b \pmod {m} \Leftarrow a \equiv b \pmod {\varphi (m)}$, то для индукции будет достаточно лишь $\varphi (m) < m$, в то время как $\varphi (m)$ сразу будет четное, откуда $\varphi ( \varphi (m)) \leqslant \frac{\varphi (m)}{2}$, откуда получаем, что башня степеней будет содержать не более $[\log _2 n]+2$ элементов, иначе ее уже можно урезать.

[Sonic86]

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

Хотя если брать $2^a \equiv 2^b \pmod {m} \Leftarrow a \equiv b \pmod {\varphi (m)}$

Это неверно для четных $m$, так что чтобы описанный метод применять нужно разбивать модуль на степень двойки и нечетное число.