In general, if the prime factorization of n is p₁*p₂*...*p_t, then the system of equations

(x mod pi) = ai, where i = 1, 2,..., t

has a unique solution, x, where x is less than n. (Note that some primes can appear more than once. For example, p₁ might be equal to p₂ .) In other words, a number (less than the product of some primes) is uniquely identified by its residues mod those primes.

For example, use 3 and 5 as primes, and 14 as the number. 14 mod 3 = 2, and 14 mod 5 = 4. There is only one number less than 3*5 = 15 which has those residues: 14. The two residues uniquely determine the number.

So, for an arbitrary a < p and b < q (where p and q are prime), there exists a unique x, where x is less than pq, such that

x ≡ a (mod p), and x ≡ b (mod q)

To find this x, first use Euclid’s algorithm to find u, such that

u*q ≡ 1 (mod p)

Then compute:

x = (((a - b)*u) mod p)*q + b

Here is the Chinese remainder theorem in C:

    /* r is the number of elements in arrays m and u;
    m is the array of (pairwise relatively prime) moduli
    u is the array of coefficients
    return value is n such than n == u[k]%m[k] (k=0..r-1) and
    	n < m[0]*m[1]*...*m[r-1]
    */

    /* totient() is left as an exercise to the reader. */
    int chinese_remainder (size_t r, int *m, int *u)
    {
        size_t i;
        int modulus;
        int n;
        modulus = 1;
        for (i=0; i<r; ++i)
    	modulus *= m[i];

        n = 0;
        for (i=0; i<r; ++i) {
    	n += u[i] * modexp(modulus / m[i], totient(m[i]),
        m[i]);
    	n %= modulus;
        }

        return n;
    }

The converse of the Chinese remainder theorem can also be used to find the solution to the problem: if p and q are primes, and p is less than q, then there exists a unique x less than pq, such that

a ≡ x (mod p), and b ≡ x (mod q)

If a ≥ b mod p, then

x = (((a - (b mod p))*u) mod p)*q + b

If a < b mod p, then

x = (((a + p - (b mod p))*u) mod p)*q + b

Quadratic Residues

If p is prime, and a is greater than 0 and less than p, then a is a quadratic residue mod p if

x² ≡ a (mod p), for some x

Not all values of a satisfy this property. For a to be a quadratic residue modulo n, it must be a quadratic residue modulo all the prime factors of n. For example, if p = 7, the quadratic residues are 1, 2, and 4:

1² = 1 ≡ 1 (mod 7)

2² = 4 ≡ 4 (mod 7)

3² = 9 ≡ 2 (mod 7)

4² = 16 ≡ 2 (mod 7)

5² = 25 ≡ 4 (mod 7)

6² = 36 ≡ 1 (mod 7)

Note that each quadratic residue appears twice on this list.

There are no values of x which satisfy any of these equations:

x² ≡ 3 (mod 7)

x² ≡ 5 (mod 7)

x² ≡ 6 (mod 7)

The quadratic nonresidues modulo 7, the numbers that are not quadratic residues, are 3, 5, and 6.

Although I will not do so here, it is easy to prove that, when p is odd, there are exactly (p- 1)/2 quadratic residues mod p and the same number of quadratic nonresidues mod p. Also, if a is a quadratic residue mod p, then a has exactly two square roots, one of them between 0 and (p- 1)/2, and the other between (p- 1)/2 and (p- 1). One of these square roots is also a quadratic residue mod p; this is called the principal square root.

If n is the product of two primes, p and q, there are exactly (p- 1)(q- 1)/4 quadratic residues mod n. A quadratic residue mod n is a perfect square modulo n. This is because to be a square mod n, the residue must be a square mod p and a square mod q. For example, there are 11 quadratic residues mod 35: 1, 4, 9, 11, 14, 15, 16, 21, 25, 29, and 30. Each quadratic residue has exactly four square roots.

Legendre Symbol

The Legendre symbol, written L(a,p), is defined when a is any integer and p is a prime greater than 2. It is equal to 0, 1, or -1.

L(a,p) = 0 if a is divisible by p.

L(a,p) = 1 if a is a quadratic residue mod p.

L(a,p) = - 1 is a is a quadratic nonresidue mod p.

One way to calculate L(a,p) is:

L(a,p) = a^{(p- 1)/2} mod p

Or you can use the following algorithm:

1.  If a = 1, then L(a,p) = 1

2.  If a is even, then L(a,p) = L(a /2,p)*(- 1)^{(p2- 1)/8}

3.  If a is odd (and ≠ 1), then L(a,p) = L(p mod a,a)*(- 1)^{(a- 1)*(p- 1)/4}

Note that this is also an efficient way to determine whether a is a quadratic residue mod p (when p is prime).