剰余計算 ユークリッド互徐法 中国剰余定理

質問

こんにちは。もし、この中でどの問題でもとける方がいましたら教えて頂けませんか。
よろしくお願いします。

7^1024 mod 17.

* =は合同の記号だと思ってくださいです。

39x = 1(mod 95)

x = 2(mod 10)

x = 5(mod13)

回答No.1

f272 · ベストアンサー

7^2=49=15
7^4=15^2=4
7^8=4^2=1
だから7^1024=(7^8)^128=1^128=1

39x=1
(39^2)x=39
39^2=1521=1だから
x=39

回答No.2

hokkaidouda

７＾１０２４を１９で割った余りを求めよという問題ですよね。

(7、19)=1であるから
※7、11は互いに素であるということ。
オイラーの定理が使える。

ψ(19)＝18であるから
7^18≡1(mod19)

7＾1024＝(7＾18)＾56×7＾16
※1024=18×56＋16

ここで
7＾2＝49≡11(mod19)
であるから
7＾4＝(7＾2)^2≡121≡7(mod19)
7^16=(7＾4)＾2≡49≡11

したがって
7＾1024＝(7＾18)×7＾16
　　　　　≡1×11
　　　　　≡11(mod19)

7＾1024を17で割った余りは11