求解部分x^k=b(mod m)问题

原本信誓旦旦的想要解决整个一般性的xk≡b(mod m)问题,然而发现推理过程出了点问题(原因可看这里),故把标题加了“部分”两字,亦即对另一部分的这类问题我还不会解决。

对ab≡c(mod m)这个式子,实际上包括3个问题。在这篇文章中,我们知道了已知a和b求解c。这篇文章中,掌握了已知a和c求b的方法。现在,只剩下最后一个问题:已知b和c,求解a。正式的,本文要解决的问题是:求解xk≡b(mod m),其中k,b,m是整数且m>0,k>1。

首先应该注意到的一点是,如果x有解,由于指数循环节的存在,若是k比Φ(m)还大,可令k=k(mod Φ(m))+Φ(m),这样就无需害怕指数k超级大了。因此,若是m较小,可直接穷举x从0至m-1,得到所有解。但m较大时,显然穷举的方法复杂度就有点不能承受了。

同样的,素数探路原则,考虑m为素数的情况。m为素数时,若gcd(b,m)=m,显然有x≡0(mod m)。所以这里讨论当gcd(b,m)=1的情况。若gcd(k,Φ(m))=1,则有uk+vΦ(m)=1,有x1=xuk+vΦ(m)。若x是解,即xk≡b(mod m),于是有x≡xuk+vΦ(m)≡buxvΦ(m)(mod m)。因为gcd(b,m)=1,显然gcd(x,m)=1,因此有xvΦ(m)≡1(mod m)。于是,我们求得了

x≡bu(mod m), 其中m为素数, gcd(b,m)=gcd(k,Φ(m))=1, uk+vΦ(m)=1.

那么k和Φ(m)不互素时的情况应该怎么做?毕竟不可能那么碰巧的给你的k和Φ(m)恰好互素,k应该可以是任意数,和m无关。

因为m是素数,我们知道一定可以找到一个数g,使得ge≡b(mod m)!我们只要找到m的其中一个原根就行了!由原根定理可知,每个素数p都有且恰好有Φ(p-1)个原根!因此可以令g为最小的那个原根(如果你不知道什么是原根或怎么求最小原根,可以先看这里)。找出g之后,e就可以求出了,如果你还记得这里的内容的话。于是由指标法则可以知道,若xk≡b(mod m),则有kI(x)≡e(mod Φ(m)),因此可以求出I(x)(可以是多个解),于是x≡gI(x)(mod m)。

现在,m是素数的情况解决了。当m是任意数时,由于我们扩展了原根的定义,只需m存在原根。并且在m存在原根的前提下,若gcd(b,m)=1,做法和m是素数的情况是相同的。当b和m不互素时,令d=gcd(b,m),由xk≡b(mod m)可知m|(xk-b),因此d|xk。把d分解成素数乘积的形式,设d=p1a1...prar,因此x必被p1e1...prer整除,其中ei=ceil(ai/k)。令c=p1e1...prer,于是可令x=cx′。令ck≡a(mod m),显然d|ck,所以d|a。令a′=a/d,b′=b/d,m'=m/d,因此,同余式xk≡b(mod m)也即ax′k≡b(mod m),可等价于同余式a′x′k≡b′(mod m′)。可把x′k看成一项,代表未知数,同余式即为线性同余方程。由于gcd(b′,m′)=1,所以,若gcd(a′,m′)≠1,那么方程无解。否则,方程有唯一解,设解为y,即有x′k≡y(mod m′)。而这是一个子问题,可递归求出x′的所有解。由x=cx′可知x的所有解即为x′的每个解乘以c!

若是m没有原根,该怎么办?我也不知道。。。若是有哪位朋友知道并且愿意分享,强烈热烈且迫切的欢迎您和我联系!我的联系方式在about页面!



发表评论

电子邮件地址不会被公开。 必填项已用*标注

*