跳转至

剩余

定义

令整数 \(k\ge2\)，整数 \(a,m\) 满足 \(\gcd(a,m)=1\)，若存在整数 \(x\) 使得

\[ x^k\equiv a\pmod m \]

则称 \(a\) 为模 \(m\) 的 \(k\) 次剩余。

二次剩余

\[ x^2\equiv a\pmod p \]
Euler判别法

对于奇素数 \(p\) 和满足 \(\gcd(a,p)=1\)的 \(a\)

当 \(a^{\frac{p-1}{2}}\equiv1\pmod p\) 时, \(a\) 是模 \(p\) 的二次剩余

洛谷P5491

P5491 【模板】二次剩余 - 洛谷

\(p\) 是奇素数

求 \(x^2\equiv a\pmod p\) 的根

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
i64 w = 0; // x^2 - n 
array<i64, 2> mul(array<i64, 2> a, array<i64, 2> b, i64 P) {
    return {(a[0] * b[0] + a[1] * b[1] % P * w) % P, (a[0] * b[1] + a[1] * b[0]) % P};
}
i64 qpow(i64 a, i64 b, i64 P) {
    i64 res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % P;
        }
        a = a * a % P;
        b >>= 1;
    }
    return res;
}
i64 qpow(array<i64, 2> a, i64 b, i64 P) {
    array<i64, 2> res{1, 0};
    while (b) {
        if (b & 1) {
            res = mul(res, a, P);
        }
        a = mul(a, a, P);
        b >>= 1;
    }
    return res[0];
}
i64 cipolla(i64 a, i64 p) {
    // x^2\equiv a\pmod p
    a %= p;
    if (qpow(a, (p - 1) / 2, p) == p - 1) {
        // 无解
        return -1;
    }
    i64 x = 0;
    while (true) {
        x = rand() % p;
        w = ((x * x % p - a) % p + p) % p;
        if (qpow(w, (p - 1) / 2, p) == p - 1) {
            break;
        }
    }
    return qpow({x, 1}, (p + 1) / 2, p);
}
void solve() {
    int a, p;
    cin >> a >> p;
    if (a == 0) {
        cout << 0 << "\n";
        return;
    }
    i64 ans1 = cipolla(a, p), ans2 = -ans1 + p;
    if (ans1 == -1) {
        cout << "Hola!\n";
    } else {
        if (ans1 > ans2) {
            swap(ans1, ans2);
        }
        if (ans1 != ans2) {
            cout << ans1 << " ";
        }
        cout << ans2 << "\n";
    }
}
int main() {
    srand(time(nullptr));
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

二次剩余的数量

对于奇素数 \(p\) 和满足 \(\gcd(a,p)=1\)的 \(a\)

二次剩余和非二次剩余均有 \(\frac{p-1}{2}\)

特例

当 \(p\mod4=3\) 时, \(a^{\frac{p+1}{4}}\mod p\) 为一个解.

当 \(p\mod8=5\) 时, \(B\equiv(2a)^{\frac{p-5}{8}}\pmod p\), \(i\equiv2ab^2\pmod p\), \(a*b*(i-1)\mod p\) 为一个解.