Две последние цифры степени, как сэкономить "ручную работу"?

[Xenia1996]

Дана последовательность натуральных чисел:

$n_1=1, n_2=2^{n_1}, n_3=3^{n_2}, \dots , n_m=m^{n_{m-1}}, \dots$

Найти две последние цифры $n_9$

(Решение "вручную")

Моя насчитала 21 У меня вышло 21, но не придумала ничего более умного, чем считать "вручную", по арифмосту (арифметике остатков).

5 в любой степени больше первой дарамдаш 25.

6 дарамдаш 6, 36, 16, 96, 76, 56, и снова 36. Период равен 5 (слава богу, не взаимно прост с 100), а сдвиг равен 1, следовательно $n_6=76 \mod 100$

Аналогично находим $n_7=1 \mod 100$ , $n_8=8 \mod 100$ и , наконец $n_9=21 \mod 100$

Это ещё повезло, что не было периодов, взаимно простых с 100.

Мой вопрос в следующем:

Как можно решить эту задачу не "вручную"?

[spaits]

Вручную: $81$.

[Xenia1996]

spaits в сообщении #422977 писал(а):

Вручную: $81$.

Один из нас ошибся. Полагаю, это - Вы

[spaits]

Xenia1996 в сообщении #423013 писал(а):

Один из нас ошибся. Полагаю, это - Вы

Правильно: $21$.
$n_1=1$; $n_2=2^1=2$; $n_3=3^2=9$; $n_4=4^9=262144=44 (mod100)$; $n_5=5^{44}=25 (mod100)$; $n_6=6^{25}=56(mod100)$; $n_7=7^{56}=01(mod100)$; $n_8=8^1=08(mod100)$; $n_9=9^8=43046721=21(mod100)$.

[Xenia1996]

spaits в сообщении #422977 писал(а):

Вручную: $81$.

Перепроверила себя ещё два раза. Всё равно огурец! 21 получается.

Забила в Альфочку:

$9^{8^{7^{6^{5^{4^{3^{2^1}}}}}}}$

Снова получила 21.

-- Вт мар 15, 2011 00:47:53 --

spaits в сообщении #423023 писал(а):

Xenia1996 в сообщении #423013 писал(а):

Один из нас ошибся. Полагаю, это - Вы

Правильно: $01$.
$n_1=1$; $n_2=2^1=2$; $n_3=3^2=9$; $n_4=4^9=262144=44 (mod100)$; $n_5=5^{44}=25 (mod100)$; $n_6=6^{25}=56(mod100)$; $n_7=7^{56}=01(mod100)$; $n_8=8^1=08(mod100)$; $n_9=9^8=01(mod100)$.

У Вас ошибка на шестом члене. Не 56, а 76.
И на девятом - тоже!

[spaits]

Xenia1996 в сообщении #423025 писал(а):

У Вас ошибка на шестом члене. Не 56, а 76.

Я уже исправила: $21$.
А как "не вручную" считать?

[Xenia1996]

spaits в сообщении #423029 писал(а):

Xenia1996 в сообщении #423025 писал(а):

У Вас ошибка на шестом члене. Не 56, а 76.

Я уже исправила: $21$.
А как "не вручную" считать?

(Оффтоп)

О! Не знала, что Вы - тоже девушка
В таком случае, не "один из нас ошибся", а "одна из нас ошиблась".
И ошибка у Вас была не на шестом члене, а на шестом элементе
Хотя, слово "шестом" всё равно пробуждает ассоциации со словом "шест"...

А как считать не "вручную", у меня мозга не хватает, чтобы сообразить.

[Leox]

(Оффтоп)

Тема в ассоциаций раскрыта не полностью. Странная избирательность.

[Sonic86]

Xenia1996!
Смысл в том, что вычисление по модулю - это очень простая штука. Поскольку Вы уже регулярно с ними сталкиваетесь, я Вам советую прочесть на эту тему хоть что-то. Возьмите хоть Бухштаба Теорию чисел - там это все очень просто написано (можете даже не все главы читать)(есть в Интернете и у меня).
Часть я Вам объясню тут.
Во-первых, если Вы хотите вычислить $a^b \pmod m$, то это очень просто: представляете $b$ в 2-ичной системе счисления и из этого представления все находите с помощью возведения в квадрат и перемножения, причем после каждой арифметической операции берете выражение по модулю. Например по модулю 100 $4^9 \equiv 4^{8+1} \equiv 4 \cdot ((4^2)^2)^2 \equiv 4 \cdot (16^2)^2 \equiv 4 \cdot 256^2 \equiv 4 \cdot 56^2 \equiv 4 \cdot 3136 \equiv 4 \cdot 36 \equiv 144 \equiv 44 \pmod {100}$
Далее, $a^b \equiv a^{b \pmod {L(m)}} \pmod m$, где $L(m)$ - функция Люка. Можете вместо нее брать функцию Эйлера $\varphi (m) = m(1-\frac{1}{p_1})...(1-\frac{1}{p_s})$ для $m=p_1^{a_1}...p_s^{a_s}$, но функция Люка обычно меньше. Функция Люка для нечетных $m$ определяется как $\text{НОК}(p_1^{a_1-1}(p_1-1),...,p_s^{a_s-1}(p_s-1))$ (а для четных она еще меньше, чем это выражение и делит его, но я ее для четных забыл ).
Так вот: $L(100)=\text{НОК}(2 \cdot (2-1),5 \cdot (5-1))=40$, $L(40) = \text{НОК}(4 \cdot (2-1), (5-1))=4$, то есть по модулю 100 уже $a^{b^c} \equiv a^{b^{c \pmod 4} \pmod {40}} \pmod {100}$ и тогда вот эта гигантская башня, которую Вы написали, становится не 9-и, а 3-хэтажной.
Вот
Наконец вот это:

Xenia1996 писал(а):

Это ещё повезло, что не было периодов, взаимно простых с 100.

Это Вам не повезло. Это просто $m$ не взаимно просто с $\varphi (m)$ при четных $m \geq 4$, причем всегда. Попробуйте доказать .
$m$ не взаимно просто с $\varphi (m) \Rightarrow$ $m$ - нечетное, свободное от квадратов + еще несколько жестких условий - очень маловероятное явление...

[kocuHyc]

А как вычислить две первые цифры? Или хотя бы одну?

[Sonic86]

Sonic86 писал(а):

А как вычислить две первые цифры? Или хотя бы одну?

Я пока не знаю

[whitefox]

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

Далее, $a^b \equiv a^{b \pmod {L(m)}} \pmod m$, где $L(m)$ - функция Люка.

Верно только если $a$ взаимнопросто с $m$.
Эта функция более известна как функция Кармайкла $\lambda(n)$, и определяется как экспонента мультипликативной группы целых по модулю $n$.

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

Функция Люка для нечетных $m$ определяется как $\text{НОК}(p_1^{a_1-1}(p_1-1),...,p_s^{a_s-1}(p_s-1))$ (а для четных она еще меньше, чем это выражение и делит его, но я ее для четных забыл ).

Для простых $p$ и положительных целых $k$ таких, что $p\geqslant3$ или $k\leqslant2$:

$$\lambda(p^k)=p^{k-1}(p-1).$$

Для $k\geqslant3$:

$$\lambda(2^k)=2^{k-2}.$$

Для различных простых $p_1,p_2,\dots,p_i$ и положительных целых $k_1,k_2,\dots,k_i$:

$$\lambda(p^{k_1}p^{k_2} \dots p^{k_i})=\text{HOK}(\lambda(p^{k_1}),\lambda(p^{k_2}),\dots,\lambda(p^{k_i})).$$

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

Так вот: $L(100)=\text{НОК}(2 \cdot (2-1),5 \cdot (5-1))=40$

Ошибка: $\text{НОК}(2 \cdot (2-1),5 \cdot (5-1))=20$

Вычислить можно так:
$n_9\bmod100=9^{n_8\bmod20}\bmod100$
$n_8\bmod20=4\cdot(2\cdot3^{(n_7-1)\bmod4}\bmod5)$
$n_7\bmod4=3^{n_6\bmod2}\bmod4$
$n_6\bmod2=6^{n_5}\bmod2=0$
$n_7\bmod4=1$
$n_8\bmod20=8$
$n_9\bmod100=9^8\bmod100=21$

[Sonic86]

Согласен. С ошибками тоже.

[Legioner93]

(Оффтоп)

Знаю, что не в тему совсем, но вычислите 100-ую цифру после запятой числа $(2-\sqrt{3})^{100^2}$

[Sonic86]

(Оффтоп)

0!!