Остаток при делении числа на другое число

[ZumbiAzul]

Здравствуйте, уважаемые форумчане!

Помогите, пожалуйста, решить задачу вида: найти остаток при делении числа $a$ на число $b$, где

1) $a=a_n=7^{7^{7^{...^7}}}, b=13$ (степень возводится в степень $n$ раз). Или, иначе, $a_0=7, a_k=7^{a_{k-1}}, k=1,..,n$.

2) $a=11^{21^{71^{9}}}, b=79$.

[whitefox]

Воспользуйтесь известным соотношением:
$a^b \equiv a^{b\bmod{\lambda(m)}}\pmod m$, где $\lambda(m)$ - функция Кармайкла, а $a$ взаимно просто с $m.$

[ZumbiAzul]

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

Воспользуйтесь известным соотношением:
$a^b \equiv a^{b\bmod{\lambda(m)}}\pmod m$, где $\lambda(m)$ - функция Кармайкла, а $a$ взаимно просто с $m.$

Спасибо, whitefox!

Только все равно не понимаю, как правильно применить написанное вами сравнение. У меня получается просто свойство рефлексивности.

Вот, скажем, рассмотрим 2-ю задачу.

Числа 11 и 79 взаимно просты, следовательно

$$11^b\equiv 11^{b\bmod \lambda(79)}\pmod {79}, $$

$$\lambda(79)=78,$$

т.е.

$$11^b\equiv 11^{b\bmod 78}\pmod {79},$$

где $b$, как я понял любая натуральная степень. Пусть $b=21$, тогда $21\bmod 78 = 21$ и получаем

$$11^{21}\equiv 11^{21}\pmod {79}.$$

Я чувствую, что решение должно состоять из цепочки аналогичных шагов. Не могли бы Вы показать один первый шаг, пожалуйста?

[Sonic86]

ZumbiAzul в сообщении #943119 писал(а):

Пусть $b=21$, тогда $21\bmod 78 = 21$ и получаем

$$11^{21}\equiv 11^{21}\pmod {79}.$$

Во 2-м случае да, придется сначала возводить в степень (необязательно сразу во всю степень, можно частями), а потом брать остаток от деления.
Но Вы не дошли до верхнего этажа. Сначала надо аналогичным ходом добраться до самого верха и потом разрушать башню сверху вниз.

[whitefox]

ZumbiAzul в сообщении #943119 писал(а):

Я чувствую, что решение должно состоять из цепочки аналогичных шагов. Не могли бы Вы показать один первый шаг, пожалуйста?

ZumbiAzul в сообщении #943037 писал(а):

2) $a=11^{21^{71^{9}}}, b=79$.

Пусть $a_1= 21^{71^9}$ тогда $a=11^{a_1}$ и $a\equiv11^{a_1\bmod 78}\pmod{79}.$
И переходим к вычислению $a_1\bmod 78.$
Когда дойдём до самого верха башни -- начинаем спуск вниз.

[ZumbiAzul]

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

тогда $21\bmod 78$

Я ведь правильно понял, что эту запись надо рассматривать как остаток от деления числа 21 на 78? или эта запись обозначает множество чисел, которые при делении на 78 дают в остатке 21 (т.е. чисел, сравнимых с 21 по модулю 78)?

[Sonic86]

ZumbiAzul в сообщении #943154 писал(а):

Я ведь правильно понял, что эту запись надо рассматривать как остаток от деления числа 21 на 78? или эта запись обозначает множество чисел, которые при делении на 78 дают в остатке 21 (т.е. чисел, сравнимых с 21 по модулю 78)?

Множество чисел, которые при делении на $m$ дают в остатке $r$ обозначают обычно $\bar{r}_m$ или $r+m\mathbb{Z}$ (хотя обозначения не настолько общепринятые, ИМХО).
Через $a\mod m$ я (и Вы, видимо, тоже) обозначаю остаток от деления $a$ на $m$ (бинарную операцию), более-менее устойчивого обозначения этого я не видел (погромисты еще пишут $a\% m$, но лучше так не делать).

[whitefox]

Поняли правильно, это бинарная операция $\mod$ результатом которой является остаток от деления первого числа на второе $(a\bmod b=a-\left\lfloor\frac ab\right\rfloor b).$

-- 09 дек 2014, 21:17 --

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

более-менее устойчивого обозначения этого я не видел

Не соглашусь, обозначение этой бинарной операции как $\mod$, с подачи Д.Кнута, стало широко распространённым (в $\TeX$ для неё предусмотрен собственный код \bmod)

-- 09 дек 2014, 21:22 --

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

погромисты еще пишут $a\% m$

Компьютерная операция % не эквивалентна математической операции $\mod,$ например

Используется синтаксис C++

-3 % 7 == -3

в то время, как $-3\bmod 7=4.$

[Sonic86]

(whitefox)

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

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

погромисты еще пишут $a\% m$

Компьютерная операция % не эквивалентна математической операции $\mod,$ например

Используется синтаксис C++

-3 % 7 == -3

в то время, как $-3\bmod 7=4.$

Знаю, именно поэтому и написал "погромисты".
Они просто думают, что a\% m - это остаток от деления. Доказывать, что они так думают, я не буду. Хотя нет, вот 1-й попавшийся сайт: http://prostocpp.narod.ru/operacii.html

[whitefox]

(Sonic86)

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

Доказывать, что они так думают, я не буду.

На то они и погромисты
Мой комментарий был предназначен ТС, для пояснения почему Вы не рекомендуете так поступать.

[ZumbiAzul]

Вот решение, но как-то слишком много произвола получается.

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

Пусть $a_1= 21^{71^9}$ тогда $a=11^{a_1}$ и $a\equiv11^{a_1\bmod 78}\pmod{79}.$
И переходим к вычислению $a_1\bmod 78.$

Пусть $a_2={71^9}$ тогда $a_1=21^{a_2}$ и $a_1\equiv21^{a_2\bmod \lambda(m_1)}\pmod{m_1}.$
Далее пусть $a_3={9}$ тогда $a_2=71^{a_3}$ и $a_2\equiv71^{a_3\bmod \lambda(m_2)}\pmod{m_2}.$
Выберем теперь $m_1=m_2=4$ (полагаю, это можно сделать, т.к. числа 71 и 21 взаимно просты с 4 и формула не нарушается), тогда $\lambda(m_1)=\lambda(m_2)=2$. Т.е. остатки при делении будут либо 0, либо 1.

Итак, $a_3\bmod 2=9\bmod 2=1$.
Далее, $a_2\bmod 2=71^1\bmod 2=1$.
Наконец, $a_1\bmod 2=21^1\bmod 2=1$.

В итоге $a\equiv 11\pmod{79}$ и, стало быть, остаток от деления исходного числа $a$ на 79 составляет 11.

Вроде задача решена, но сильно смущает наличие произвола в выборе $m_1, m_2$.
Верно ли я решил вторую задачу?

[Sonic86]

ZumbiAzul в сообщении #943175 писал(а):

Выберем теперь $m_1=m_2=4$ (полагаю, это можно сделать, т.к. числа 71 и 21 взаимно просты с 4 и формула не нарушается)

Это что-то из области фантастики.

Вам надо просто итерировать применение формулы с функцией Кармайкла вверх по башне.

[whitefox]

ZumbiAzul в сообщении #943175 писал(а):

Пусть $a_2={71^9}$ тогда $a_1=21^{a_2}$ и $a_1\equiv21^{a_2\bmod \lambda(m_1)}\pmod{m_1}.$

Чему равно $m_1$?

ZumbiAzul в сообщении #943175 писал(а):

Далее пусть $a_3={9}$ тогда $a_2=71^{a_3}$ и $a_2\equiv71^{a_3\bmod \lambda(m_2)}\pmod{m_2}.$

Чему равно $m_2$?

ZumbiAzul в сообщении #943175 писал(а):

Выберем теперь $m_1=m_2=4$ (полагаю, это можно сделать, т.к. числа 71 и 21 взаимно просты с 4 и формула не нарушается), тогда $\lambda(m_1)=\lambda(m_2)=2$. Т.е. остатки при делении будут либо 0, либо 1.

Это Вы о чём? Никакого произвола в выборе $m_1,m_2$ нет, они определены однозначно.

[ZumbiAzul]

$m_1 = \lambda(78)=12, m_2=\lambda(12)=2$ ?? Т.е. $\bmod m$ превращается в $\pmod m$?

[VAL]

ZumbiAzul в сообщении #943175 писал(а):

Выберем теперь $m_1=m_2=4$ (полагаю, это можно сделать, т.к. числа 71 и 21 взаимно просты с 4 и формула не нарушается)[..]

Если уж применять столь радикальный метод, надо быть последовательным и не парится:
Поскольку 5 и 71 взаимно просты выберем 5 в качестве ответа.


PS: На самом деле, как Вам уже указали, никакого произвола нет.