Вычисление остатка с помощью функции Эйлера

[Keks0314]

Здравствуйте. Подскажите, пожалуйста, как вычислять остаток в задачах такого типа с помощью функции Эйлера: ${{860^{801}}^{717}}^{969}$ $\pmod {390}$. Как находить остаток с 1 степенью, к примеру, $23^{277}$ $\pmod 9$, понятно.

[Sonic86]

Keks0314 в сообщении #1278013 писал(а):

Как находить остаток с 1 степенью, к примеру, $23^{277}$ $\pmod 9$, понятно.

Как Вы будете искать $23^{a}\pmod 9$?

[Keks0314]

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

Keks0314 в сообщении #1278013 писал(а):

Как находить остаток с 1 степенью, к примеру, $23^{277}$ $\pmod 9$, понятно.

Как Вы будете искать $23^{a}\pmod 9$?

23 $\equiv 5 $ $\pmod 9$. 5 взаимно просто с 9, поэтому можно воспользоваться формулой Эйлера. $\varphi(9)$ = 6. Представим $\alpha$ как 6x + r. Чтобы найти остаток, достаточно вычислить $5^{r}$ $\pmod 9$

[Sonic86]

Keks0314 в сообщении #1278025 писал(а):

23 $\equiv 5 $ $\pmod 9$. 5 взаимно просто с 9, поэтому можно воспользоваться формулой Эйлера. $\varphi(9)$ = 6. Представим $\alpha$ как 6x + r. Чтобы найти остаток, достаточно вычислить $5^{r}$ $\pmod 9$

А вот это все попробуйте записать в виде одного сравнения по модулю $23$:
$23^a\equiv?\pmod{9}$

[Keks0314]

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

А вот это все попробуйте записать в виде одного сравнения по модулю $23$:
$23^a\equiv?\pmod{9}$

$23^{a \pmod{6}}$? Возможно, неточно понял Вас.

[Sonic86]

Keks0314 в сообщении #1278083 писал(а):

$23^{a \pmod{6}}$?

Все верно:
$23^a\equiv 23^{a \pmod 6}\pmod 9$
А если $a=5^{4^3}$, то какая формула получится?

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

[Keks0314]

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

]Все верно:
$23^a\equiv 23^{a \pmod 6}\pmod 9$
А если $a=5^{4^3}$, то какая формула получится?

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

Понял Вас, спасибо большое за помощь.

[LonelyHorny]

Как в данном примере можно использовать теорему Эйлера, если $gcd(860, 390) $=$ 10?$

[Sonic86]

LonelyHorny в сообщении #1278175 писал(а):

Как в данном примере можно использовать теорему Эйлера, если $gcd(860, 390) = 10?$

Надо разложить основание на 2 множителя: взаимно-простое с модулем и остальное. Как работать с основанием, которое взаимно просто с модулем - только что разобрались. Для не взаимно простого основания надо использовать правило $ak\equiv bk \pmod{mk}\Leftrightarrow a\equiv b \pmod{m}$. Одной формулой с ходу это не запишу - некрасиво выглядит. Т.е. надо вынести общий множитель - в результате получим опять основание, взаимно-простое с модулем, с которым умеем работать.

[LonelyHorny]

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

Надо разложить основание на 2 множителя: взаимно-простое с модулем и остальное. Как работать с основанием, которое взаимно просто с модулем - только что разобрались. Для не взаимно простого основания надо использовать правило $ak\equiv bk \pmod{mk}\Leftrightarrow a\equiv b \pmod{m}$. Одной формулой с ходу это не запишу - некрасиво выглядит. Т.е. надо вынести общий множитель - в результате получим опять основание, взаимно-простое с модулем, с которым умеем работать.

Мне как раз не ясно, как воспользоваться этим свойством сравнений из-за большой степени. 860 можно разложить как 43 * 20. 43 взаимно просто с 390. 20 и 390 нужно сократить на 10. Но как именно это сделать? Просто если я и применял это свойство, то для чисел вроде $20^{10}$, для которых всё было довольно просто: $20*20^{9} \pmod {390} \Leftrightarrow 2*20^{9} \pmod {39}$.

[Sonic86]

LonelyHorny в сообщении #1278294 писал(а):

Мне как раз не ясно, как воспользоваться этим свойством сравнений из-за большой степени.

Потому что она - большая и страшная? Давайте ее тоже заменим на букву $a$, чтобы она не была такая страшная
Надо вычислить $860^a \pmod{390}$.
Вот теперь попробуйте:
1. Выделить степень $10$ отдельно, остальное (которое взаимно простое) - отдельно.
2. Вынести НОД за скобку. (считайте, что $a>0$)
3. Упростить то, что осталось от степени $10$.
Получается?

LonelyHorny в сообщении #1278294 писал(а):

Просто если я и применял это свойство, то для чисел вроде $20^{10}$, для которых всё было довольно просто: $20*20^{9} \pmod {390} \Leftrightarrow 2*20^{9} \pmod {39}$.

Да и тут точно так же надо действовать.



Вообще интересно, возможна ли и насколько полезна будет общая формула, которая работала бы в любом случае, без выделения случая НОД?

upd: кажется так:
Если $d=\gcd(a,m)$ для любых $a,m$ $a^{\varphi(m)}\equiv d\cdot\left(d^{-1}\pmod{\frac{m}{d}}\right)\pmod {m}$
Формула корректна, поскольку $d\cdot\left(d^{-1}\pmod{\frac{m}{d}}\right)\equiv d(r+\frac{m}{d}t)=rd+tm\equiv rd \pmod m$ - единственное значение по модулю $m$. Кроме того $d\cdot\left(d^{-1}\pmod{\frac{m}{d}}\right)\equiv1\pmod{\frac{m}{d}}$.

Обобщать формулу с функцией Кармайкла лень

upd2: хотя я же забыл: там м.б. сколь угодно длинный предпериод, так что красивой формулы действительно не получится, только если добавлять какие-то частые и удобные условия. Например, $(\forall t>0)\gcd(a^t,m)=d$.
Например, если $\gcd(a,m)=d=\gcd(d^2,m)$, то $a^{2\varphi(m)}\equiv a^{\varphi(m)}\pmod m$. А это уже очень удобно для символьных преобразований (равносильное условие $d=\gcd(a,m)=\gcd(a^2,m)$).
При этих условиях $(\forall x)a^x\equiv a^{\varphi(m)+(x\bmod \varphi(m))}\pmod m$.
Вот можете это юзать