用两种方法计算 7 ^ (-1) mod 17
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/06 15:49:14
![用两种方法计算 7 ^ (-1) mod 17](/uploads/image/z/8564844-12-4.jpg?t=%E7%94%A8%E4%B8%A4%E7%A7%8D%E6%96%B9%E6%B3%95%E8%AE%A1%E7%AE%97+7+%5E+%28-1%29+mod+17)
用两种方法计算 7 ^ (-1) mod 17
用两种方法计算 7 ^ (-1) mod 17
用两种方法计算 7 ^ (-1) mod 17
(1)设a≡7 ^ (-1) mod 17,则7a≡1 mod 17.
令7a=1+17k,很容易得到一组解为a=5,k=2.
所以7 ^ (-1)≡5 mod 17.
(2)由欧拉定理有7^φ(17)≡1 mod 17,其中由于17为素数,所以φ(17)=16.
所以7^16≡1 mod 17,所以7^(-1)≡7^15 mod 17.
7^3=343≡3 mod 17,所以7^15≡3^5=243≡5 mod 17.
所以7 ^ (-1)≡5 mod 17.