大学数学で、合同方程式の問題なんですが、

質問

大学数学で、合同方程式の問題なんですが、

ｘ＾９７≡２２　ｍｏｄ　２２５

の解の求め方がわかりません。
どなたかおしえていただけないでしょうか

それとｘ＾ｔ≡ａ　ｍｏｄ　ｎ
の解を求める際に
ｇｃｄ（ａ，ｍ）＝１
ｇｃｄ（ｋ、φ（ｍ））＝１を使うらしいのですが意味がわかりません。
このときのａ，ｍ，ｋは一般自然数です

ｘ＾９７は指数でｘの９７乗のことです

よろしくお願いいたします。

回答No.1

proto · ベストアンサー

まず法225に対してφ(225)を求めます。
(φ(x)はオイラー関数)

　　225 = (3^2)*(5^2)
より
　　φ(225) = φ(3^2)*φ(5^2) = (3^2-3)*(5^2-5) = 120

次に
　　gcd(97,φ(225)) = gcd(97,120) = 1
であることを確かめます。
実際これは成り立ちますね。自身で確かめて見てください。

gcd(97,120)=1より
　　97x+120y = 1
を満たす整数x,yが存在します。
そのようなx,yのうちyが負である組を何でも良いので一つ見つけます。
(ユークリッドの互除法の逆などで求めれば良いでしょう)

今回はそのようなx,yのうちx=73,y=-59を取ります。
(別のx,yでも解けます)
x,yを元の式に代入すると
　　97*73-120*59 = 1
　　97*73 = 1+120*59
となります。
これを用います。

　　x^97 ≡ 22　　(mod 225)
両辺を73乗すると
　　(x^97)^73 ≡ 22^73
　　x^(97*73) ≡ 22^73　　(mod 225)
97*73=1+120*59より
　　x^(1+120*59) ≡ 22^73
　　x * (x^120)^59 ≡ 22^73　　(mod 225)

さて、オイラーの定理より
225と互いに素なxについて
　　x^φ(225) = x^120 ≡ 1　　(mod 225)
が成り立つから、
　　x * (x^120)^59 ≡ x * 1^59　≡ 22^73
　　x ≡ 22^73　　(mod 225)

以上より22^73(mod225)が答え。
あとは計算。