x^22==5（mod 41） 这种x的指数比较大的怎么解 主要想知道方法

题目

x^22==5（mod 41） 这种x的指数比较大的怎么解 主要想知道方法

答案

两端平方得 x^44≡25(mod 41) ,由费马小定理,25≡x^44≡x^40*x^4≡x^4(mod 41) ,因此 x^2≡±5(mod 41) ,因为 (5/41)=(41/5)=(1/5)=1 ,所以 x^2≡5(mod 41) 有两解 ,x≡±13 (mod 41) .因为 (-5/41)=(36/41)=1 ,所以...