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

[whitefox]

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

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

Числа принадлежащие одному классу вычетов взаимозаменяемы.

[ZumbiAzul]

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

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

$$21^{10}\equiv(-5)^{10}\equiv25^5\equiv(-1)^5=-1\equiv12\equiv25\pmod{13}$$

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

-- Ср дек 10, 2014 15:06:00 --

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

Числа принадлежащие одному классу вычетов взаимозаменяемы.

Откуда следует, что если основание $a$ числа $a^n$ заменить на число $b$, принадлежащее тому же классу вычетов, что и $a$, то полученное число $b^n$ будет взаимозаменяемым c исходным числом $a^n$?

[provincialka]

Сравнения по одному основанию можно складывать, перемножать и, следовательно, возводить в натуральную степень. Первые два свойства проверяются простым вычислением. Впрочем, последнее также довольно очевидно, так как $x^n-y^n$ делится (как многочлен) на $x-y$.

[ZumbiAzul]

provincialka в сообщении #943661 писал(а):

Сравнения по одному основанию можно складывать, перемножать и, следовательно, возводить в натуральную степень. Первые два свойства проверяются простым вычислением. Впрочем, последнее также довольно очевидно, так как $x^n-y^n$ делится (как многочлен) на $x-y$.

Спасибо, теперь понятно.

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

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

в исходной задаче ответ писать следует -1 или 25?

[whitefox]

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

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

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

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}.$$

Любопытно как Вы вычисляли корень 12 степени. Для сравнений даже корень второй степени не всегда существует.

О том, что Ваш метод не может быть верным говорит не верный результат, так как $21\not\equiv1\pmod{13}.$

-- 10 дек 2014, 15:24 --

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

в исходной задаче ответ писать следует -1 или 25?

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

[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\cdot25)\bmod26]}\pmod{79}=11^{57}\pmod{79}=??.$

Остается посчитать остаток от деления $11^{57}$ на 79.
Остальное ведь теперь все верно?

-- Ср дек 10, 2014 15:36:55 --

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

Любопытно как Вы вычисляли корень 12 степени. Для сравнений даже корень второй степени не всегда существует.

Но ведь для любого целого числа $a$ верно соотношение $(a^{12})^{\frac{1}{12}}=a$. Т.е. корень из 12 степени числа в степени 12 будет само число.

[whitefox]

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

Остается посчитать остаток от деления $11^{57}$ на 79.
Остальное ведь теперь все верно?

Вроде как
У меня вышло тоже самое.

-- 10 дек 2014, 15:54 --

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

Но ведь для любого целого числа $a$ верно соотношение $(a^{12})^{\frac{1}{12}}=a$. Т.е. корень из 12 степени числа в степени 12 будет само число.

Со сравнениями так просто не получится. Ваша попытка вычисления $21^{10}\bmod13$ показывает что может найтись пара чисел $a$ и $b$ не сравнимых по модулю $m$ таких, что $a^n\equiv b^n\pmod m.$

Как в Вашем случае $21\not\equiv1\pmod{13}$ в то время как $21^{12}\equiv1^{12}\pmod{13}.$

[ZumbiAzul]

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

Вроде как
У меня вышло тоже самое.

Ответ будет 49?

[whitefox]

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

Ответ будет 49?

У меня ответ другой.

[ZumbiAzul]

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

У меня ответ другой.

я так и думал)
вашим методом не получается получить что-либо дельное, как тогда решить?

[whitefox]

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

вашим методом не получается получить что-либо дельное, как тогда решить?

Им и решать:

$$11^{57}\equiv11\cdot11^{56}\equiv11\cdot42^{28}\pmod{79}$$

и так далее.

[ZumbiAzul]

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

и так далее.

Ответ 21?

[whitefox]

Да

[ZumbiAzul]

Ур-р-р-р-ра-а-а-а!=)
Теперь осталась первая задача

Вот, что у меня получается:

$7^{7^{7^{7^{{...}^{7^{7\bmod1}\bmod1}{...}}\bmod1}\bmod2}\bmod12}\bmod13= 7^{7^{7^{7^{{...}^{7^{0}\bmod1}{...}}\bmod1}\bmod2}\bmod12}\bmod13= 7^{7^{7^{7^{{...}^{1\bmod1}{...}}\bmod1}\bmod2}\bmod12}\bmod13= 7^{7^{7^{7^{{...}^{0}{...}}\bmod1}\bmod2}\bmod12}\bmod13= 7^{7^{7^{7^{0}\bmod1}\bmod2}\bmod12}\bmod13= 7^{7^{7^{1\bmod1}\bmod2}\bmod12}\bmod13= 7^{7^{7^{0}\bmod2}\bmod12}\bmod13= 7^{7^{1\bmod2}\bmod12}\bmod13= 7^{7^{1}\bmod12}\bmod13= 7^{7\bmod12}\bmod13= 7^{0}\bmod13 = 1\bmod13 = 1.$

Как-то слишком все просто. Я правильно решил?

[whitefox]

Вы уверены, что это $7\bmod12=0$ правильно?