求解同余方程11x^18=15(mod23)不用大量计算的解法注：=代表那个三条横线的符号注：=代表≡，刚才没打出来
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/16 02:24:34
求解同余方程11x^18=15(mod23)不用大量计算的解法注：=代表那个三条横线的符号注：=代表≡，刚才没打出来
求解同余方程
11x^18=15(mod23)
不用大量计算的解法
注：=代表那个三条横线的符号
注：=代表≡，刚才没打出来
求解同余方程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的立方遍历一遍),从而x=12.
所以原方程的解是x=11+23k和x=12+23k.
为简便，以==或=表示同余号≡
11x^18=15(mod23)
解:
注意到,gcd(x,23)=1,从而x^22==1 mod 23
于是15x^4==11mod23
于是x^4==13（我的求解过程请见注释1）
即x^4==36
于是x^2==6或-6
通过在excel中利用函数(mod A1*A1,23)计算,得到
1...
全部展开
为简便，以==或=表示同余号≡
11x^18=15(mod23)
解:
注意到,gcd(x,23)=1,从而x^22==1 mod 23
于是15x^4==11mod23
于是x^4==13（我的求解过程请见注释1）
即x^4==36
于是x^2==6或-6
通过在excel中利用函数(mod A1*A1,23)计算,得到
11^2 mod 23=6,并且知道xx==-6无解.(也可以由勒让德符号L(-1,23)=-1知)
于是原同余式的解为:x=±11 mod 23.
如果手工计算,我考虑如下采用析平方因子法来做:
xx==6==52==4*13=4*(36)
从而x==±12==±11
但是，以上过程并不能保证求出的是全部解。因为,18次的同余式，最多可能有18个解。此题的最终结果我没有验证。
另外,如果有离散对数(指标)表,可以非常方便的求解.
补记:昨晚我回家后,利用23的原根10,手算了10^i mod 23, i=1,11(注:10^11==-1,10^(11+j)==10^j),建立离散对数表,确证以上同余方程只有两个解.
另外,我猜想,奇素数p的n次同余方程的解数<=gcd(n,φ(p)),并可推广到合数模.注意到-1=1 mod 2,因此素数2可能比较特殊；另外，-1=p-1 mod p，也可能造成内部的特殊情况。
另外,利用非原根如2,(2^11 mod 23=1)也可以建立类似于离散对数的性质。因此我认为，原根的概念其实还不是最重要的，较之更重要的是一任意幂的模余的分布问题。
请参见:
http://hi.baidu.com/wsktuuytyh/blog/item/c3630807caf75bc77b894705.html
注释1:
15x^4==11mod23,-8x^4==-12,2x^4==3==26,x^4==13.
我是利用洪伯阳方法以分式方式进行计算的:x^4==11/15==-12/-8==3/2==26/2
也可如下:
注意到11*-2=-22==1mod 23
于是:x^18==(-2)*15==-7
从而x^4==-1/7==-2/14==21/14==3/2==13
收起