求解同余方程11x^18=15(mod23)不用大量计算的解法注：=代表那个三条横线的符号注：=代表≡，刚才没打出来

Question

求解同余方程
11x^18=15(mod23)
不用大量计算的解法
注：=代表那个三条横线的符号
注：=代表≡，刚才没打出来

Answer 1

为了简单,我就用等号来表示同余,省略mod 23.
先解11y=15.注意到11(-2)=-22=1,所以y=-30=16.
然后x^18=16得x^9=4或x^9=-4.解其中一个就能得到另一个的解.
由x^9=4=27得x^3=3=1728(这一步没办法,把1到11的立方遍历一遍),从而x=12.
所以原方程的解是x=11+23k和x=12+23k.