精华内容
下载资源
问答
  • 求解二次同余式
    千次阅读
    2017-11-05 16:22:20

    求解形如 x^2 = a (mod p) 这样的同余式

    /*
    模P平方根:
        求 X ^2 = a (mod p)
        定理:当P为!!!奇素数 !!!的时候
        先判断(a / p )的勒让德符号, 若为-1则无解,若为1则有解
        分解P-1,然后求B,然后求出X(t-1),和a的逆元
        然后开始求 ans = ( a的逆元 * 上一个X的平方(t-k))的(t-k-1)次方对P取模
        如果  ans == -1 则 J = 1;
        如果  ans ==  1 则 J = 0;
        然后开始求现在的 X = (上一个X * B的(J*2的k次方)次方
        直到求出X0,也就是最后的解
    */
    #include<bits/stdc++.h>
    using namespace std;
    
    void Divide(int p, int &t, int &s)
    {
        t = 0, s= 0;
        while(p % 2 == 0)
        {
            t++;
            p /= 2;
        }
        s = p;
        return ;
    }
    
    int Pow(int a, int b, int mod)
    {
        int ans = 1, base = a;
        while(b != 0)
        {
            if(b & 1)
                ans = (ans * base) % mod;
            base = (base * base) % mod;
            b >>= 1;
        }
        return ans;
    }
    
    int Legendre(int a, int p)
    {
        if(a == 2)
        {
            int x = (p+1)*(p-1)/8;
            if(x % 2 == 0)
                return 1;
            else
                return -1;
        }
        else
        {
            int ans = Pow(a, (p-1)/2, p);
            if(ans == p-1)
                return -1;
            else
                return 1;
        }
    }
    
    int FindN(int p)
    {
        for(int i = 1; i < p; i++)
        {
            if(Legendre(i, p) == -1)
                return i;
        }
    }
    
    int e_gcd(int a, int b, int &x, int &y)
    {
        if(b == 0)
        {
            x = 1; y = 0;
            return a;
        }
        int q = e_gcd(b, a%b, y, x);
        y -= a/b*x;
        return q;
    }
    
    int Inverse(int a, int m)
    {
        int x, y;
        int gcd = e_gcd(a, m, x, y);
        if(1 % gcd != 0)
            return -1;
        x *= 1/gcd;
        m = abs(m);
        int ans = x % m;
        if(ans <= 0)
            ans += m;
        return ans;
    }
    
    int JudgeJ(int A, int x, int t, int p)
    {
        cout << A << " " << x << " " << t << " " << p << endl;
        x = ((x % p) * (x % p) % p);
        int xx = (A * x) % p;
        int ans = Pow(xx, pow(2, t), p);
        if(ans == p-1)
            return 1;
        else
            return 0;
    }
    
    int main()
    {
        int a, p;
        printf("请输入所求算式的 a 和 p:\n");
        while( scanf("%d %d", &a, &p) != EOF)
        {
            if(Legendre(a, p) == -1)
            {
                cout << "无解" << endl;
                continue;
            }
            int t, s;
            Divide(p-1, t, s); //求t和s
            int n = FindN(p);  //找到那个不符合条件的n
            int b = Pow(n, s, p);
            int *X;
            X = (int *) malloc(sizeof(int) * (t+5));
            X[t-1] = Pow(a, (s+1)/2, p);
            t--;
            int A = Inverse(a, p);          //求A的逆元
            int k = 0;
            while(t > 0)
            {
                int j = JudgeJ(A, X[t], t-1, p);
                int B = Pow(b, j * pow(2, k), p);
                X[t-1] = ((X[t] % p) * (B % p)) % p;
                t--; k++;
            }
            printf("所求的解为:");
            cout << X[0] << endl;
        }
        return 0;
    }
    


    更多相关内容
  • 二次同余方程的解法(2020.11.20).pdf
  • 定理、判别1.勒让德符号(Legendre Symbol)2.欧拉判别准则(Euler's criterion)(1)内容(2)证明(3)注意三、x2≡n(modx^2≡n(modx2≡n(mod p)p)p)——奇波拉算法(Cipolla's algorithm)1.操作2.证明x=(a+a2−n)p+...


    一、介绍

    1.定义

    当存在某个 x x x,可以使得式子 x 2 ≡ n ( m o d x^2≡n(mod x2n(mod p ) p) p)成立时,称“n是模p的二次剩余”;
    当对任意x不成立时,称“n是模 p的二次非剩余”。

    例如,满足模11的二次剩余的数有: 1 , 3 , 4 , 5 , 6 1,3,4,5,6 1,3,4,5,6
    模11二次非剩余的数有: 2 , 6 , 7 , 8 , 10 2,6,7,8,10 2,6,7,8,10

    至于 0 0 0,即不是二次剩余也不是二次非剩余。

    2.定理

    对于方程 x 2 ≡ n ( m o d x^2≡n(mod x2n(mod p ) p) p),如果 p p p是一个奇质数(即 p p p为大于2的质数),那么在集合 { 1 , 2 , … , p − 1 } \{1,2,…,p-1\} {1,2,,p1}中,有 p − 1 2 \frac{p-1}{2} 2p1个数满足模 p p p的二次剩余,剩下的 p − 1 2 \frac{p-1}{2} 2p1个数为模 p p p的二次非剩余。

    证明:

    第一步:对于任何一个整数 X X X来说, X 2 % p X^2\%p X2%p都可以写为: x 2 % p ( x ∈ { 1 , 2 , … , p − 1 } ) x^2\%p(x \in \{1,2,…,p-1 \}) x2%p(x{1,2,,p1})

    X = k ∗ p + x X=k*p+x X=kp+x
    X 2 % p = ( k ∗ p + x ) 2 % p ⇒ x 2 % p X^2\%p=(k*p+x)^2\%p\Rightarrow x^2\%p X2%p=(kp+x)2%px2%p

    第二步:证明 x 2 x^2 x2 ( p − x ) 2 (p-x)^2 (px)2在模 p p p条件下同余

    ( p − x ) 2 (p-x)^2 (px)2进行展开得到 ( p 2 − 2 p x + x 2 ) (p^2-2px+x^2) (p22px+x2),再对 p p p取模,得到 x 2 x^2 x2
    证毕。

    第三步:证明在 { 1 , 2 , … , p − 1 2 } \{1,2,…,\frac{p-1}{2} \} {1,2,,2p1}中,不同的 x x x所对应 x 2 x^2 x2对p取模的结果不同
    反证法:若存在不同的 x x x y y y处于集合中,且 x 2 ≡ y 2 ( m o d x^2≡y^2(mod x2y2(mod p ) p) p)
    那么就推出 p ∣ ( x 2 − y 2 ) ⇒ p ∣ ( x − y ) ( x + y ) p|(x^2-y^2)\Rightarrow p|(x-y)(x+y) p(x2y2)p(xy)(x+y)

    由于 ( x + y ) < p (x+y)<p (x+y)<p,这个式子成立的唯一可能就是 x = = y x==y x==y,与条件相矛盾。
    证毕。

    由上方的三个证明可以得知,前 p − 1 2 \frac{p-1}{2} 2p1个数对应 x 2 x^2 x2对p取模的结果与后 p − 1 2 \frac{p-1}{2} 2p1个数相同,而且,前 p − 1 2 \frac{p-1}{2} 2p1个数对应 x 2 x^2 x2对p取模的结果各自不同,说明集合 { 1 , 2 , … , p − 1 } ) \{1,2,…,p-1 \}) {1,2,,p1})对应的 x 2 x^2 x2对p取模的结果有 p − 1 2 \frac{p-1}{2} 2p1个,再结合证明一,进行推广,所有整数对应的 x 2 x^2 x2对p取模的结果有 p − 1 2 \frac{p-1}{2} 2p1

    也就是在集合 { 1 , 2 , … , p − 1 } \{1,2,…,p-1\} {1,2,,p1}中,有 p − 1 2 \frac{p-1}{2} 2p1个数满足模 p p p的二次剩余,剩下的 p − 1 2 \frac{p-1}{2} 2p1个数为模 p p p的二次非剩余。


    二、判别

    1.勒让德符号(Legendre Symbol)

    如果 p p p是一个奇质数, a a a是一个整数,可以使用 ( a p ) (\frac{a}{p}) (pa)来表示 a a a是否为模 p p p二次剩余,或者是既不是二次剩余,也不是二次非剩余。
    在这里插入图片描述

    2.欧拉判别准则(Euler’s criterion)

    (1)内容

    如果 p p p是一个奇质数, a a a是一个整数此时存在等式:
    ( a p ) = a p − 1 2 ( m o d (\frac{a}{p})=a^{\frac{p-1}{2}}(mod (pa)=a2p1(mod p ) p) p)

    (2)证明

    1. 若 ( a p ) = 0 (\frac{a}{p})=0 (pa)=0
    a = k p ⇒ a p − 1 2 = ( k p ) p − 1 2 a=kp\Rightarrow a^{\frac{p-1}{2}}=(kp)^{\frac{p-1}{2}} a=kpa2p1=(kp)2p1
    ( k p ) p − 1 2 ≡ 0 ( m o d (kp)^{\frac{p-1}{2}}≡0(mod (kp)2p10(mod p ) p) p)
    所以此时 a p − 1 2 = 0 = ( a p ) a^{\frac{p-1}{2}}=0=(\frac{a}{p}) a2p1=0=(pa)

    2. 若 ( a p ) = 1 (\frac{a}{p})=1 (pa)=1
    a a a x 2 x^2 x2同余,而且 x ∈ { 1 , 2 , … , p − 1 } x\in\{1,2,…,p-1\} x{1,2,,p1},
    由于 x x x p p p互质,根据费马小定理,可知:
    x p − 1 ≡ 1 ( m o d x^{p-1}≡1(mod xp11(mod p ) p) p)
    ⇒ ( x 2 ) p − 1 2 ≡ 1 ( m o d \Rightarrow (x^2)^{\frac{p-1}{2}}≡1(mod (x2)2p11(mod p ) = ( a p ) p)=(\frac{a}{p}) p)=(pa)

    3. 若 ( a p ) = − 1 (\frac{a}{p})=-1 (pa)=1
    此时 a a a i ∗ j i*j ij同余,且 i ≠ j , i 、 j ∈ { 1 , 2 , … , p − 1 } i\neq j,i、j\in\{1,2,…,p-1\} i=jij{1,2,,p1}
    i ∗ j ≡ a ( m o d i*j≡a(mod ija(mod p ) p) p)
    ⇒ i ≡ a ∗ j − 1 ( m o d \Rightarrow i≡a*j^{-1}(mod iaj1(mod p ) p) p)

    第一步证明不同的 i i i所对应的 j j j是不同的。

    反证法:若存在 由 于 I ≡ a ∗ j − 1 ( m o d 由于I≡a*j^{-1}(mod Iaj1(mod p ) p) p) i ≡ a ∗ j − 1 ( m o d i≡a*j^{-1}(mod iaj1(mod p ) p) p)
    则可以写为: I − i = k p I-i=kp Ii=kp
    由于 i 、 I ∈ { 1 , 2 , … , p − 1 } i、I\in\{1,2,…,p-1\} iI{1,2,,p1}
    唯有 i = = I i==I i==I时,才会成立,产生矛盾。
    证毕。

    第二步证明 a p − 1 2 = ( p − 1 ) ! a^{\frac{p-1}{2}}=(p-1)! a2p1=(p1)!

    可以将集合 { 1 , 2 , … , p − 1 } \{1,2,…,p-1\} {1,2,,p1}内的 p − 1 p-1 p1个数分为 p − 1 2 \frac{p-1}{2} 2p1组,每组里面的两个数的积与 a a a同余,所以 ( p − 1 ) ! (p-1)! (p1)! a p − 1 2 a^{\frac{p-1}{2}} a2p1.

    根据威尔逊定理:p 是质数的充要条件为 ( p − 1 ) ! ≡ − 1 ( m o d (p−1)! ≡ −1 (mod (p1)!1(mod p ) p) p)
    此时可以得到: a p − 1 2 = ( p − 1 ) ! ≡ − 1 ( m o d a^{\frac{p-1}{2}}=(p-1)!≡ −1 (mod a2p1=(p1)!1(mod p ) p) p)

    (3)注意

    以算法实现时,直接计算 a p − 1 2 a^{\frac{p-1}{2}} a2p1 p p p的结果将得到 p − 1 p-1 p1,所以也可以表示为:
    a p − 1 2 % p = { 1 ( a p ) = 1 p − 1 ( a p ) = − 1 0 ( a p ) = 0 a^{\frac{p-1}{2}}\%p=\begin{cases} 1 & (\frac{a}{p})=1\\ p-1 & (\frac{a}{p})=-1 \\ 0 & (\frac{a}{p})=0 \\ \end{cases} a2p1%p=1p10(pa)=1(pa)=1(pa)=0

    三、 x 2 ≡ n ( m o d x^2≡n(mod x2n(mod p ) p) p)——奇波拉算法(Cipolla’s algorithm)

    求解方程 x 2 ≡ n ( m o d x^2≡n(mod x2n(mod p ) p) p)

    1.操作

    (1)先利用欧拉判别准则判断 n n n是否满足对模 p p p二次剩余,若满足进行下一操作,若不满足,则结束。

    (2) 通过随机试错的方法从集合 { 0 , 1 , 2 , . . . , p − 1 } \{0,1,2,...,p-1\} {0,1,2,...,p1}中找到一个 a a a,且 a 2 − n a^2-n a2n满足模 p p p的二次非剩余,即 ( a 2 − n p ) = = − 1 (\frac{a^2-n}{p})==-1 (pa2n)==1

    (3) x = ( a + a 2 − n ) p + 1 2 x=(a+\sqrt{a^2-n})^{\frac{p+1}{2}} x=(a+a2n )2p+1就是一个解,由于 x 2 x^2 x2 ( p − x ) 2 (p-x)^2 (px)2同余,所以还有第二个解 ( p − x ) (p-x) (px)

    2.证明 x = ( a + a 2 − n ) p + 1 2 x=(a+\sqrt{a^2-n})^{\frac{p+1}{2}} x=(a+a2n )2p+1为解

    大佬的证明
    在这里插入图片描述
    重点在于将上方的定理推导到复数域中。
    在这里插入图片描述
    在这里插入图片描述


    四、模板题

    代码

    #include<bits/stdc++.h> 
    using namespace std;
    typedef long long LL;
     
    LL quick_mod(LL a, LL b, LL m)
    {
        LL ans = 1;
        a %= m;
        while(b)
        {
            if(b & 1)
            {
                ans = ans * a % m;
                b--;
            }
            b >>= 1;
            a = a * a % m;
        }
        return ans;
    }
     
    struct T
    {
        LL p, d;
    };
     
    LL w;
     
    //二次域乘法
    T multi_er(T a, T b, LL m)
    {
        T ans;
        ans.p = (a.p * b.p % m + a.d * b.d % m * w % m) % m;
        ans.d = (a.p * b.d % m + a.d * b.p % m) % m;
        return ans;
    }
     
    //二次域上快速幂
    T power(T a, LL b, LL m)
    {
        T ans;
        ans.p = 1;
        ans.d = 0;
        while(b)
        {
            if(b & 1)
            {
                ans = multi_er(ans, a, m);
                b--;
            }
            b >>= 1;
            a = multi_er(a, a, m);
        }
        return ans;
    }
     
    //求勒让德符号
    LL Legendre(LL a, LL p)
    {
        return quick_mod(a, (p-1)>>1, p);
    }
     
    LL mod(LL a, LL m){
        a %= m;
        if(a < 0) a += m;
        return a;
    }
     
    LL Solve(LL n,LL p){
        if(p == 2) return 1;
        if (Legendre(n, p) + 1 == p)//为二次非剩余 
            return -1;
        LL a = -1, t;
        while(true){
            a = rand() % p;
            t = a * a - n;
            w = mod(t, p);
            if(Legendre(w, p) + 1 == p) break;
        }
        T tmp;
        tmp.p = a;
        tmp.d = 1;
        T ans = power(tmp, (p + 1)>>1, p);
        return ans.p;
    }
     
    int main(){
        int t;
        cin>>t;
        while(t--){
            int n, p;
            cin>>n>>p;
            n%=p;
            int a = Solve(n, p);
            if(a == -1){
                cout<<"Hola!"<<endl; 
                continue;
            }
            int b = p - a;
            if(a > b) swap(a, b);
            if(a == b)
                cout<<a<<endl;
            else
                cout<<a<<" "<<b<<endl;
        }
        return 0;
    }
    

    五、 x 2 ≡ n ( m o d x^2≡n(mod x2n(mod p k ) p^k) pk)(gcd(x,p)=1,p为奇质数)

    先解同余式 x 2 ≡ n ( m o d x^2≡n(mod x2n(mod p ) p) p)

    设解为 r r r,即 r 2 ≡ n ( m o d r^2≡n(mod r2n(mod p ) p) p)
    转化可得: r 2 − n = m p r^2-n=mp r2n=mp ⇒ ( r 2 − n ) k = ( m p ) k \Rightarrow (r^2-n)^k=(mp)^k (r2n)k=(mp)k

    w w w表示 n \sqrt{n} n

    上式就变为了 ( r + w ) k ( r − w ) k = ( m p ) k (r+w)^k(r-w)^k=(mp)^k (r+w)k(rw)k=(mp)k

    进行二项式展开,
    ( r + w ) k = C k 0 r k + C k 1 r k − 1 w . . . + C k k − 1 r w k − 1 + C k k w k ⇒ t + u ∗ w (r+w)^k=C_k^0r^k+C_k^1r^{k-1}w...+C_k^{k-1}rw^{k-1}+C_k^kw^k\Rightarrow t+u*w (r+w)k=Ck0rk+Ck1rk1w...+Ckk1rwk1+Ckkwkt+uw
    ( r − w ) k = C k 0 r k + C k 1 r k − 1 ( − w ) . . . + C k k − 1 r ( − w ) k − 1 + C k k ( − w ) k ⇒ t − u ∗ w (r-w)^k=C_k^0r^k+C_k^1r^{k-1}(-w)...+C_k^{k-1}r(-w)^{k-1}+C_k^k(-w)^k\Rightarrow t-u*w (rw)k=Ck0rk+Ck1rk1(w)...+Ckk1r(w)k1+Ckk(w)ktuw

    仅当 ( − w ) (-w) (w)的次数为偶次时才会作用于 t t t,此时负号相抵消,故两式能够构成一个平方差的形式。

    上式就变为了 t 2 − u 2 ∗ n = ( m p ) k t^2-u^2*n=(mp)^k t2u2n=(mp)k
    t 2 − u 2 ∗ n ≡ 0 ( m o d t^2-u^2*n≡0(mod t2u2n0(mod p k ) p^k) pk)

    处理得 t 2 ≡ u 2 n ( m o d t^2≡u^2n(mod t2u2n(mod p ) p) p)

    通过二项式展开的式子,有 g c d ( p , u ) = = 1 gcd(p,u)==1 gcd(p,u)==1(暂未证明,待补充)

    通过消去律,可以得到: t 2 ( u − 1 ) 2 ≡ n ( m o d t^2(u^{-1})^2≡n(mod t2(u1)2n(mod p ) p) p)
    通过求逆元的方法可以求出 u − 1 u^{-1} u1

    此时得出了第一个解 x = t ∗ i n v ( u ) ( m o d x=t*inv(u)(mod x=tinv(u)(mod p k ) p^k) pk)
    再根据之前的同余关系 x 2 ≡ ( p − x ) 2 ( m o d x^2≡(p-x)^2(mod x2(px)2(mod p ) p) p)
    所以还有第二个解 ( p k − t ∗ i n v ( u ) ) ( m o d (p^k-t*inv(u))(mod (pktinv(u))(mod p k ) p^k) pk)

    例:求方程 x 2 ≡ 13 ( m o d x^2≡13(mod x213(mod 27 ) 27) 27)的解

    可以求出 t = 40 , u = 16 , i n v ( u ) = 22 t=40,u=16,inv(u)=22 t=40,u=16,inv(u)=22
    所以第一个解为 t ∗ i n v ( u ) = ( 40 ∗ 22 ) % 27 = 16 t*inv(u)=(40*22)\%27=16 tinv(u)=(4022)%27=16
    第二个解就是 p k − x = 27 − 16 = 11 p^k-x=27-16=11 pkx=2716=11

    为了方便理解,也可以写为 x ≡ ± 11 ( m o d x≡\pm11(mod x±11(mod 27 ) 27) 27)


    展开全文
  • NOI数学:二次同余方程的解法

    千次阅读 2022-02-21 15:13:56
    二次同余方程的解 - autoint - 博客园 算法导论-----数论-----计算x^2=1(mod n) 在区间[1,n-1]的解 - Inpeace7 - 博客园 【?】高精版同余方程 【?】高精版同余方程 - 委屈的咸鱼鱼鱼鱼 - 博客园

    高精度取模

    高精度取模_to_more_excellent的博客-CSDN博客_c++高精度取模

    C++ P1082 同余方程

    C++ P1082 同余方程_ice_word的博客-CSDN博客_c++ 同余方程

    二次同余方程的解

    二次同余方程的解 - autoint - 博客园

    算法导论-----数论-----计算x^2=1(mod n) 在区间[1,n-1]的解 - Inpeace7 - 博客园

    【?】高精版同余方程

    【?】高精版同余方程 - 委屈的咸鱼鱼鱼鱼 - 博客园

    高精度求平方根

    高精度求平方根_LzyRapX-CSDN博客_高精度平方根

    二次同余方程的解

    二次同余方程的解_ACdreamer-CSDN博客_二次同余方程怎么解

    二次同余方程的解 - autoint - 博客园

    二次同余方程的解_新的开始...-CSDN博客

    求解模奇质数意义下的二次同余方程

    求解模奇质数意义下的二次同余方程_DZYO的博客-CSDN博客_求解二次同余方程

    总结——数论:解高次同余方程 BSGS算法

    总结——数论:解高次同余方程 BSGS算法_dengzhang6507的博客-CSDN博客

    Rabin加密算法和n次同余方程

    https://xz.aliyun.com/t/5113

    Strange Way to Express Integers(高精度---同余方程)(扩展欧几里德)

    Strange Way to Express Integers(高精度---同余方程)(扩展欧几里德)_SHUI-CSDN博客

    https://xz.aliyun.com/t/5113

    求解模奇质数意义下的二次同余方程

    求解模奇质数意义下的二次同余方程_DZYO的博客-CSDN博客_求解二次同余方程

    https://arkike.blog.csdn.net/article/details/8896483

    二次同余方程模合数的一般解法

    二次同余方程模合数的一般解法_Quack-CSDN博客_二次同余方程解法

    高次同余方程,二次同余方程学习笔记

    高次同余方程,二次同余方程学习笔记_Aaronliu17008的博客-CSDN博客

    高次同余方程,二次同余方程学习笔记 - Xu-daxia - 博客园

    高次同余方程式的解数及解法_ Learn as if you were to live forever-CSDN博客_高次同余式的解数及解法

    Rabin加密算法和n次同余方程

    https://xz.aliyun.com/t/5113

    二次剩余入门

    二次剩余入门_Eiffel的博客-CSDN博客_二次剩余

    怎么判定x^2 = 6 (mod 8)是否有解?

    怎么判定x^2 = 6 (mod 8)是否有解?【数论吧】_百度贴吧

    4n+1型素数模的二次同余方程

    \(4n+1\)型素数模的二次同余方程 - 高等数学讨论 - 悠闲数学娱乐论坛(第2版) - Powered by Discuz!

    解方程 x^2≡1(mod 2^t).

    解方程x^2≡1(mod2^t). – 手机爱问

    同余式x^2=29(mod 35)的所有解怎么求?

    同余式x^2=29(mod 35)的所有解怎么求?_百度知道

    5种情况求x^2≡a(mod p)

    5种情况求x^2≡a(mod p)(1) p是奇数质数 k是正整数 求x^2≡p^2(mod p^k)有多少解?(2) a是一个整数的完全平方 p是质数 求x^2≡a(mod p)有多少解?(3) 证明如果x^2≡a(mod p)只有两个解 那么 x^2≡a(mod p^k)只有_作业帮

    5种情况求x^2≡a(mod p)

    (1) p是奇数质数 k是正整数 求x^2≡p^2(mod p^k)有多少解?

    (2) a是一个整数的完全平方 p是质数 求x^2≡a(mod p)有多少解?

    (3) 证明如果x^2≡a(mod p)只有两个解 那么 x^2≡a(mod p^k)只有两个解(k是整数)

    (4) 找出10个奇数质数p满足p|x^2+5 (x是整数) 另:能对这些质数做一个推断吗

    (5)找出10个奇数质数p满足p|x^2+1 (x是整数) 另:能对这些质数做推断吗

    (1) p是奇数质数 k是正整数 求x^2≡p^2(mod p^k)有多少解?

    k=1,有一个解x≡0(mod p)

    k=2,有一个解x≡0(mod p)

    k>2,显然正负p是两个不同的解,如果A是另一个不同的解,则(A^2,p^k)=(p^2,p^k)=p^2,

    所以A^2=z^2*p^2,(z,p)=1,A=z*p

    则A^2-p^2=(z^2-1)p^2=mp^k,(m,p)=1,(z-1)(z+1)=m*p^(k-2),z-1与z+1只有一个可能是p的倍数

    所以z=n*p^(k-2)+/-1 m=n(np^(k-2)+/-2),显然(n,p)=1

    取n=0,1,2,3,...p-1,p+1,p+2,.2p-1,2p+1,2p+2,...3p-1.(p^2-1)*p -1

    共计2+(p-1)*2*(p^2-1)个解

    (2) a是一个整数的完全平方 p是质数 求x^2≡a(mod p)有多少解?

    (3) 证明如果x^2≡a(mod p)只有两个解 那么 x^2≡a(mod p^k)只有两个解(k是整数)

    (4) 找出10个奇数质数p满足p|x^2+5 (x是整数) 另:能对这些质数做一个推断吗

    (5)找出10个奇数质数p满足p|x^2+1 (x是整数) 另:能对这些质数做推断吗



    高精度求平方根

    高精度求平方根_LzyRapX-CSDN博客_高精度平方根

    集训————数论,扩展欧几里得,高精度求模以及同余定理

    集训————数论,扩展欧几里得,高精度求模以及同余定理;_HPU WIN-CSDN博客

    C++对拍

    C++对拍_py_2017的博客-CSDN博客_对拍c++

    树链剖分 --算法竞赛专题解析(30)

    树链剖分 --算法竞赛专题解析(30)_罗勇军的博客-CSDN博客

    二次剩余入门

    二次剩余入门_Eiffel的博客-CSDN博客_二次剩余

    Cipolla算法学习小记

    Cipolla算法学习小记_Facico的博客-CSDN博客

    https://oi-wiki.org/math/quad-residue/

    二次剩余Cipolla算法_FLY_WHITE的博客-CSDN博客

    【模板】【数论】二次剩余Cipolla算法,离散对数BSGS 算法

    【模板】【数论】二次剩余Cipolla算法,离散对数BSGS 算法_weixin_33726318的博客-CSDN博客

    【数论模板】二次剩余Cipolla算法,离散对数BSGS 算法

    【数论模板】二次剩余Cipolla算法,离散对数BSGS 算法_Never give in.-CSDN博客

    二次剩余定理及Cipolla算法入门到自闭

    https://my.oschina.net/u/4390999/blog/3419093

    二次剩余Cipolla算法 【转载a_crazy_czy】

    二次剩余Cipolla算法 【转载a_crazy_czy】_zoro_n的博客-CSDN博客

    二次剩余的判定及Cipolla算法

    二次剩余的判定及Cipolla算法 - 我云知世就是力量 - 博客园

    二次剩余Cipolla算法

    二次剩余Cipolla算法_FLY_WHITE的博客-CSDN博客

    【二次剩余】Cipolla(模意义下开根)

    【二次剩余】Cipolla(模意义下开根)_HOWARLI的博客-CSDN博客_模意义下开根

    2020年教学直播平台排名

    2020年教学直播平台排名_教育部

    区块链中的数学-用Cipolla算法求解二次剩余方程

    区块链中的数学-用Cipolla算法求解二次剩余方程 | 登链社区 | 深入浅出区块链技术

    高精度运算永远不最终版(更新优化中..)

    高精度运算永远不最终版(更新优化中..) - &豪 - C++博客

     

    展开全文
  • 次同余式的解数和解法

    千次阅读 2020-11-01 00:39:17
    初等数论 关于高次同余式的笔记。

    索引

    (解数)定理1:设 m 1 , m 2 , ⋯   , m k ∈ Z > 0 {{m}_{1}},{{m}_{2}},\cdots ,{{m}_{k}}\in {{\mathbb{Z}}_{>0}} m1,m2,,mkZ>0两两互素, m = ∏ i = 1 k m i m=\prod\limits_{i=1}^{k}{{{m}_{i}}} m=i=1kmi f ( x ) f\left( x \right) f(x)是整系数多项式,则

    1-i): f ( x ) ≡ 0     m o d   m 有 解 ⇔ 方 程 组 f ( x ) ≡ 0     m o d   m i ( 1 ≤ i ≤ k ) 有 解 f\left( x \right)\equiv 0\text{ }\bmod m有解\Leftrightarrow 方程组f\left( x \right)\equiv 0\text{ }\bmod {{m}_{i}}\left( 1\le i\le k \right)有解 f(x)0 modmf(x)0 modmi(1ik)

    证明

    1. ( ⇒ ) \left( \Rightarrow \right) ()
      ∃ x 0 ,   f ( x 0 ) ≡ 0     m o d   m \exists {{x}_{0}},\text{ }f\left( {{x}_{0}} \right)\equiv 0\text{ }\bmod m x0, f(x0)0 modm,由于 ∀ 1 ≤ i ≤ k ,   m i ∣ m \forall 1\le i\le k,\text{ }\left. {{m}_{i}} \right|m 1ik, mim,因此有
      f ( x 0 ) ≡ 0     m o d   m i ,   ∀ 1 ≤ i ≤ k f\left( {{x}_{0}} \right)\equiv 0\text{ }\bmod {{m}_{i}},\text{ }\forall 1\le i\le k f(x0)0 modmi, 1ik
    2. ( ⇐ ) \left( \Leftarrow \right) ()
      ∃ x 0 ,   ∀ 1 ≤ i ≤ k ,   f ( x 0 ) ≡ 0     m o d   m i \exists {{x}_{0}},\text{ }\forall 1\le i\le k,\text{ }f\left( {{x}_{0}} \right)\equiv 0\text{ }\bmod {{m}_{i}} x0, 1ik, f(x0)0 modmi,则有
      f ( x 0 ) ≡ 0     m o d     l c m ( m 1 , ⋯   , m k ) f\left( {{x}_{0}} \right)\equiv 0\text{ }\bmod \text{ }lcm\left( {{m}_{1}},\cdots ,{{m}_{k}} \right) f(x0)0 mod lcm(m1,,mk)
      由于 m 1 , ⋯   , m k {{m}_{1}},\cdots ,{{m}_{k}} m1,,mk两两互素,因此有
      l c m ( m 1 , ⋯   , m k ) = m lcm\left( {{m}_{1}},\cdots ,{{m}_{k}} \right)=m lcm(m1,,mk)=m
      即有
      f ( x 0 ) ≡ 0     m o d   m f\left( {{x}_{0}} \right)\equiv 0\text{ }\bmod m f(x0)0 modm

    1-ii):设 f ( x ) ≡ 0     m o d   m f\left( x \right)\equiv 0\text{ }\bmod m f(x)0 modm T T T   m o d   m \bmod m modm的解,而 ∀ 1 ≤ i ≤ k \forall 1\le i\le k 1ik f ( x ) ≡ 0     m o d   m i f\left( x \right)\equiv 0\text{ }\bmod {{m}_{i}} f(x)0 modmi T i {{T}_{i}} Ti   m o d   m i \bmod {{m}_{i}} modmi的解,则有 T = ∏ i = 1 k T i T=\prod\limits_{i=1}^{k}{{{T}_{i}}} T=i=1kTi

    证明
      对于一个同余方程
    f ( x ) ≡ 0     m o d   m f\left( x \right)\equiv 0\text{ }\bmod m f(x)0 modm
    m m m进行素因子分解得到
    m = p 1 e 1 p 2 e 2 ⋯ p k e k m={{p}_{1}}^{{{e}_{1}}}{{p}_{2}}^{{{e}_{2}}}\cdots {{p}_{k}}^{{{e}_{k}}} m=p1e1p2e2pkek
    p 1 e 1 , p 2 e 2 , ⋯   , p k e k {{p}_{1}}^{{{e}_{1}}},{{p}_{2}}^{{{e}_{2}}},\cdots ,{{p}_{k}}^{{{e}_{k}}} p1e1,p2e2,,pkek两两互素。由定理1-i),问题等价于求解方程组
    f ( x ) ≡ 0     m o d   p i e i ,   i = 1 , 2 , ⋯   , k f\left( x \right)\equiv 0\text{ }\bmod {{p}_{i}}^{{{e}_{i}}},\text{ }i=1,2,\cdots ,k f(x)0 modpiei, i=1,2,,k
    f ( x ) ≡ 0     m o d   p i e i f\left( x \right)\equiv 0\text{ }\bmod {{p}_{i}}^{{{e}_{i}}} f(x)0 modpiei的解集为
    S i = { x ≡ b i j i     m o d   m i , j i = 1 , 2 , ⋯   , T i } {{S}_{i}}=\left\{ x\equiv b_{i}^{{{j}_{i}}}\text{ }\bmod {{m}_{i}},{{j}_{i}}=1,2,\cdots ,{{T}_{i}} \right\} Si={xbiji modmi,ji=1,2,,Ti}
    其中 j i {{j}_{i}} ji是作为左上标而非指数。
    则问题又等价于求解 ∏ i = 1 k T i \prod\limits_{i=1}^{k}{{{T}_{i}}} i=1kTi个方程组
    { x ≡ b 1 j 1     m o d   m 1 ,   j 1 ∈ { 1 , 2 , ⋯   , T 1 } x ≡ b 2 j 2     m o d   m 2 , j 2 ∈ { 1 , 2 , ⋯   , T 2 } ⋮ x ≡ b k j k     m o d   m k ,   j k ∈ { 1 , 2 , ⋯   , T k } \left\{ \begin{aligned} & x\equiv b_{1}^{{{j}_{1}}}\text{ }\bmod {{m}_{1}},\text{ }{{j}_{1}}\in \left\{ 1,2,\cdots ,{{T}_{1}} \right\} \\ & x\equiv b_{2}^{{{j}_{2}}}\text{ }\bmod {{m}_{2}},{{j}_{2}}\in \left\{ 1,2,\cdots ,{{T}_{2}} \right\}\\ & \vdots \\ & x\equiv b_{k}^{{{j}_{k}}}\text{ }\bmod {{m}_{k}},\text{ }{{j}_{k}}\in \left\{ 1,2,\cdots ,{{T}_{k}} \right\} \\ \end{aligned} \right. xb1j1 modm1, j1{1,2,,T1}xb2j2 modm2,j2{1,2,,T2}xbkjk modmk, jk{1,2,,Tk}
    m = m i M i ,   ∀ i m={{m}_{i}}{{M}_{i}},\text{ }\forall i m=miMi, i,并解 M i M i ′ ≡ 1     m o d   m i {{M}_{i}}{{M}_{i}}'\equiv 1\text{ }\bmod {{m}_{i}} MiMi1 modmi M i ′ {{M}_{i}}' Mi。由孙子定理,最终得到原同余式 f ( x ) ≡ 0     m o d   m f\left( x \right)\equiv 0\text{ }\bmod m f(x)0 modm的一切解为
    x ≡ ∑ i = 1 k M i M i ′ b i j i ,   ∀ i ,   ∀ j i ∈ { 1 , 2 , ⋯   , T i } x\equiv \sum\limits_{i=1}^{k}{{{M}_{i}}{{M}_{i}}'b_{i}^{{{j}_{i}}}},\text{ }\forall i,\text{ }\forall {{j}_{i}}\in \left\{ 1,2,\cdots ,{{T}_{i}} \right\} xi=1kMiMibiji, i, ji{1,2,,Ti}
    又由博文《孙子定理与首一一元一次同余式组(模数两两互素的情况)》中的第二个定理,若 ∃ ξ i ′ , ξ i ′ ′ ∈ { b i 1 , b i 2 , ⋯   , b i T i }   &   ξ i ′ ≠ ξ i ′ ′ \exists {{\xi }_{i}}',{{\xi }_{i}}''\in \left\{ b_{i}^{1},b_{i}^{2},\cdots ,b_{i}^{{{T}_{i}}} \right\}\text{ }\And \text{ }{{\xi }_{i}}'\ne {{\xi }_{i}}'' ξi,ξi{bi1,bi2,,biTi} & ξi=ξi,则有
    ∑ i = 1 k M i M i ′ ξ i ′ ≡ ∑ i = 1 k M i M i ′ ξ i ′ ′     m o d   m \sum\limits_{i=1}^{k}{{{M}_{i}}{{M}_{i}}'{{\xi }_{i}}'}\cancel{\equiv }\sum\limits_{i=1}^{k}{{{M}_{i}}{{M}_{i}}'{{\xi }_{i}}''}\text{ }\bmod m i=1kMiMiξi i=1kMiMiξi modm
    因此方程 f ( x ) ≡ 0     m o d   m f\left( x \right)\equiv 0\text{ }\bmod m f(x)0 modm   m o d   m \bmod m modm解个数 T T T满足
    T = ∏ i = 1 k T i T=\prod\limits_{i=1}^{k}{{{T}_{i}}} T=i=1kTi

    例题

    1. 使用穷举法求解高次同余式
      f ( x ) ≡ x 4 + 2 x 3 + 8 x + 9 ≡ 0     m o d   35 f\left( x \right)\equiv {{x}^{4}}+2{{x}^{3}}+8x+9\equiv 0\text{ }\bmod 35 f(x)x4+2x3+8x+90 mod35

        直接使用穷举法代入 x = 0 ,   ± 1 ,   ± 2 ,   ⋯   ,   ± 17 x=0,\text{ }\pm 1,\text{ }\pm 2,\text{ }\cdots ,\text{ }\pm 17 x=0, ±1, ±2, , ±17计算,且模数 35 35 35较大,工作量会很大。因此先考虑对其进行化简。
      35 = 5 × 7 35=5\times 7 35=5×7 5 5 5 7 7 7互素,因此可将原方程化为等价形式
      { f ( x ) ≡ 0     m o d   5 f ( x ) ≡ 0     m o d   7 \left\{ \begin{aligned} & f\left( x \right)\equiv 0\text{ }\bmod 5 \\ & f\left( x \right)\equiv 0\text{ }\bmod 7 \\ \end{aligned} \right. {f(x)0 mod5f(x)0 mod7
      基于此分别使用穷举法求解。
      x     m o d   5 − 2 − 1 0 1 2 f ( x )     m o d   5 − 7 ≡ − 2 0 9 ≡ − 1 20 ≡ 0 57 ≡ 2 x     m o d   7 − 3 − 2 − 1 0 1 2 3 f ( x )     m o d   7 12 ≡ 5 − 7 ≡ 0 0 9 ≡ 2 20 ≡ − 1 57 ≡ 1 168 ≡ 0 \begin{matrix} \begin{matrix} x\text{ }\bmod 5 & -2 & -1 & 0 & 1 & 2 \\ f\left( x \right)\text{ }\bmod 5 & -7\equiv -2 & 0 & 9\equiv -1 & 20\equiv 0 & 57\equiv 2 \\ \end{matrix} \\ \begin{aligned} & \\ & \begin{matrix} x\text{ }\bmod 7 & -3 & -2 & -1 & 0 & 1 & 2 & 3 \\ f\left( x \right)\text{ }\bmod 7 & 12\equiv 5 & -7\equiv 0 & 0 & 9\equiv 2 & 20\equiv -1 & 57\equiv 1 & 168\equiv 0 \\ \end{matrix} \\ \end{aligned} \\ \end{matrix} x mod5f(x) mod52721009112002572x mod7f(x) mod73125270100921201257131680
      因此等价于解首一同余式组
      { x ≡ b 1     m o d   5 x ≡ b 2     m o d   7 ,   b 1 ∈ { − 1 , 1 } ,   b 2 ∈ { − 2 , − 1 , 3 } \left\{ \begin{aligned} & x\equiv {{b}_{1}}\text{ }\bmod 5 \\ & x\equiv {{b}_{2}}\text{ }\bmod 7 \\ \end{aligned} \right.,\text{ }{{b}_{1}}\in \left\{ -1,1 \right\},\text{ }{{b}_{2}}\in \left\{ -2,-1,3 \right\} {xb1 mod5xb2 mod7, b1{1,1}, b2{2,1,3}
        M 1 M 1 ′ ≡ 1     m o d   5 ⇔ 7 M 1 ′ ≡ 1 ≡ 1 + ( 7 − 2 ) × 4     m o d   5 ⇔ M 1 ′ ≡ 3     m o d   5   M 2 M 2 ′ ≡ 1     m o d   7 ⇔ 5 M 2 ′ ≡ 1 ≡ 1 + ( 5 + 2 ) × 2     m o d   7 ⇔ M 2 ′ ≡ 3     m o d   7 \begin{aligned} & \text{ }{{M}_{1}}{{M}_{1}}'\equiv 1\text{ }\bmod 5 \\ & \Leftrightarrow 7{{M}_{1}}'\equiv 1\equiv 1+\left( 7-2 \right)\times 4\text{ }\bmod 5 \\ & \Leftrightarrow {{M}_{1}}'\equiv 3\text{ }\bmod 5 \\ & \\ & \text{ }{{M}_{2}}{{M}_{2}}'\equiv 1\text{ }\bmod 7 \\ & \Leftrightarrow 5{{M}_{2}}'\equiv 1\equiv 1+\left( 5+2 \right)\times 2\text{ }\bmod 7 \\ & \Leftrightarrow {{M}_{2}}'\equiv 3\text{ }\bmod 7 \\ \end{aligned}  M1M11 mod57M111+(72)×4 mod5M13 mod5 M2M21 mod75M211+(5+2)×2 mod7M23 mod7
      由孙子定理,同余式组的解为
      x ≡ ∑ i = 1 2 M i M i ′ b i ′     m o d   ( 5 × 7 = 35 ) ≡ 7 × 3 × b 1 + 5 × 3 × b 2 ≡ 21 b 1 + 15 b 2     m o d   35 \begin{aligned} & x\equiv \sum\limits_{i=1}^{2}{{{M}_{i}}{{M}_{i}}'{{b}_{i}}'}\text{ }\bmod \left( 5\times 7=35 \right) \\ & \equiv 7\times 3\times {{b}_{1}}+5\times 3\times {{b}_{2}} \\ & \equiv 21{{b}_{1}}+15{{b}_{2}}\text{ }\bmod 35 \\ \end{aligned} xi=12MiMibi mod(5×7=35)7×3×b1+5×3×b221b1+15b2 mod35
      列表如下。
      b 1     m o d   5 b 2     m o d   7 x ≡ 21 b 1 + 15 b 2     m o d   35 − 1 − 2 − 51 ≡ 19     m o d   35 − 1 − 1 − 36 ≡ 34     m o d   35 − 1 3 24     m o d   35 1 − 2 − 9 ≡ 26     m o d   35 1 − 1 6     m o d   35 1 3 66 ≡ 31     m o d   35 \begin{matrix} {{b}_{1}}\text{ }\bmod 5 & {{b}_{2}}\text{ }\bmod 7 & x\equiv 21{{b}_{1}}+15{{b}_{2}}\text{ }\bmod 35 \\ -1 & -2 & -51\equiv 19\text{ }\bmod 35 \\ -1 & -1 & -36\equiv 34\text{ }\bmod 35 \\ -1 & 3 & 24\text{ }\bmod 35 \\ 1 & -2 & -9\equiv 26\text{ }\bmod 35 \\ 1 & -1 & 6\text{ }\bmod 35 \\ 1 & 3 & 66\equiv 31\text{ }\bmod 35 \\ \end{matrix} b1 mod5111111b2 mod7213213x21b1+15b2 mod355119 mod353634 mod3524 mod35926 mod356 mod356631 mod35
      因此解得
      x ≡ 6 , 19 , 24 , 26 , 31 , 34     m o d   35 x\equiv 6,19,24,26,31,34\text{ }\bmod 35 x6,19,24,26,31,34 mod35

    2. 求解 x 2 ≡ 9     m o d   35 {{x}^{2}}\equiv 9\text{ }\bmod 35 x29 mod35

         35 = 5 × 7 35=5\times 7 35=5×7 5 5 5 7 7 7互素,因此问题等价于求解
      { x 2 ≡ 9     m o d   5 x 2 ≡ 9     m o d   7 \left\{ \begin{aligned} & {{x}^{2}}\equiv 9\text{ }\bmod 5 \\ & {{x}^{2}}\equiv 9\text{ }\bmod 7 \\ \end{aligned} \right. {x29 mod5x29 mod7
      5 , 7 5,7 5,7都是素数,因此有
      x 2 ≡ 9     m o d   5   ⇔   x ≡ 3     m o d   5   ∨   x ≡ − 3 ≡ 2     m o d   5 x 2 ≡ 9     m o d   7   ⇔   x ≡ 3     m o d   7   ∨   x ≡ − 3 ≡ 4     m o d   7 \begin{aligned} & {{x}^{2}}\equiv 9\text{ }\bmod 5\text{ }\Leftrightarrow \text{ }x\equiv 3\text{ }\bmod 5\text{ }\vee \text{ }x\equiv -3\equiv 2\text{ }\bmod 5 \\ & {{x}^{2}}\equiv 9\text{ }\bmod 7\text{ }\Leftrightarrow \text{ }x\equiv 3\text{ }\bmod 7\text{ }\vee \text{ }x\equiv -3\equiv 4\text{ }\bmod 7 \\ \end{aligned} x29 mod5  x3 mod5  x32 mod5x29 mod7  x3 mod7  x34 mod7
      因此问题等价于求解四个方程组
      { x ≡ b 1     m o d   5 x ≡ b 2     m o d   7 ,   b 1 ∈ { 2 , 3 } ,   b 2 ∈ { 3 , 4 } \left\{ \begin{aligned} & x\equiv {{b}_{1}}\text{ }\bmod 5 \\ & x\equiv {{b}_{2}}\text{ }\bmod 7 \\ \end{aligned} \right.,\text{ }{{b}_{1}}\in \left\{ 2,3 \right\},\text{ }{{b}_{2}}\in \left\{ 3,4 \right\} {xb1 mod5xb2 mod7, b1{2,3}, b2{3,4}
        M 1 M 1 ′ = 7 M 1 ′ ≡ 1 ≡ 1 + 5 × 4 = 21     m o d   5 ⇔ M 1 ′ ≡ 3     m o d   5 M 2 M 2 ′ ≡ 5 M 2 ′ ≡ 1 ≡ 1 + 7 × 2 = 15     m o d   7 ⇔ M 2 ′ ≡ 3     m o d   7 \begin{aligned} & \text{ }{{M}_{1}}{{M}_{1}}'=7{{M}_{1}}'\equiv 1\equiv 1+5\times 4=21\text{ }\bmod 5 \\ & \Leftrightarrow {{M}_{1}}'\equiv 3\text{ }\bmod 5 \\ & \\ & {{M}_{2}}{{M}_{2}}'\equiv 5{{M}_{2}}'\equiv 1\equiv 1+7\times 2=15\text{ }\bmod 7 \\ & \Leftrightarrow {{M}_{2}}'\equiv 3\text{ }\bmod 7 \\ \end{aligned}  M1M1=7M111+5×4=21 mod5M13 mod5M2M25M211+7×2=15 mod7M23 mod7
      因此 x 2 ≡ 9     m o d   35 {{x}^{2}}\equiv 9\text{ }\bmod 35 x29 mod35的一切解可以表示为
      x ≡ M 1 M 1 ′ b i + M 2 M 2 ′ b 2 ≡ 21 b 1 + 15 b 2     m o d   5 × 7 = 35 b 1   m o d   5 b 2   m o d   7 x     m o d   35 2 3 17 2 4 − 3 ≡ 32 3 3 3 3 4 18 \begin{aligned} & x\equiv {{M}_{1}}{{M}_{1}}'{{b}_{i}}+{{M}_{2}}{{M}_{2}}'{{b}_{2}}\equiv 21{{b}_{1}}+15{{b}_{2}}\text{ }\bmod 5\times 7=35 \\ & \begin{matrix} {{b}_{1}}\bmod 5 & {{b}_{2}}\bmod 7 & x\text{ }\bmod 35 \\ 2 & 3 & 17 \\ 2 & 4 & -3\equiv 32 \\ 3 & 3 & 3 \\ 3 & 4 & 18 \\ \end{matrix} \\ \end{aligned} xM1M1bi+M2M2b221b1+15b2 mod5×7=35b1mod52233b2mod73434x mod3517332318
      即有
      x ≡ ± 3 ,   17 , 18     m o d   35 x\equiv \pm 3,\text{ }17,18\text{ }\bmod 35 x±3, 17,18 mod35

    (解法)定理2(Hensel引理):设 f ( x ) f\left( x \right) f(x)是整系数多项式, k ∈ Z > 1 k\in {{\mathbb{Z}}_{>1}} kZ>1 p p p是素数,且 f ( x ) ≡ 0     m o d   p k − 1 f\left( x \right)\equiv 0\text{ }\bmod {{p}^{k-1}} f(x)0 modpk1有解 x ≡ r     m o d   p k − 1 x\equiv r\text{ }\bmod {{p}^{k-1}} xr modpk1,则

    2-i): f ( x ) ≡ 0     m o d   p k  有解 ⇔   f ( r ) p k − 1 + t f ′ ( r ) ≡ 0     m o d   p 有 解 f\left( x \right)\equiv 0\text{ }\bmod {{p}^{k}}\text{ 有解}\Leftrightarrow \text{ }\frac{f\left( r \right)}{{{p}^{k-1}}}+tf'\left( r \right)\equiv 0\text{ }\bmod p有解 f(x)0 modpk 有解 pk1f(r)+tf(r)0 modp

    证明
      首先, f ( x ) ≡ 0     m o d   p k − 1 f\left( x \right)\equiv 0\text{ }\bmod {{p}^{k-1}} f(x)0 modpk1有解 x 0 ≡ r     m o d   p k − 1 {{x}_{0}}\equiv r\text{ }\bmod {{p}^{k-1}} x0r modpk1,因此该解有以下推导
    x 0 ≡ r     m o d   p k − 1   ⇒   x 0 − r ≡ 0     m o d   p k − 1   ⇒   p k − 1 ∣ ( x 0 − r ) {{x}_{0}}\equiv r\text{ }\bmod {{p}^{k-1}}\text{ }\Rightarrow \text{ }{{x}_{0}}-r\equiv 0\text{ }\bmod {{p}^{k-1}}\text{ }\Rightarrow \text{ }\left. {{p}^{k-1}} \right|\left( {{x}_{0}}-r \right) x0r modpk1  x0r0 modpk1  pk1(x0r)
    考虑关于 t t t的同余式
      x 0 ≡ r + t p k − 1     m o d   p k ⇔ p k − 1 t ≡ x 0 − r     m o d   p k \begin{aligned} & \text{ }{{x}_{0}}\equiv r+t{{p}^{k-1}}\text{ }\bmod {{p}^{k}} \\ & \Leftrightarrow {{p}^{k-1}}t\equiv {{x}_{0}}-r\text{ }\bmod {{p}^{k}} \\ \end{aligned}  x0r+tpk1 modpkpk1tx0r modpk
    由于 gcd ⁡ ( p k − 1 , p k ) = p k − 1 ∣ ( x 0 − r ) \gcd \left( {{p}^{k-1}},{{p}^{k}} \right)=\left. {{p}^{k-1}} \right|\left( {{x}_{0}}-r \right) gcd(pk1,pk)=pk1(x0r),因此该同余式有解 t ≡ t 0     m o d   p k t\equiv t_0\text{ }\bmod {{p}^{k}} tt0 modpk

      其次,将整系数多项式 f ( x ) f\left( x \right) f(x)视为在 R \mathbb{R} R上无限阶连续可导的函数,并在点 x = r x=r x=r进行泰勒展开得
    f ( x ) = ∑ j = 0 ∞ f ( j ) ( r ) j ! ( x − r ) j   ≡ 0     m o d   p k f\left( x \right)=\sum\limits_{j=0}^{\infty }{\frac{{{f}^{\left( j \right)}}\left( r \right)}{j!}{{\left( x-r \right)}^{j}}}\text{ }\equiv 0\text{ }\bmod {{p}^{k}} f(x)=j=0j!f(j)(r)(xr)j 0 modpk

    1. ∃ x 0 ∈ Z \exists {{x}_{0}}\in \mathbb{Z} x0Z f ( x 0 ) ≡ 0     m o d   p k f\left( {{x}_{0}} \right)\equiv 0\text{ }\bmod {{p}^{k}} f(x0)0 modpk,则有
      f ( x 0 ) ≡ 0     m o d   p k − 1 f\left( {{x}_{0}} \right)\equiv 0\text{ }\bmod {{p}^{k-1}} f(x0)0 modpk1
      由前面的讨论, ∃ t ≡ t 0     m o d   p k \exists t\equiv {{t}_{0}}\text{ }\bmod {{p}^{k}} tt0 modpk,使得
      x 0 ≡ r + t 0 p k − 1     m o d   p k {{x}_{0}}\equiv r+{{t}_{0}}{{p}^{k-1}}\text{ }\bmod {{p}^{k}} x0r+t0pk1 modpk
      因而有
      f ( x 0 ) ≡ f ( r + t 0 p k − 1 ) = ∑ j = 0 ∞ f ( j ) ( r ) j ! ( t 0 p k − 1 ) j = ∑ j = 0 ∞ f ( j ) ( r ) j ! t 0 j p j ( k − 1 ) ≡ 0     m o d   p k f(x_0)\equiv f\left( r+{{t}_{0}}{{p}^{k-1}} \right)=\sum\limits_{j=0}^{\infty }{\frac{{{f}^{\left( j \right)}}\left( r \right)}{j!}{{\left( {{t}_{0}}{{p}^{k-1}} \right)}^{j}}}=\sum\limits_{j=0}^{\infty }{\frac{{{f}^{\left( j \right)}}\left( r \right)}{j!}{{t}_{0}}^{j}{{p}^{j\left( k-1 \right)}}}\equiv 0\text{ }\bmod {{p}^{k}} f(x0)f(r+t0pk1)=j=0j!f(j)(r)(t0pk1)j=j=0j!f(j)(r)t0jpj(k1)0 modpk

      j ( k − 1 ) − k ≥ 0 k ∈ Z > 1   ⇒   k − 1 ∈ Z > 0 }   ⇒   j ≥ k k − 1 = 1 + 1 k − 1 \left. \begin{aligned} & j\left( k-1 \right)-k\ge 0 \\ & k\in {{\mathbb{Z}}_{>1}}\text{ }\Rightarrow \text{ }k-1\in {{\mathbb{Z}}_{>0}} \\ \end{aligned} \right\}\text{ }\Rightarrow \text{ }j\ge \frac{k}{k-1}=1+\frac{1}{k-1} j(k1)k0kZ>1  k1Z>0}  jk1k=1+k11
      因此当 j ≥ 2 j\ge 2 j2时,有
      p k ∣ p j ( k − 1 )   ⇒   f ( j ) ( r ) j ! t 0 j p j ( k − 1 ) ≡ 0     m o d   p k \left. {{p}^{k}} \right|{{p}^{j\left( k-1 \right)}}\text{ }\Rightarrow \text{ }\frac{{{f}^{\left( j \right)}}\left( r \right)}{j!}{{t}_{0}}^{j}{{p}^{j\left( k-1 \right)}}\equiv 0\text{ }\bmod {{p}^{k}} pkpj(k1)  j!f(j)(r)t0jpj(k1)0 modpk
      结合 f ( r + t 0 p k − 1 ) f\left( r+{{t}_{0}}{{p}^{k-1}} \right) f(r+t0pk1)的泰勒展开,因此有
      f ( r + t 0 p k − 1 ) ≡ f ( r ) + t 0 f ′ ( r ) p k − 1 ≡ 0     m o d   p k f\left( r+{{t}_{0}}{{p}^{k-1}} \right)\equiv f\left( r \right)+{{t}_{0}}f'\left( r \right){{p}^{k-1}}\equiv 0\text{ }\bmod {{p}^{k}} f(r+t0pk1)f(r)+t0f(r)pk10 modpk
      x = r x=r x=r f ( x ) ≡ 0     m o d   p k − 1 f\left( x \right)\equiv 0\text{ }\bmod {{p}^{k-1}} f(x)0 modpk1的解,有
      f ( r ) ≡ 0     m o d   p k − 1   ⇒   p k − 1 ∣ f ( r ) f\left( r \right)\equiv 0\text{ }\bmod {{p}^{k-1}}\text{ }\Rightarrow \text{ }\left. {{p}^{k-1}} \right|f\left( r \right) f(r)0 modpk1  pk1f(r)
      于是最终有
      f ( r ) p k − 1 + t 0 f ′ ( r ) ≡ 0     m o d   p \frac{f\left( r \right)}{{{p}^{k-1}}}+{{t}_{0}}f'\left( r \right)\equiv 0\text{ }\bmod p pk1f(r)+t0f(r)0 modp

    2. ∃ t 0 ,   f ( r ) p k − 1 + t 0 f ′ ( r ) ≡ 0     m o d   p \exists {{t}_{0}},\text{ }\frac{f\left( r \right)}{{{p}^{k-1}}}+{{t}_{0}}f'\left( r \right)\equiv 0\text{ }\bmod p t0, pk1f(r)+t0f(r)0 modp,则有
        f ( r ) + t 0 f ′ ( r ) p k − 1 ≡ 0     m o d   p k \text{ }f\left( r \right)+{{t}_{0}}f'\left( r \right){{p}^{k-1}}\equiv 0\text{ }\bmod {{p}^{k}}  f(r)+t0f(r)pk10 modpk
      因此有
      f ( r + t 0 p k − 1 ) = ∑ j = 0 ∞ f ( j ) ( r ) j ! ( t 0 p k − 1 ) j ≡ f ( r ) + t 0 f ′ ( r ) p k − 1 ≡ 0     m o d   p k f\left( r+{{t}_{0}}{{p}^{k-1}} \right)=\sum\limits_{j=0}^{\infty }{\frac{{{f}^{\left( j \right)}}\left( r \right)}{j!}{{\left( {{t}_{0}}{{p}^{k-1}} \right)}^{j}}}\equiv f\left( r \right)+{{t}_{0}}f'\left( r \right){{p}^{k-1}}\equiv 0\text{ }\bmod {{p}^{k}} f(r+t0pk1)=j=0j!f(j)(r)(t0pk1)jf(r)+t0f(r)pk10 modpk
      f ( x ) ≡ 0     m o d   p k f\left( x \right)\equiv 0\text{ }\bmod {{p}^{k}} f(x)0 modpk有解 x ≡ r + t 0 p k − 1     m o d   p k x\equiv r+{{t}_{0}}{{p}^{k-1}}\text{ }\bmod {{p}^{k}} xr+t0pk1 modpk

    3. 基于上述的讨论,在 f ( x ) ≡ 0     m o d   p k − 1 f\left( x \right)\equiv 0\text{ }\bmod {{p}^{k-1}} f(x)0 modpk1有解 x ≡ r     m o d   p k − 1 x\equiv r\text{ }\bmod {{p}^{k-1}} xr modpk1的基础上,设
      f ( x ) ≡ 0     m o d   p k f\left( x \right)\equiv 0\text{ }\bmod {{p}^{k}} f(x)0 modpk
      的解集为 A = { x : f ( x ) ≡ 0     m o d   p k } A=\left\{ x:f\left( x \right)\equiv 0\text{ }\bmod {{p}^{k}} \right\} A={x:f(x)0 modpk}
      f ( r + t p k − 1 ) ≡ 0     m o d   p k f\left( r+t{{p}^{k-1}} \right)\equiv 0\text{ }\bmod {{p}^{k}} f(r+tpk1)0 modpk
      的解集为 B = { x ≡ r + t p k − 1     m o d   p k : f ( r + t p k − 1 ) ≡ 0     m o d   p k } B=\left\{ x\equiv r+t{{p}^{k-1}}\text{ }\bmod {{p}^{k}}:f\left( r+t{{p}^{k-1}} \right)\equiv 0\text{ }\bmod {{p}^{k}} \right\} B={xr+tpk1 modpk:f(r+tpk1)0 modpk},则有
      A = B A=B A=B

    2-ii): f ′ ( r ) ≡ 0     m o d   p   ⇒   ∃ ! t ∈ { 0 , 1 , ⋯   , p − 1 } ,   f ( r + t p k − 1 ) ≡ 0     m o d   p k f'\left( r \right)\cancel{\equiv }0\text{ }\bmod p\text{ }\Rightarrow \text{ }\exists !t\in \left\{ 0,1,\cdots ,p-1 \right\},\text{ }f\left( r+t{{p}^{k-1}} \right)\equiv 0\text{ }\bmod {{p}^{k}} f(r) 0 modp  !t{0,1,,p1}, f(r+tpk1)0 modpk

    证明
      若 f ′ ( r ) ≡ 0     m o d   p f'\left( r \right)\cancel{\equiv }0\text{ }\bmod p f(r) 0 modp,则有 p ∣ f ′ ( r ) p\cancel{|}f'\left( r \right) p f(r)。又 p p p是素数,因此有
    gcd ⁡ ( p , f ′ ( r ) ) = 1 \gcd \left( p,f'\left( r \right) \right)=1 gcd(p,f(r))=1
    同余式
    f ( r ) p k − 1 + t f ′ ( r ) ≡ 0     m o d   p ⇔ f ′ ( r ) t ≡ − f ( r ) p k − 1     m o d   p \frac{f\left( r \right)}{{{p}^{k-1}}}+tf'\left( r \right)\equiv 0\text{ }\bmod p\Leftrightarrow f'\left( r \right)t\equiv -\frac{f\left( r \right)}{{{p}^{k-1}}}\text{ }\bmod p pk1f(r)+tf(r)0 modpf(r)tpk1f(r) modp
    有(唯一)解 t = t 0     m o d   p t={{t}_{0}}\text{ }\bmod p t=t0 modp,即
    f ( r + t p k − 1 ) ≡ 0     m o d   p k f\left( r+t{{p}^{k-1}} \right)\equiv 0\text{ }\bmod {{p}^{k}} f(r+tpk1)0 modpk
    有唯一解 t = t 0     m o d   p t={{t}_{0}}\text{ }\bmod p t=t0 modp

      再由2-i), f ( x ) ≡ 0     m o d   p k f\left( x \right)\equiv 0\text{ }\bmod {{p}^{k}} f(x)0 modpk有唯一解
    x ≡ r + t 0 p k − 1     m o d   p k x\equiv r+{{t}_{0}}{{p}^{k-1}}\text{ }\bmod {{p}^{k}} xr+t0pk1 modpk

    2-iii): f ′ ( r ) ≡ 0     m o d   p   &   f ( r ) ≡ 0     m o d   p k   ⇒   ∀ t ∈ { 0 , 1 , ⋯   , p − 1 } ,   f ( r + t p k − 1 ) ≡ 0     m o d   p k f'\left( r \right)\equiv 0\text{ }\bmod p\text{ }\And \text{ }f\left( r \right)\equiv 0\text{ }\bmod {{p}^{k}}\text{ }\Rightarrow \text{ }\forall t\in \left\{ 0,1,\cdots ,p-1 \right\},\text{ }f\left( r+t{{p}^{k-1}} \right)\equiv 0\text{ }\bmod {{p}^{k}} f(r)0 modp & f(r)0 modpk  t{0,1,,p1}, f(r+tpk1)0 modpk

    证明
       f ( r ) ≡ 0     m o d   p k f\left( r \right)\equiv 0\text{ }\bmod {{p}^{k}} f(r)0 modpk,则有
    p ∣ f ( r )