用两种方法计算 7 ^ (-1) 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.