Задача на теорию сравнений

[Unconnected]

Решаю по модулю 11 сначала:
(снижаем основание)

$9^{35^{42^{43}}} \equiv x (\mod 11)$ // надеюсь, так можно делать

$9^{10} \equiv1(\mod 11)$
Ищем теперь остаток деления "башни" на 10.
$35^{42^{43}}\equiv y(\mod 10)$
По очевидным соображениям, $y \equiv 5$
Значит, $9^{5} \equiv x (\mod 11)$
Возводим обе части в квадрат: $9^{10} \equiv x^{2} (\mod 11)$ , т.е. $x \equiv +-1 (\mod 11)$

Это верно?

[bot]

Как это может быть верным? Сколько может быть остатков?

Наказание неотвратимо: В квадрат возвел - получи посторонние корни.
Проще 9 заменить на -2.

[Unconnected]

В каком плане сколько остатков?
-1 лишний корень там значит.

//это не полное решение, а только по одному модулю, проба пера)

[Unconnected]

10й раз перерешиваю, всё ответ не тот..( Может, нельзя основание степени так уменьшать? Хотя в произведении простом можно, $10x\equiv3(\mod 7)$ эквивалентно $3x\equiv 3(\mod 7)$

[Sonic86]

Блин, что там сложного:

$a^{b^{c^{d}}} \equiv (a \mod m)^{(b \mod \varphi (m))^{(c \mod \varphi (\varphi (m)))^{(c \mod \varphi (\varphi (\varphi (m))))}}} \pmod m$

-- Пт ноя 25, 2011 14:45:34 --

Unconnected в сообщении #507873 писал(а):

Может, нельзя основание степени так уменьшать?

Можно.

[Unconnected]

А почему неправильно решение выше по модулю 11? Мне бы очевидным способом научиться..

[bot]

А кто говорит, что неправильно? Возведение в квадрат было лишним, что естественно привело к постороннему решению и потребовало отсечения.
Проще было из $x\equiv 9^5\pmod{11}$ сразу получить $x\equiv -2^5\pmod{11}$, откуда $x\equiv 1\pmod{11}$

А вот где там у Вас и зачем появляется модуль 7, совсем не понимаю.

[Unconnected]

Модуль 7 это просто пример приводил. В общем, нашёл ошибку, чертова невнимательность.. Спасибо за поддержку)