请问一次同余式所有整数解的求法?需要计算公式.答:
首先,ax==b mod m
与不定方程ax=b+ym完全等效.
如果它们有公约数,或约去,求解后,再转化为模m的形式.如x==r mod n
转为x==r+n*i mod kn, i=0,…,k-1.
如果gcd(a,m) |b不成立,则无解.
公式一:
显然,如果有解,约去公约数,则必然可转化为gcd(a,m)=1的情况.此时很容易得到公式解.
依欧拉定理, gcd(a,m)=1,则a^Φ(m)==1 mod m.于是a*a^(Φ(m)-1)==1 mod m,即
x==a^(Φ(m)-1) mod m.
这种方法在巧妙的编程方式下,用电脑计算,不失为一种好手段.通常是将Φ(m)-1二进制化,再将多个积项取余,求积.用其他数制或其他思路计算,也行.如何方便如何算.利用洪伯阳同余表示,手算也较方便.
思路二:这种思路我是独创.用熟了很节省书写,思路也很明确.总之很便捷.
利用同余思想,在不定方程两边同时取余,再将倍数集中得到系数减小的另一不定方程.(与原式比较,得到的比较式方程,可以反映出两者的简单的系数关系.)
如此一直到可以看出特解为止.再根据比较式回代.
更多内容,请百度搜索:
wsktuuytyh 同余式
或
wsktuuytyh 不定方程
思路三:
ax==b mod m,gcd(a,m)=1
将模数分解为m=m1*m2*...*mn,(互质(互素)的多个因数)以它们分别为模解出结果.再逆求同余式组.逆解同余式组也不难.对于中国剩余定理,我有简化方案.
可百度搜索:wsktuuytyh 模积计数法
对m为大合数的情况,这种逆求法有一定用处.
以下谈m为质数或其幂的情况
简单的情况,可以取一个与m互素的数k, 得到kax==kb mod m
而ka mod m为一个较小或较好的值,简化为 ux==kb==v mod m
再设法使as-ut==1,再将s,t作用于两个同余式,即得解答.
当然也可以得到另外两个,或多个类似的同余式,让他们线性叠加,使左边x的系数为1即得解.
利用洪伯阳表示来描述和计算,可以使这个过程十分简洁和高效.可以利用比例的性质、带分数的性质来处理同余式.
进一步利用矩阵,可以将线性叠加描述得更简洁.
相关资料,可搜索
wsktuuytyh 洪伯阳 带分数
对于不太复杂的情况,用洪伯阳表述,不用线性叠加的手段就可以方便的求得解答.