![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67)
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
No.6ベストアンサー
- 回答日時:
2⁵³45⁵³=90⁵³≡1(mod89)だからx=45⁵³とおいて
問題は
2⁵³x≡1(mod89)を解くことに帰着
フェルマの定理から
2⁸⁸≡1(mod89)これから2⁴⁴≡±1(mod89)だけども
符号を決めなくてはならないので実際に計算して2¹¹≡-1
したがって
2⁴⁴≡1これから2⁵³=2⁴⁴2⁹≡2⁹≡67
したがって
67x≡1(mod89)67≡-22(mod89)だから
-22x≡1(mod89)この両辺3倍してすぐ上の式に加えて
x≡4(mod89)
No.5
- 回答日時:
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)
![](http://oshiete.xgoo.jp/images/v2/common/profile/M/noimageicon_setting_16.png?e8efa67)
No.3
- 回答日時:
おっと、質問と同じ事かいてしまった。
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
- 回答日時:
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
![](http://oshiete.xgoo.jp/images/v2/common/profile/M/noimageicon_setting_16.png?e8efa67)
No.1
- 回答日時:
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
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 【数学】到達できない箇所 2 2022/05/11 22:35
- 数学 m, n を整数. g.c.d(m, n) = d, l.c.m(m, n) = l とすると { 2 2022/05/22 18:54
- 数学 大学数学 「条件:t進表現において、何乗しても右から2桁が変わらない2桁の自然数が存在する。」 上記 7 2023/06/28 22:25
- その他(ゲーム) スカイリム、Modに関して Modはインターネットに繋げないと利用できませんが、Modをダウンロード 1 2022/09/20 14:20
- 数学 一次合同式と連立合同式の問題について 3 2022/05/07 15:47
- その他(ゲーム) SkyrimSEのMod organizer で困っています。誰か助けてください。 1 2022/12/05 01:49
- CPU・メモリ・マザーボード マイクラ(java)で影modを使用しながら快適に遊びたい!! 1 2022/08/02 18:20
- ノートパソコン マイクラについて教えてください! 今日初めてマイクラjavaをインストールしました。そして、1.20 2 2023/07/29 01:54
- オンラインゲーム GeForce GTX 1050でマイクラ modの導入してのプレイは可能ですか?6つほどMODは導 1 2023/08/25 11:18
- CPU・メモリ・マザーボード PCでCPUをCore i7 13700KとCore i9 13900Kで悩んでいます。 5 2023/07/07 12:59
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
AとBはn次正方行列とする。 積A...
-
大学の記述入試で外積は使えま...
-
写真の定理4-5の証明についてで...
-
至上最難問の数学がとけた
-
lim[x→+∞](x^n/e^x)=0 の証明
-
オイラーの多面体定理の拡張
-
拡張ユークリッド互除法による...
-
4.6.8で割るとあまりはそれぞれ...
-
【遊びのピタゴラスイッチはな...
-
定理と法則の違い
-
フーリエの積分定理がわかりません
-
数A nは自然数とする。n , n+2 ...
-
det(AB)=det(A)+det(B)
-
数論が専門の方へ、ピタゴラス...
-
長さがマイナスの答えのとき、...
-
【線形代数】基底、dimVの求め方
-
双子素数
-
留数定理とコーシーの積分公式...
-
8のx乗=mod11の答えは?
-
完全数はどうして「完全」と名...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
ファルコンの定理は解かれまし...
-
至上最難問の数学がとけた
-
lim[x→+∞](x^n/e^x)=0 の証明
-
AとBはn次正方行列とする。 積A...
-
これは証明になってる
-
中国剰余式定理(一般形)の証明...
-
【遊びのピタゴラスイッチはな...
-
直角三角形じゃないのに三平方...
-
パップスギュルダンの定理について
-
大学の記述入試で外積は使えま...
-
定理と法則の違い
-
【線形代数】基底、dimVの求め方
-
奇数次の代数方程式
-
完全数はどうして「完全」と名...
-
二次合同式の解き方
-
オイラーの多面体定理の拡張
-
11・13y≡5(mod9)がy≡4(mod9)にな...
-
量子化定理とは?
-
A,Bの異なる2つの箱に異なる1...
-
11の22乗を13で割った余り...
おすすめ情報
フォルマーの小定理?を使えばもしかしたら一気に求められそうですがそこに持ってくまでの過程が思い付きません。