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

x^22==5（mod 41） 这种x的指数比较大的怎么解 主要想知道方法
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 ,
所以 x^2≡-5(mod 41)有两解,x≡±6 (mod 41) .
因此,原同余式的解为 x≡±6 ,±13 (mod 41) .