求解同余方程

问题描述:

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

为了简单,我就用等号来表示同余,省略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的立方遍历一遍),...