No.2ベストアンサー
- 回答日時:
mod 2173 で
M ≡ A^73 = 127^(57×73) = 127^4161.
よって、
mod 41 で
M ≡ 127^(4161 - 40×104) = 127^1,
mod 53 で
M ≡ 127^(4161 - 52×80) = 127^1.
従って、mod 2173 で
M ≡ 127.
泥臭く計算したけど、この綺麗な結果の裏には
なんかもっと華麗な計算がありそう。
No.1
- 回答日時:
173 = 41×53
この素因数分解を見つけるのがたいへんで、
涙目になりました。
かろうじてプログラムはしなかったけれど、
百均電卓の御世話にはなりましたよ。
2173 までのエラトステネス篩も
頑張ればできなくはないけれど、
小さい素数で順に割ってみるほうが早いかな。
今回は問題の指数が小さくて
オイラーの定理が使えないので、
中国剰余定理で mod 2173 を
mod 41 と mod 53 に分解してみましょう。
まず mod 41 で、
127^57 ≡ (127 - 41×3)^(57 - φ(41))
= 4^17 = 4^(16+1) = (16^8)×4 = (256^4)×4
≡ (10^4)×4 = 40000
≡ 25,
次に mod 53 で、
127^57 ≡ (127 - 53×2)^(57 - φ(53))
= 21^5 = 441×441×21
≡ 17×17×21 = 289×21
≡ 24×21 = 504
≡ 27.
A ≡ 25 {mod 41}, A ≡ 27 {mod 53} となる A は、
A = 25 + 41p = 27 + 53q {p,qは整数} と置いて
不定方程式 41p - 53q = 2 を解けば、
ユークリッド互除法で 41×22 - 53×17 = 1 が得られることから
p = 22×2 + 53k, q = 17×2 + 41k {kは整数}.
これを A = 25 + 41p へ代入すると、
A = 25 + 41×(22×2 + 53k) = (25 + 41×22×2) + 2173k.
よって mod 2173 で、
A ≡ 25 + 41×22×2 = 1829.
ああしんど。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 一次合同式と連立合同式の問題について 3 2022/05/07 15:47
- 数学 ユークリッドの互除法、合同式の問題について 1 2022/05/08 11:49
- 数学 【数学】到達できない箇所 2 2022/05/11 22:35
- 数学 数学A 合同式の利用 2 2023/03/02 23:53
- 数学 写真の(2)の問題では「P(X=4)=P(X≦4)-P(X≦3)」という式で求めていますが、 「P( 9 2022/11/14 23:36
- 工学 制御工学の問題について 1 2022/10/22 17:44
- 数学 曲面の面積の問題について 3 2022/06/10 14:26
- 数学 画像の問題について質問です。問題式を楕円の式に変形して、積分範囲を0<=x<=a √(z^2-1) 3 2022/08/29 13:44
- 物理学 分布定数回路の問題について 1 2022/06/12 11:36
- 数学 写真(URL)の問題の(1)についてですが、 円c1は 2点を通ると書いてあることから、 2点の座標 5 2023/02/14 19:44
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
spi 非言語教えてください
-
この問題の解答が(写真) A. a <...
-
spi 非言語教えてください
-
【代数学】置換の位数を数える方法
-
わんこら式勉強法を実践してい...
-
必要条件 十分条件が分かりません
-
2x+y+z=8を満たす正の整数の組...
-
小学5年生 割合の問題
-
判断推理です。 A〜Eの5人が自...
-
漸化式の問題を教えてください...
-
線形代数 置換
-
記数法の問題が分かりません。
-
次の等式を満たす実数x,yを求め...
-
数学の問題です。 連立方程式 s...
-
高一数学〔 チャート 460ページ...
-
以上とか未満とか以下とか…区別...
-
整式 P(x)を(x-1)²で割ったとき...
-
難しい
-
今更だけど
-
ド忘れしたんですけど、2分の1...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
spi 非言語教えてください
-
spi 非言語教えてください
-
数学です
-
SPIの問題です。 【ある本を3日...
-
【代数学】置換の位数を数える方法
-
次の式を複素数の範囲でとけ ど...
-
わんこら式勉強法を実践してい...
-
数学の問題です。 連立方程式 s...
-
必要条件 十分条件が分かりません
-
割る数と余りから割られる数を...
-
以上とか未満とか以下とか…区別...
-
対数計算について
-
漸化式の問題を教えてください...
-
数的の問題
-
4プロセスの解説お願いします!
-
6でわると、商が8になる整数...
-
判断推理です。 A〜Eの5人が自...
-
累乗の各位の和
-
数学の三角形の内心、外心の問...
-
数学の参考書の解答の解説って...
おすすめ情報