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

[Sonic86]

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

$m_1 = \lambda(78)=12, m_2=\lambda(12)=2$

Да. Вот теперь применяйте.

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

Т.е. $\bmod m$ превращается в $\pmod m$

что?

[whitefox]

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

$m_1 = \lambda(78)=12, m_2=\lambda(12)=2$ ??

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

И переходим к вычислению $a_1\bmod 78.$

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

$a_1\equiv21^{a_2\bmod \lambda(m_1)}\pmod{m_1}.$

Так чему, всё таки, равно $m_1$?

[ZumbiAzul]

$m_1=78, m_2=12$

[whitefox]

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

$m_1=78$

Насчёт $m_1$ верно.
Что бы идти дальше, не забудьте проверить взаимную простоту $m_1$ и 21.

[ZumbiAzul]

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

Что бы идти дальше, не забудьте проверить взаимную простоту $m_1$ и 21.

Они не взаимно просты (их Н.О.Д. = 3), значит формулу применять нельзя. Как тогда быть?

[whitefox]

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

Они не взаимно просты (их Н.О.Д. = 3), значит формулу применять нельзя. Как тогда быть?

Использовать соотношение $21^{a_2}\bmod 78=3\cdot((7\cdot21^{a_2-1})\bmod26).$
В общем случае $d(a\bmod b)=(da)\bmod(db)$

[ZumbiAzul]

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

Использовать соотношение $21^{a_2}\bmod 78=3\cdot((7\cdot21^{a_2-1})\bmod26).$

Что-то я совсем запутался... А как применить формулу к выражению $(7\cdot21^{a_2-1})\bmod26$ ? Формула ведь дана без коэффициентов... А здесь мешает семерка..(

[whitefox]

Используйте тождество:

$$(ab)\bmod m=((a\bmod m)(b\bmod m))\bmod m$$

[ZumbiAzul]

Спасибо большое!
Вот решение, проверьте, пожалуйста, правильный ли ответ.

$11^{21^{71^{9}}}\equiv11^{21^{71^{9}}\bmod {78}}\pmod{79}=11^{21\cdot21^{71^{9}-1}\bmod {78}}\pmod{79}=11^{3\cdot(7\cdot21^{71^{9}-1}\bmod {26})}\pmod{79}=11^{3\cdot(7\bmod26)(21^{71^{9}-1}\bmod {26})\bmod26}\pmod{79}=11^{3\cdot7\cdot(21^{(71^{9}-1)\bmod\lambda(26)}\bmod {26})\bmod26}\pmod{79}=11^{3\cdot7\cdot(21^{71^{9}\bmod\lambda(26)-1}\bmod {26})\bmod26}\pmod{79}=11^{3\cdot7\cdot(21^{(71^{9}\bmod12+(-1)\bmod12)\bmod12}\bmod {26})\bmod26}\pmod{79}=11^{3\cdot7\cdot(21^{(71^{9\bmod\lambda(12)}\bmod12+11)\bmod12}\bmod {26})\bmod26}\pmod{79}=11^{3\cdot7\cdot(21^{(71^{9\bmod2}\bmod12+11)\bmod12}\bmod {26})\bmod26}\pmod{79}=11^{3\cdot7\cdot(21^{[(71^{1}\bmod12)\bmod12+11\bmod12]\bmod12}\bmod {26})\bmod26}\pmod{79}=11^{3\cdot7\cdot(21^{22\bmod12}\bmod {26})\bmod26}\pmod{79}=11^{3\cdot7\cdot(21^{10}\bmod {26})\bmod26}\pmod{79}=11^{3\cdot7\cdot1\bmod26}\pmod{79}=11^{21}\pmod{79}=64.$

При вычислении возникли 2 подзадачи:
1. Найти остаток от деления числа $21^{10}$ на 26;
2. Найти остаток от деления числа $11^{21}$ на 79.
Вот их решения:

1. Т.к. $26=2\cdot13$ и Н.О.Д(21,2)=Н.О.Д.(21,13)=1, то по малой теореме Ферма имеют место следующие два сравнения:

$$21^1\equiv1\pmod2,$$

$$21^{12}\equiv1\pmod{13}.$$

Беря корень 12-й степени из второго сравнения, получаем

$$21^1\equiv1\pmod2,$$

$$21^1\equiv1\pmod{13}.$$

Возводя оба сравнения в 10-ю степень, получаем:

$$21^{10}\equiv1\pmod2,$$

$$21^{10}\equiv1\pmod{13}.$$

Т.к. два одинаковых сравнения имеют место по разным модулям, то имеет место и сравнение по модулю, равному произведению модулей, т.е.

$$21^{10}\equiv1\pmod{26}.$$

2. Т.к. все числа 11, 21, 79 попарно взаимно просты, то опять применяем теорему Ферма:

$$11^{78}\equiv1\pmod{79}.$$

Беря корень 6-й степени, получаем

$$11^{13}\equiv1\pmod{79}.$$

Путем прямых вычислений можно добавить к данному сравнению еще одно:

$$11^{2}\equiv42\pmod{79}.$$

Возведем его в четвертую степень и напишем пару получившихся сравнений:

$$11^{13}\equiv1\pmod{79}.$$

$$11^{8}\equiv42^4\pmod{79}.$$

Перемножая их, получаем сравнение

$$11^{21}\equiv42^4\pmod{79}.$$

Далее, вычисляя в столбик, находим остаток от деления числа $42^4$ на 79. Остаток равен 64.

[whitefox]

Идею решения Вы поняли правильно. Осталось исправить ошибки, причина которых неодназначность понимания выражений, например:

Что означает $21\cdot21^{71^9-1}\bmod78?$

Означает ли это $21\cdot(21^{71^9-1}\bmod78)?$

Или $(21\cdot21^{71^9-1})\bmod78?$

-- 10 дек 2014, 14:07 --

Цитата:

1. Т.к. $26=2\cdot13$ и Н.О.Д(21,2)=Н.О.Д.(21,13)=1, то по малой теореме Ферма имеют место следующие два сравнения:

$$21^1\equiv1\pmod2,$$

$$21^{12}\equiv1\pmod{13}.$$

Беря корень 12-й степени из второго сравнения, получаем

$$21^1\equiv1\pmod2,$$

$$21^1\equiv1\pmod{13}.$$

Возводя оба сравнения в 10-ю степень, получаем:

$$21^{10}\equiv1\pmod2,$$

$$21^{10}\equiv1\pmod{13}.$$

Т.к. два одинаковых сравнения имеют место по разным модулям, то имеет место и сравнение по модулю, равному произведению модулей, т.е.

$$21^{10}\equiv1\pmod{26}.$$

Э-э-э . . .
Вообще-то такие вычисления проводят обычно так:

$$21^{10}\equiv(-5)^{10}\equiv25^5\equiv(-1)^5\pmod{26}$$

и так далее.

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

[ZumbiAzul]

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

$11^{21^{71^{9}}}\equiv11^{21^{71^{9}}\bmod {78}}\pmod{79}=11^{(21\cdot21^{71^{9}-1})\bmod {78}}\pmod{79}=11^{3\cdot[(7\cdot21^{71^{9}-1})\bmod {26}]}\pmod{79}=11^{3\cdot[((7\bmod26)(21^{71^{9}-1}\bmod {26}))\bmod26]}\pmod{79}=11^{3\cdot[(7\cdot(21^{(71^{9}-1)\bmod\lambda(26)}\bmod {26}))\bmod26]}\pmod{79}=11^{3\cdot[(7\cdot(21^{71^{9}\bmod\lambda(26)-1}\bmod {26}))\bmod26]}\pmod{79}=11^{3\cdot[(7\cdot(21^{(71^{9}\bmod12+(-1)\bmod12)\bmod12}\bmod {26}))\bmod26]}\pmod{79}=11^{3\cdot[(7\cdot(21^{(71^{9\bmod\lambda(12)}\bmod12+11)\bmod12}\bmod {26}))\bmod26]}\pmod{79}=11^{3\cdot[(7\cdot(21^{(71^{9\bmod2}\bmod12+11)\bmod12}\bmod {26}))\bmod26]}\pmod{79}=11^{3\cdot[(7\cdot(21^{[(71^{1}\bmod12)\bmod12+11\bmod12]\bmod12}\bmod {26}))\bmod26]}\pmod{79}=11^{3\cdot[(7\cdot(21^{22\bmod12}\bmod {26}))\bmod26]}\pmod{79}=11^{3\cdot[(7\cdot(21^{10}\bmod {26}))\bmod26]}\pmod{79}=11^{3\cdot[(7\cdot1)\bmod26]}\pmod{79}=11^{21}\pmod{79}=48.$

-- Ср дек 10, 2014 14:29:32 --

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

но в конце нужно было воспользоваться китайской теоремой об остатках.

А как ею надо было воспользоваться, не могли бы вы показать, пожалуйста (никогда раньше ей не пользовался)?

-- Ср дек 10, 2014 14:31:14 --

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

Вообще-то такие вычисления проводят обычно так:

$$21^{10}\equiv(-5)^{10}\equiv25^5\equiv(-1)^5\pmod{26}$$

Круто! В одну строчку

[whitefox]

Вы по прежнему настаиваете, что $21^{10}\bmod26=1?$

[ZumbiAzul]

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

Вы по прежнему настаиваете, что $21^{10}\bmod26=1?$

Судя по Вашим выкладкам, д.б. 25... Но тогда, где ошибка в моих рассуждениях?

[whitefox]

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

А как ею надо было воспользоваться, не могли бы вы показать, пожалуйста (никогда раньше ей не пользовался)?

Посмотрите на простенький пример из Википедии.

-- 10 дек 2014, 14:52 --

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

Но тогда, где ошибка в моих рассуждениях?

Вычислите $21^{10}\bmod13$ указанным мной способом.

[ZumbiAzul]

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

$$21^{10}\equiv(-5)^{10}\equiv25^5\equiv(-1)^5\pmod{26}$$

и так далее.

В ваших вычислениях не очевидно, почему мы не обращаем внимания на степень и пишем просто, что

$$21^{10}\equiv(-5)^{10}\pmod{26}$$

Почему это так?