∑MathAdvanced

Quadratic Residues

Key Points

•
A quadratic residue modulo an odd prime p is any a for which $x^{2}$ ≡ a (mod p) has a solution; exactly half of the nonzero classes are residues.
•
Euler’s criterion says $a^{(p - 1) /2}$ ≡ 1 (mod p) if and only if a is a quadratic residue; otherwise it is ≡ −1 (mod p).
•
The Legendre symbol $\frac{a}{p}$ encodes this test: it is 1 for residues, −1 for non-residues, and 0 when p | a.
•
The Tonelli–Shanks algorithm finds a square root modulo an odd prime p in O(( $lo g$ p)^2) time, after first checking that a is a residue.
•
When p ≡ 3 (mod 4), a fast shortcut gives a root: r ≡ $a^{(p + 1) /4}$ (mod p).
•
The Legendre symbol is multiplicative and links to quadratic reciprocity, enabling fast evaluation without exponentiation when prime factors are known.
•
Do not confuse the Jacobi symbol $\frac{a}{n}$ with the Legendre symbol: for composite n, $\frac{a}{n}$ = 1 does not guarantee a square root exists.
•
In programming contests, normalize inputs, guard against overflow with 128-bit multiplication, handle p=2 and a≡0 separately, and return both roots r and p−r.

Prerequisites

→Modular arithmetic basics — Understanding congruences, reduction modulo p, and arithmetic in \mathbb{Z}/p\mathbb{Z} is necessary to define and manipulate quadratic residues.
→Fast modular exponentiation — Euler’s criterion and Tonelli–Shanks both rely on efficient exponentiation modulo p.
→Prime numbers and gcd — Legendre symbol and Tonelli–Shanks assume p is prime; gcd helps handle the a ≡ 0 case and detect divisibility.
→Groups and homomorphisms (light) — The “half are residues” fact and the structure of Tonelli–Shanks are clearer with group-theoretic intuition.
→Binary representation and bit operations — Tonelli–Shanks uses the 2-adic factorization p−1 = q·2^s and repeated squaring.
→Safe modular multiplication — Prevent overflow in C++ by using 128-bit intermediates or alternative techniques.
→Chinese Remainder Theorem (optional) — Needed to extend square-root finding from primes to composite, square-free moduli.
→Quadratic reciprocity (optional) — Provides fast evaluation of Legendre/Jacobi symbols and deeper theoretical understanding.

Detailed Explanation

Tap terms for definitions

01Overview

Quadratic residues are a core concept in modular arithmetic: for an odd prime p, an integer a is a quadratic residue modulo p if there exists an x such that x^2 ≡ a (mod p). This captures the idea of “which numbers are perfect squares” when arithmetic is taken around a clock with p hours. A striking structure emerges: among the p−1 nonzero residues, exactly half are squares and half are not. The Legendre symbol (a/p) concisely records this status: it equals 1 if a is a residue, −1 if not, and 0 when p divides a. Euler’s criterion connects residues to exponentiation: a^{(p−1)/2} ≡ (a/p) (mod p). Algorithmically, we often want to find an x such that x^2 ≡ a (mod p). When p ≡ 3 (mod 4) this is fast via a single exponentiation; otherwise, the Tonelli–Shanks algorithm solves it efficiently by exploiting the 2-adic factorization of p−1. These tools appear in cryptography (e.g., decompressing elliptic-curve points), error-correcting codes, and competitive programming tasks involving modular equations. Understanding residues also opens the door to deeper number theory, including quadratic reciprocity and the Jacobi symbol for composite moduli.

02Intuition & Analogies

Think of modular arithmetic as time on a 12-hour clock, except with p hours where p is prime. Squaring is like taking a number and folding it through a rule that loses sign: on a usual number line, 3^2 and (−3)^2 both give 9. Modulo p, plus/minus collisions also happen because x^2 ≡ (p−x)^2. If you list all x from 1 to p−1 and square them mod p, many different x collapse to the same result; in fact, every nonzero square has exactly two parents: x and p−x. This two-to-one folding explains why there are exactly (p−1)/2 nonzero squares. Euler’s criterion gives a clever shortcut: instead of trying all x, raise a to the power (p−1)/2 and read off whether it behaves like a square. In group terms, the nonzero residues modulo p form a cycle under multiplication. The map x → x^2 is a homomorphism whose kernel is {1, −1}. Counting with the homomorphism image-kernel principle yields the “half are squares” result. To actually find a square root, Tonelli–Shanks is like solving a lock with several tumblers. You write p−1 as q·2^s (a power of two times an odd part), then successively correct the candidate root by multiplying by powers of a fixed non-residue until the “error term” becomes 1. When p ≡ 3 (mod 4), it’s like finding a master key: a single exponentiation already lands on the root.

03Formal Definition

Let p be an odd prime. An integer a is a quadratic residue modulo p if there exists x

\in

Z

such that

x^{2}

\equiv

(mod p)

. Otherwise, if a

\neq \equiv

(mod p)

and no such x exists, a is a quadratic non-residue. The Legendre symbol is defined for a

\in

Z

\n \n \frac{a}{p}

\begin{cases}

0, & p

∣

a, \\ 1, & a

\neq \equiv

0 \ (

mod

\ p)

and

\exists

x^{2}

\equiv

a \ (

mod

\ p), \\ -1, &

otherwise.

\end{cases}\n\nEuler

’s criterion states that for a with p

∤

\n \n \frac{a}{p}

\equiv

a^{

\frac{p - 1}{2}

}

(mod p)

\n \ninterpreting

the right-hand side in \{1, p-1\}

≅

\{1, -1\}. The set

F_{p}^{\times}

of nonzero residues forms a cyclic group of order p−1. The squaring map s:

F_{p}^{\times}

\to

F_{p}^{\times}

, s(x) =

x^{2}

, is a group homomorphism with kernel \{1, -1\}. Hence

∣

im

(s)

∣

\frac{p - 1}{2}

, and these are precisely the nonzero quadratic residues. When p

\equiv

3 \ (

mod

\ 4), any a with

\frac{a}{p}

=1 has a square root r

\equiv

a^{

\frac{p + 1}{4}

} \ (

mod

\ p). In general, Tonelli–Shanks finds r by writing p−1 = q

\cdot

2^{s} with q odd, choosing a non-residue z, and iteratively adjusting a candidate root until the residual factor becomes 1.

04When to Use

Use quadratic residues when you need to decide or compute square roots modulo a prime. Common scenarios include: (1) Solving x^2 \equiv a (mod p) in contest problems, especially with large primes; (2) Elliptic-curve point decompression, where given x you must recover y such that y^2 \equiv x^3 + ax + b (mod p); (3) Counting solutions to quadratic congruences or equations that reduce to one via substitution; (4) Testing whether an expression is a square modulo p as a necessary condition in constructive proofs or algorithm branches. Implementation choices: If p = 2, handle directly. If a \equiv 0 (mod p), the only root is 0. If p \equiv 3 (mod 4), prefer the fast exponent r = a^{(p+1)/4} (mod p). Otherwise, apply Tonelli–Shanks; it is robust and runs in O((\log p)^2). If you must work modulo a composite n, compute the Jacobi symbol (a/n) to get a quadratic character, but remember that (a/n) = 1 does not guarantee a solution; find roots modulo each prime factor and combine them via CRT. For many queries on the same small p, precomputing a residue table can be faster than repeated exponentiations.

⚠️Common Mistakes

Forgetting normalization: not reducing a modulo p before tests can cause overflow or wrong answers; always set a = (a % p + p) % p.\n- Misusing Euler’s criterion when a \equiv 0 (mod p): a^{(p-1)/2} ≡ 0 is not in {±1}; handle a = 0 separately.\n- Confusing Legendre and Jacobi symbols: for composite n, (a/n) = 1 does not imply a square root exists; only for prime p does (a/p) characterize residuosity.\n- Applying Tonelli–Shanks to composite moduli: it assumes p is an odd prime; for composites you must factor n and use CRT or other methods.\n- Ignoring edge cases p = 2 and p \equiv 3 (mod 4): both have simpler, faster solutions than full Tonelli–Shanks.\n- Returning only one root: if r is a root and a \not\equiv 0 (mod p), then p − r is the other; many tasks require both.\n- Integer overflow in C++: modular multiplication with 64-bit operands can overflow; use unsigned __int128 or Montgomery multiplication.\n- Assuming every residue has exactly two roots: the case a \equiv 0 (mod p) has exactly one root x \equiv 0; for nonzero residues there are exactly two.\n- Failing to find a non-residue z efficiently: don’t precompute; a few random trials with Legendre tests typically succeed quickly because half the elements are non-residues.

Key Formulas

Legendre symbol definition

(\frac{a}{p}) = ⎩ ⎨ ⎧ 0, 1, - 1, p ∣ a, \exists x : x^{2} \equiv a (mod p), otherwise

Explanation: This defines the Legendre symbol for an odd prime p. It classifies a modulo p as a square, a non-square, or zero.

Euler’s criterion

a^{\frac{p - 1}{2}} \equiv (\frac{a}{p}) (mod p)

Explanation: Raising a to (p−1)/2 modulo p yields 1 for residues and −1 for non-residues (interpreting −1 as p−1 in modulo arithmetic). It turns residuosity into an exponentiation test.

Multiplicativity

(\frac{ab}{p}) = (\frac{a}{p}) (\frac{b}{p})

Explanation: The Legendre symbol is a multiplicative character. This allows factoring a into primes or small pieces to evaluate the symbol more easily.

Supplementary law for −1

(\frac{- 1}{p}) = (- 1)^{\frac{p - 1}{2}}

Explanation: −1 is a square modulo p if and only if p ≡ 1 (mod 4). This gives an immediate test without exponentiation.

Supplementary law for 2

(\frac{2}{p}) = (- 1)^{\frac{p ^{2} - 1}{8}}

Explanation: 2 is a square modulo p exactly when p ≡ ±1 (mod 8). This is a quick parity-based rule.

Quadratic reciprocity

(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{( p - 1 ) ( q - 1 )}{4}}

Explanation: For odd primes p and q, this relates residuosity across p and q. It flips the symbol depending on whether both primes are 3 mod 4.

Half of nonzeros are squares

# {nonzero quadratic residues mod p} = \frac{p - 1}{2}

Explanation: Because squaring on $F_{p}$ ^× is a 2-to-1 map with kernel {±1}, its image has half the size of the group. This counts the number of distinct nonzero squares.

Tonelli–Shanks setup

p - 1 = q \cdot 2^{s}, q odd

Explanation: Factor p−1 into an odd part q and a power of 2. The algorithm’s loop length and updates are based on this decomposition.

Fast square root case

If p \equiv 3 (mod 4), r \equiv a^{\frac{p + 1}{4}} (mod p)

Explanation: When p is 3 modulo 4 and $\frac{a}{p}$ =1, this single exponentiation yields a square root directly. It is much faster than general methods.

Pair of roots

x^{2} \equiv a (mod p) ⟹ x \equiv \pm r (mod p)

Explanation: If a has a nonzero square root r modulo p, then the only roots are r and p−r. This follows from uniqueness of square roots in fields.

Complexity Analysis

Modular exponentiation by repeated squaring computes

a^{e}

mod p in O(

lo g

e) modular multiplications. When p fits into 64 bits, each multiplication can be done in constant time using 128-bit intermediates (unsigned __int128) to avoid overflow. Thus, evaluating Euler’s criterion

a^{(p - 1) /2}

mod p takes O(

lo g

p) multiplications and O(1) extra memory. For modular square roots, two main cases arise. If p ≡ 3 (mod 4), the root r ≡

a^{(p + 1) /4}

(mod p) is found via a single exponentiation in O(

lo g

p) multiplications. In the general case, Tonelli–Shanks factors p−1 = q·2^s (with

s = v_{2} (p - 1

)). It performs an initial exponentiation to get

t = a^{q}

and

r = a^{(q+1

)/2}, each in O(

lo g

p) multiplications. The main loop runs at most s iterations; in each, we find the smallest i with

t^{2^{i}}

≡ 1 by up to O(s) squarings, and then update using a few multiplications and squarings. Overall, this costs O(

lo g

p +

s^{2}

) modular multiplications; because s ≤ ⌊

lo g_{2}

(p−1)⌋, this is O((

lo g

p)^2). Space usage is O(1), storing a handful of residues. For many queries with the same small p (e.g.,

p \leq 1 0^{6}

), precomputing the residue table by squaring all x costs O(p) time and O(p) space, after which each query is O(1). For very large p (e.g., cryptographic sizes), asymptotics count bit-level operations: exponentiation uses O(M(

lo g

lo g

p) bit complexity with M for big-integer multiplication; Tonelli–Shanks remains quasi-quadratic in

lo g

p and O(1) space.

Code Examples

Legendre symbol via Euler’s criterion (residuosity test)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 using u64 = uint64_t;
5 using u128 = __uint128_t;
6 
7 // Multiply a and b modulo m using 128-bit to avoid overflow (for 64-bit m)
8 static inline u64 mul_mod(u64 a, u64 b, u64 m) {
9     return (u64)((u128)a * b % m);
10 }
11 
12 // Fast modular exponentiation: computes a^e mod m
13 u64 pow_mod(u64 a, u64 e, u64 m) {
14     u64 r = 1 % m;
15     a %= m;
16     while (e > 0) {
17         if (e & 1) r = mul_mod(r, a, m);
18         a = mul_mod(a, a, m);
19         e >>= 1;
20     }
21     return r;
22 }
23 
24 // Legendre symbol (a/p) for odd prime p
25 // Returns 0 if p | a, 1 if a is a quadratic residue, -1 otherwise
26 int legendre_symbol(long long a_ll, u64 p) {
27     if (p == 2) return (a_ll & 1) ? 1 : 0; // degenerate case
28     // Normalize a into [0, p-1]
29     u64 a = ( ( ( (__int128)a_ll % ( (__int128)p ) ) + p ) % p );
30     if (a == 0) return 0;
31     u64 x = pow_mod(a, (p - 1) / 2, p); // Euler's criterion
32     if (x == 1) return 1;
33     if (x == p - 1) return -1; // x ≡ -1 (mod p)
34     // Should not happen for prime p and a != 0, but we keep a fallback
35     return 0;
36 }
37 
38 int main() {
39     ios::sync_with_stdio(false);
40     cin.tie(nullptr);
41 
42     // Example usage: test several values modulo a prime p
43     u64 p = 1'000'000'007ULL; // large prime commonly used in contests
44     vector<long long> tests = {0, 1, 2, 3, 5, -1, (long long)p - 1};
45 
46     for (long long a : tests) {
47         int ls = legendre_symbol(a, p);
48         cout << "(a/p) for a = " << a << " mod p = " << ls << '\n';
49     }
50 
51     return 0;
52 }
53

This program computes the Legendre symbol (a/p) using Euler’s criterion a^{(p−1)/2} mod p. It first normalizes a into [0, p−1], handles the a ≡ 0 case, then uses fast exponentiation with 128-bit-safe modular multiplication to avoid overflow. The result 1 means a is a quadratic residue modulo p, −1 means a is a non-residue, and 0 means p divides a.

Time: O(log p) per querySpace: O(1)

Tonelli–Shanks: modular square root modulo an odd prime

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 using u64 = uint64_t;
5 using u128 = __uint128_t;
6 
7 static inline u64 mul_mod(u64 a, u64 b, u64 m) {
8     return (u64)((u128)a * b % m);
9 }
10 
11 u64 pow_mod(u64 a, u64 e, u64 m) {
12     u64 r = 1 % m;
13     a %= m;
14     while (e > 0) {
15         if (e & 1) r = mul_mod(r, a, m);
16         a = mul_mod(a, a, m);
17         e >>= 1;
18     }
19     return r;
20 }
21 
22 int legendre_symbol(long long a_ll, u64 p) {
23     if (p == 2) return (a_ll & 1) ? 1 : 0;
24     u64 a = ( ( ( (__int128)a_ll % ( (__int128)p ) ) + p ) % p );
25     if (a == 0) return 0;
26     u64 x = pow_mod(a, (p - 1) / 2, p);
27     if (x == 1) return 1;
28     if (x == p - 1) return -1;
29     return 0; // shouldn't occur for prime p, but safe
30 }
31 
32 // Returns pair(has_root, {r1, r2}). If has_root=false, r1=r2=0.
33 // If a == 0 mod p, returns {true, {0,0}}.
34 // Requires p odd prime.
35 pair<bool, pair<u64,u64>> mod_sqrt(long long a_ll, u64 p) {
36     if (p == 2) {
37         u64 a = ( ( ( (__int128)a_ll % ( (__int128)p ) ) + p ) % p );
38         return {true, {a, a}}; // only 0 or 1
39     }
40     u64 a = ( ( ( (__int128)a_ll % ( (__int128)p ) ) + p ) % p );
41     if (a == 0) return {true, {0, 0}};
42 
43     int ls = legendre_symbol((long long)a, p);
44     if (ls == -1) return {false, {0, 0}}; // no solution
45 
46     // Fast path when p % 4 == 3
47     if ((p & 3ULL) == 3ULL) {
48         u64 r = pow_mod(a, (p + 1) / 4, p);
49         u64 r2 = (p - r) % p;
50         if (r2 < r) swap(r, r2); // optional: order roots
51         return {true, {r, r2}};
52     }
53 
54     // Tonelli–Shanks general case
55     // Factor p-1 = q * 2^s with q odd
56     u64 q = p - 1;
57     unsigned s = 0;
58     while ((q & 1ULL) == 0ULL) { q >>= 1; ++s; }
59 
60     // Find a quadratic non-residue z
61     u64 z = 2;
62     while (legendre_symbol((long long)z, p) != -1) ++z;
63 
64     u64 c = pow_mod(z, q, p);
65     u64 r = pow_mod(a, (q + 1) / 2, p);
66     u64 t = pow_mod(a, q, p);
67     unsigned m = s;
68 
69     while (t != 1) {
70         // Find the smallest i in [1, m) such that t^{2^i} == 1
71         u64 tt = t;
72         unsigned i = 0;
73         for (i = 1; i < m; ++i) {
74             tt = mul_mod(tt, tt, p);
75             if (tt == 1) break;
76         }
77         // Compute b = c^{2^{m - i - 1}}
78         u64 b = c;
79         for (unsigned j = 0; j < m - i - 1; ++j) b = mul_mod(b, b, p);
80         // Update r, t, c, m
81         r = mul_mod(r, b, p);
82         u64 b2 = mul_mod(b, b, p);
83         t = mul_mod(t, b2, p);
84         c = b2;
85         m = i;
86     }
87 
88     u64 r2 = (p - r) % p;
89     if (r2 < r) swap(r, r2); // optional: order roots
90     return {true, {r, r2}};
91 }
92 
93 int main() {
94     ios::sync_with_stdio(false);
95     cin.tie(nullptr);
96 
97     // Example: find square roots for several pairs (a, p)
98     vector<pair<long long, u64>> tests = {
99         {10, 13}, // 6^2 = 36 ≡ 10 mod 13
100         {56, 101},
101         {5, 41},   // p ≡ 1 mod 4 -> general path
102         {8218, 1'000'000'007ULL},
103         {3, 7},    // no solution
104     };
105 
106     for (auto [a, p] : tests) {
107         auto ans = mod_sqrt(a, p);
108         cout << "a = " << a << ", p = " << p << ": ";
109         if (!ans.first) {
110             cout << "no square root\n";
111         } else {
112             auto [r1, r2] = ans.second;
113             cout << "roots = {" << r1 << ", " << r2 << "}\n";
114         }
115     }
116 
117     return 0;
118 }
119

This implementation computes modular square roots modulo an odd prime p. It first rejects non-residues using the Legendre symbol. If p ≡ 3 (mod 4), it uses the shortcut r = a^{(p+1)/4}. Otherwise, it runs Tonelli–Shanks: factor p−1 = q·2^s, find a quadratic non-residue z, initialize r, t, c, and iteratively reduce t to 1 by multiplying by powers of c. The program prints either both roots r and p−r or reports that no solution exists.

Time: O((log p)^2) in the general case; O(log p) when p ≡ 3 (mod 4)Space: O(1)

Enumerate all quadratic residues modulo p (and verify the half property)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 int main() {
5     ios::sync_with_stdio(false);
6     cin.tie(nullptr);
7 
8     int p;
9     cout << "Enter an odd prime p (small, e.g., <= 10^6): ";
10     if (!(cin >> p)) return 0;
11 
12     vector<int> residues(p, 0);
13     for (int x = 1; x < p; ++x) {
14         long long s = 1LL * x * x % p;
15         residues[(int)s] = 1;
16     }
17 
18     vector<int> list;
19     for (int a = 1; a < p; ++a) if (residues[a]) list.push_back(a);
20 
21     cout << "Count of nonzero quadratic residues: " << list.size() << " (expected " << (p - 1) / 2 << ")\n";
22     cout << "Residues: ";
23     for (size_t i = 0; i < list.size(); ++i) {
24         cout << list[i] << (i + 1 == list.size() ? '\n' : ' ');
25     }
26 
27     return 0;
28 }
29

This simple program builds a boolean table of which classes are squares by squaring every nonzero x modulo p. It then lists the distinct nonzero quadratic residues and confirms that there are exactly (p−1)/2 of them, illustrating the 2-to-1 nature of the squaring map.

Time: O(p)Space: O(p)

Jacobi symbol for odd composite moduli (with caution)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Computes the Jacobi symbol (a/n) for odd n > 0.
5 // Returns -1, 0, or 1. For composite n, (a/n) = 1 does NOT guarantee a sqrt exists.
6 int jacobi(long long a_ll, long long n_ll) {
7     if (n_ll <= 0 || (n_ll % 2) == 0) return 0; // defined for odd n > 0
8     long long a = a_ll % n_ll; if (a < 0) a += n_ll;
9     long long n = n_ll;
10     int r = 1;
11     while (a != 0) {
12         // Extract factors of 2 from a
13         int twos = __builtin_ctzll((unsigned long long)a);
14         a >>= twos;
15         if (twos & 1) {
16             long long nm8 = n % 8;
17             if (nm8 == 3 || nm8 == 5) r = -r; // (2/n) law
18         }
19         // Quadratic reciprocity swap
20         if ((a % 4 == 3) && (n % 4 == 3)) r = -r;
21         long long t = a; a = n % a; n = t;
22     }
23     return (n == 1) ? r : 0; // if gcd(a_ll, n_ll) > 1, result may be 0
24 }
25 
26 int main() {
27     ios::sync_with_stdio(false);
28     cin.tie(nullptr);
29 
30     vector<pair<long long,long long>> tests = {
31         {10, 21}, // n = 3*7, (10/21) = (10/3)(10/7) = (1)(-1) = -1
32         {5, 21},  // (5/21) = (2)*(−1) = −2? Actually result ∈ {−1,0,1}: (5/21) = (5/3)(5/7) = (−1)*(−1) = 1
33         {2, 45},  // odd composite
34         {1001, 99991},
35     };
36 
37     for (auto [a, n] : tests) {
38         int j = jacobi(a, n);
39         cout << "Jacobi(" << a << "/" << n << ") = " << j << '\n';
40     }
41 
42     cout << "Note: For composite n, Jacobi(a/n) = 1 does not ensure a square root exists." << '\n';
43     return 0;
44 }
45

This code computes the Jacobi symbol using iterative application of the supplementary laws and quadratic reciprocity, without factoring n. It is useful for quick quadratic character evaluation modulo odd n, but unlike the Legendre symbol, (a/n) = 1 does not imply x^2 ≡ a (mod n) is solvable when n is composite. Use with care.

Time: O(log^2 n) using simple division and parity operationsSpace: O(1)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	using u64 = uint64_t;
5	using u128 = __uint128_t;
6
7	// Multiply a and b modulo m using 128-bit to avoid overflow (for 64-bit m)
8	static inline u64 mul_mod(u64 a, u64 b, u64 m) {
9	return (u64)((u128)a * b % m);
10	}
11
12	// Fast modular exponentiation: computes a^e mod m
13	u64 pow_mod(u64 a, u64 e, u64 m) {
14	u64 r = 1 % m;
15	a %= m;
16	while (e > 0) {
17	if (e & 1) r = mul_mod(r, a, m);
18	a = mul_mod(a, a, m);
19	e >>= 1;
20	}
21	return r;
22	}
23
24	// Legendre symbol (a/p) for odd prime p
25	// Returns 0 if p \| a, 1 if a is a quadratic residue, -1 otherwise
26	int legendre_symbol(long long a_ll, u64 p) {
27	if (p == 2) return (a_ll & 1) ? 1 : 0; // degenerate case
28	// Normalize a into [0, p-1]
29	u64 a = ( ( ( (__int128)a_ll % ( (__int128)p ) ) + p ) % p );
30	if (a == 0) return 0;
31	u64 x = pow_mod(a, (p - 1) / 2, p); // Euler's criterion
32	if (x == 1) return 1;
33	if (x == p - 1) return -1; // x ≡ -1 (mod p)
34	// Should not happen for prime p and a != 0, but we keep a fallback
35	return 0;
36	}
37
38	int main() {
39	ios::sync_with_stdio(false);
40	cin.tie(nullptr);
41
42	// Example usage: test several values modulo a prime p
43	u64 p = 1'000'000'007ULL; // large prime commonly used in contests
44	vector<long long> tests = {0, 1, 2, 3, 5, -1, (long long)p - 1};
45
46	for (long long a : tests) {
47	int ls = legendre_symbol(a, p);
48	cout << "(a/p) for a = " << a << " mod p = " << ls << '\n';
49	}
50
51	return 0;
52	}
53

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Computes the Jacobi symbol (a/n) for odd n > 0.
5	// Returns -1, 0, or 1. For composite n, (a/n) = 1 does NOT guarantee a sqrt exists.
6	int jacobi(long long a_ll, long long n_ll) {
7	if (n_ll <= 0 \|\| (n_ll % 2) == 0) return 0; // defined for odd n > 0
8	long long a = a_ll % n_ll; if (a < 0) a += n_ll;
9	long long n = n_ll;
10	int r = 1;
11	while (a != 0) {
12	// Extract factors of 2 from a
13	int twos = __builtin_ctzll((unsigned long long)a);
14	a >>= twos;
15	if (twos & 1) {
16	long long nm8 = n % 8;
17	if (nm8 == 3 \|\| nm8 == 5) r = -r; // (2/n) law
18	}
19	// Quadratic reciprocity swap
20	if ((a % 4 == 3) && (n % 4 == 3)) r = -r;
21	long long t = a; a = n % a; n = t;
22	}
23	return (n == 1) ? r : 0; // if gcd(a_ll, n_ll) > 1, result may be 0
24	}
25
26	int main() {
27	ios::sync_with_stdio(false);
28	cin.tie(nullptr);
29
30	vector<pair<long long,long long>> tests = {
31	{10, 21}, // n = 3*7, (10/21) = (10/3)(10/7) = (1)(-1) = -1
32	{5, 21}, // (5/21) = (2)(−1) = −2? Actually result ∈ {−1,0,1}: (5/21) = (5/3)(5/7) = (−1)(−1) = 1
33	{2, 45}, // odd composite
34	{1001, 99991},
35	};
36
37	for (auto [a, n] : tests) {
38	int j = jacobi(a, n);
39	cout << "Jacobi(" << a << "/" << n << ") = " << j << '\n';
40	}
41
42	cout << "Note: For composite n, Jacobi(a/n) = 1 does not ensure a square root exists." << '\n';
43	return 0;
44	}
45