请问一次同余式所有整数解的求法?需要计算公式.

2个回答

  • 请问一次同余式所有整数解的求法?需要计算公式.答:

    首先,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 洪伯阳 带分数

    对于不太复杂的情况,用洪伯阳表述,不用线性叠加的手段就可以方便的求得解答.