45^53(mod89)の簡単な求め方があれば教えてください。私は以下のように2乗して差分を繰り返し

45^53(mod89)の簡単な求め方があれば教えてください。私は以下のように2乗して差分を繰り返し求めることで答えを導出しましたが,このやり方だとあまりにも時間がかかり過ぎます。2乗計算や89で割った時の余りを考える際にどうしても筆算が必要になってしまいます。
45^53 (mod89)
≡((45^2)^26)×45 (mod89)
≡(67^26)×45 (mod89)
≡((67^2)^13)×45 (mod89)
≡(39^13)×45 (mod89) (mod89)
≡((39^2)^6)×39×45 (mod89)
≡(8^6)×64 (mod89)
≡(512^2)×64 (mod89)
≡(-22^2)×64 (mod89)
≡39×64 (mod89)
≡4

質問者からの補足コメント

• 

  フォルマーの小定理？を使えばもしかしたら一気に求められそうですがそこに持ってくまでの過程が思い付きません。

    補足日時：2022/07/01 10:15

No.6 ベストアンサー 回答者： syotao 回答日時： 2022/07/01 17:35

2⁵³45⁵³＝90⁵³≡1（mod89）だからｘ＝45⁵³とおいて

問題は
2⁵³ｘ≡1（mod89）を解くことに帰着
フェルマの定理から
2⁸⁸≡1（mod89）これから2⁴⁴≡±1（mod89）だけども
符号を決めなくてはならないので実際に計算して2¹¹≡-1
したがって
2⁴⁴≡1これから2⁵³＝2⁴⁴2⁹≡2⁹≡67
したがって
67ｘ≡1（mod89）67≡-22（mod89）だから
-22ｘ≡1（mod89）この両辺3倍してすぐ上の式に加えて
ｘ≡4（mod89）

No.5 回答者： mtrajcp 回答日時： 2022/07/01 17:25

9^2=81=-8(mod89)

↓両辺を2乗すると
9^4=64=89-25=-25=-5^2(mod89)…(1)

5^2=25(mod89)
↓両辺に5をかけると
5^3=125=89+36=36(mod89)
↓両辺に5をかけると
5^4=36*5=2*90=2(89+1)=2(mod89)…(2)
↓これに(1)をかけると
45^4=(5^4)(9^4)=-5^6(mod89)…(3)
↓両辺を2乗すると(2)から
45^8=5^12=(5^4)^3=2^3=8(mod89)
↓両辺を2乗すると
45^16=64=-25=-5^2(mod89)…(4)
↓両辺を2乗すると(2)から
45^32=5^4=2(mod89)…(5)

(3)と(4)をかけると
45^20=5^8(mod89)
↓これに(5)をかけると
45^52=5^12=(5^4)^3=2^3=8(mod89)
↓両辺に45をかけると
∴
45^53=8*45=4*90=4(mod89)

No.4 回答者： ありものがたり 回答日時： 2022/07/01 13:42

なるほど。

89 が素数だから、 mod89 で割り算を行ってもかまわないね。

No.3 回答者： t_fumiaki 回答日時： 2022/07/01 13:15

おっと、質問と同じ事かいてしまった。

89≡0より、90≡1を利用すると大幅に簡単になります。

45⁵³≡(90/2)⁵³だから、90≡1を代入すると≡1/2⁵³

ここで分母を計算する。
2⁵³=(2¹⁰)⁵×2³

2¹⁰=1024≡45より
(2¹⁰)⁵×2³≡(45)⁵×2³≡(90/2)⁵×2³≡(1/2)⁵×2³=1/4

∴45⁵³≡1/(1/4)=4

No.2 回答者： tknakamuri 回答日時： 2022/07/01 12:46

45^n mod 89

x45は90掛けて2で割ると楽。
mod89は90で割って余りを補正すると楽。

地道に
n
0 1
1 45
2 67
3 78
4 39
5 64
6 32
7 16
8 8
9 4
10 2
11 1
12 45

11回で元に戻ったので

53 mod 11=9 だから、上の表から4

No.1 回答者： t_fumiaki 回答日時： 2022/07/01 11:38

mod89において。

45⁵³≡(45²)²⁶×45

45²≡67だから、代入すると
≡67²⁶×45
≡(67²)¹³×45

67²≡39だから、代入すると
≡39¹³×45
≡(39²)⁶×39×45

39²≡8、39×45≡64だから、代入すると
≡8⁶×64

≡(8³)²×64
≡(-22)²×64
≡39×64
≡4