Как доказать равенство?

[Sijoji]

Подскажите, как можно доказать равенство? Или что почитать по теме можно, чтобы доказать самостоятельно?

(x^n mod k)^m mod k = x^(n*m) mod k

[iifat]

Для начала стоило б переписать формулу по правилам форума. Потом — попробовать начать с $x\equiv y\mod z\Rightarrow x^n\equiv y^n\mod z$

[Sijoji]

iifat в сообщении #1120121 писал(а):

Для начала стоило б переписать формулу по правилам форума. Потом — попробовать начать с $x\equiv y\mod z\Rightarrow x^n\equiv y^n\mod z$

Разве это верно?

Остаток не может быть больше делителя(у Вас X в степени)

-- 02.05.2016, 18:30 --


Помогите, пожалуйста, полностью дорешать, если не сложно. Потому что я не понимаю как можно здесь доказать равенство.

[ewert]

Sijoji в сообщении #1120155 писал(а):

Остаток не может быть больше делителя(у Вас X в степени)

Три чёрточки в данном случае означают совпадение по модулю (т.е. совпадение остатков левой и правой частей).

На самом деле Вам нужно знать только одно: что $(a\cdot b)\mod k=((a\mod k)\cdot(b\mod k))\mod k$

[arseniiv]

[Написано перед предыдущим ответом, оставлю.]

Я поспорил с собой, что выйдет путаница, и выиграл. iifat использовал здесь не остаток от деления, а (действительно похоже обозначающееся) сравнение по модулю:

$$a\equiv b\pmod n$$

(читается «сравнимы/эквивалентны/равны по модулю $n$») тогда и только тогда, когда разность $(a-b)$ — целое кратное $n$. Если $n$ целое и не ноль, это означает ровно $a\bmod n=b\bmod n$. Если $n=0$, это означает просто $a=b$, потому что только ноль кратен нулю. (Ещё $n$ может быть нецелым как, например, $\varphi\equiv\theta \pmod{2\pi}$ будет означать, что $\varphi$ и $\theta$ — углы одного и того же поворота.)

Теперь, надеюсь, распутались.

[Karan]

Почитать можно, например, вот тут: http://kvant.mccme.ru/1978/10/sravneniy ... chetov.htm
Когда почитаете, поправьте формулы и приведите свои попытки решения.

[Karan]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- отсутствуют собственные содержательные попытки решения задач(и).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.