85问答库 > 求解同余式 x^22==5（mod 41）这种x的指数比较大的怎么解主要想知道方法

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

2024-11-30 00:44:22

推荐回答（1个）

回答1：

两端平方得 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) 。

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

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