Как найти степень по модулю? Например: число 41 нужно возмести в степень 22 по модулю 37...

Question

Как найти степень по модулю? Например: число 41 нужно возмести в степень 22 по модулю 37 (41^22mod 37) Очень желательно с подробным решением...

Answer 1

Ответ:

34

Пошаговое объяснение:

Вероятно, исходное условие звучало так: найти остаток от деления 41²² на 37, используя свойства сравнения чисел по модулю. Тогда:

41²²=(37+4)²²≡4²²(mod 37)=4*64⁷=4*(37+27)⁷≡4*27⁷(mod 37)=108*27⁶=(2*37+34)*(400+280+49)³=(2*37+34)*(370+30+185+2*37+21+37+12)³≡34*(30+21+12)³(mod 37)=34*63³=34*(37+26)≡34*26³(mod 37)≡34*26*10(mod 37)=34*260=34*(7*37+1)≡34*1(mod 37)=34

То есть 41²²≡34(mod 37)

Comments

Большое спасибо! А можете подсказать,где можно почитать информацию о том,как решать таким образом? Хочу разобраться,но никак не могу найти информацию...

---

Просто я смотрю на Ваше решение,и не могу понять что Вы сделали...

---

В любой статье на тему сравнений чисел по модулю. А какие именно шаги Вам непонятны? Я могу попробовать объяснить

---

Спасибо.Я уже разобрался. К сожалению,сегодня узнал,что нужно решать другим способом-Брать Е(41,22,37) и потом как-то раскладывать...

---

Простите, а что такое Е(41,22,37)?

---

Сам не знаю) Но смысл в том,что я делю y на 2,если делится без остатка-возвожу х в квадрат,если нет-отнимаю от у единицу и делю на 2,а x возвожу в куб,как-то так

---

Честно сказать, ничего не понял... Даже с самого начала если взять. Если у четное, то х будет бесконечно в квадрат возводиться ведь. К слову, а где в Е( , , ) х и у?

---

E(x,y,mod(n))

---

Хм... А можно где-то(на скриншотах) посмотреть на примеры решений? Или на полный алгоритм?