Integer division takes two integers, the dividend and divisor, and yields two integers, the quotient and remainder, where the remainder is non-negative and smaller than the divisor. If two dividends have the same remainder when divided by the same divsior n, we say that they are congruent modulo n.

Congruence modulo n is an equivalence relation on the integers. It partitions the integers into n equivalence classes. The equivalence classes are called the residues modulo n. Any member of a residue is a representative.

Arithmetic can be defined on residues.

Addition, Additive Inverse, and Multiplication

Sometimes we can perform operations on representatives of the residues using customary integer operations and the result will be a representative of the residue we would have got if we performed the corresponding operations on the residue classes.

This is true for addition and multiplication and we can use this to show that addition and multiplication on residues are both associative and commutative. They also observe the distributive law.

The additive identity is the reside class with zero in it. The additive inverse residue exists and can be found by computing the additive inverse of a representative.

In summary, the residues modulo n are a commutative ring with identity and addition, negation, and multiplication can be calculated by doing the corresponding operations on representatives.

Exponentiation

Exponentiation can be calculated using repeated multiplication, so the preceding section shows us that we can compute exponentiation on a residue by using a representative. Note that the base is a residue, but the exponent is an integer.

There is a shortcut for computing exponents due to Euler when a and n are relatively prime:

(1)

$$ \begin{align} a^{\phi(n)} \equiv 1 \;(\text{mod}\;n) \end{align} $$

The congruence allows us to compute any exponent with fewer than φ(n) multiplications.

The function φ is called Euler's totient, and it counts the positive integers less than or equal to n which are relatively prime to n. An expression for the totient is

(2)

$$ \begin{align} \phi(n) = n \prod_{p | n} \frac{p - 1}{p} \end{align} $$

where the product is over all primes that divide n. When n is itself prime, Euler's Theorem reduces to Fermat's Little Theorem:

(3)

$$ \begin{align} a^{p-1} \equiv 1 \;(\text{mod}\; p) \end{align} $$

Multiplicative Inverse and Division

Division on the integers is often not defined. An integer a is divisible by b if there is another integer m such that:

(4)

$$ \begin{align} a = mb \end{align} $$

Multiplicative inverses for most integers don't exist. The exceptions are 1 and -1, which are their own inverses.

For residues, the situation is better. A nonzero residue a modulo n has a multiplicative inverse if and only if a and n are relatively prime. The extended Euclidean algorithm will find x and y such that ax + ny = 1, and thus x is the multiplicative inverse of a.

If the modulus n is prime, then all nonzero residues have multiplicative inverses and the residues are a field.

If n is not prime, the residues are not an integral domain and cancellation of a nonzero factor is not always possible. If d is the greatest common divisor of a and n, then for all z and z' we have this result:

(5)

$$ \begin{align} az \equiv az' \;(\text{mod}\; n) \iff z \equiv z' \;\left(\text{mod}\; \frac{n}{d}\right) \end{align} $$

If a and n are relatively prime, which means d is 1, we can cancel a from both sides of the equation.

Square Roots

Non-zero complex numbers have two square roots in the complex numbers.

Positive real numbers have two square roots in the real numbers and negative real numbers have none.

Positive integers have two square roots in the integers if they are perfect squares, otherwise they have none.

The single non-zero residue modulo 2 has one square root.

Non-zero residues (p > 2) have either two square roots or none. In the former case, the residue is said to be a quadratic residue and in the latter case a quadratic nonresidue. Determining whether a residue is a quadratic residue is complicated. The following notation, called the Legendre symbol, is used when p is an odd prime:

(6)

$$ \begin{align} \left( \frac{a}{p} \right) = \begin{cases} \;\; 1 \;\;\; a \; \text{is a quadratic residue} \\ \;\; 0 \;\;\; p \mid a \\ -1 \;\;\; a \; \text{is a quadratic nonresidue} \end{cases} \end{align} $$

The following always hold:

(7)

$$ \begin{align} \left( \frac{1}{p} \right) = 1 \\ \left( \frac{-1}{p} \right) = (-1)^{\frac{p-1}{2}} \\ \left( \frac{2}{p} \right) = (-1)^{\frac{p^2 - 1}{8}} \\ \left( \frac{a}{p} \right) \left( \frac{b}{p} \right) = \left( \frac{ab}{p} \right) \end{align} $$

When a and p are relatively prime then

(8)

$$ \begin{align} \left(\frac{a^2}{p} \right) = 1 \end{align} $$

The Jacobi symbol is a generalization of the Legendre symbol where p is replaced by any positive odd integer n. The Kronecker symbol is a further generalization where n can be any non-zero integer.

The quadratic reciprocity law states that for odd primes q and p which both are are of the form 4k +3, then exactly one of the following congruences has a solution:

(9)

$$ \begin{align} x^2 \equiv q \;(\text{mod}\;p) \end{align} $$

(10)

$$ \begin{align} x^2 \equiv p \;(\text{mod}\;q) \end{align} $$

Moreover, if q and p are odd primes not both of the form 4k + 3, then both congruences are solvable or both congruences are not.

How the quadratic reciprocity law is used:

(11)

$$ \begin{align} \left(\frac{3}{5}\right) = \left(\frac{5}{3}\right) = \left(\frac{2}{3}\right) = (-1)^{\frac{3^2 - 1}{8}} = -1 \end{align} $$

(12)

$$ \begin{align} \left(\frac{3}{7}\right) = -\left(\frac{7}{3}\right) = -\left(\frac{1}{3}\right) = -1 \end{align} $$

If a is a quadratic residue of an odd prime p congruent to 3 modulo 4, then

(13)

$$ \begin{align} x \equiv \pm a^{(p+1)/4} \;(\text{mod}\;p) \end{align} $$

If a is a quadratic residue of an odd prime p congruent to 5 modulo 8, then

(14)

$$ \begin{align} x \equiv \begin{cases} \pm a^{(n+3)/8} \;(\text{mod}\;p) \\ \pm a^{(n+3)/8} 2^{(n-1)/4} \;(\text{mod}\;p) \end{cases} \end{align} $$

There is no known formula when a is a quadratic residue of an odd prime p congruent to 1 modulo 8. The Tonelli-Shanks algorithm offers a method for finding a solution, however.

Finding square roots is a special case of finding the roots of a polynomial. If f(x) is a polynomial with integer coefficients, then Hensel's lemma provides a way subject to some conditions of calculating roots module p^k+m, m ≤ k, when we know a root for f(x) modulo p^k.

If f(x) is a polynomial with integer coefficients, then Hensel's lemma specifies conditions under which we can find roots for f(x) modulo p^k+m, m ≤ k, when we know a root for f(x) modulo p^k. In particular, suppose that

(15)

$$ \begin{align} f(r) \equiv 0 \;(\text{mod}\;p) \;\;\;\textrm{and}\;\;\; f'(r) \not\equiv 0 \;(\text{mod}\;p) \end{align} $$

let

(16)

$$ \begin{align} s = r - f(r) \cdot a \;\;\;\textrm{for any}\;a\;\textrm{such that}\;\;\; a \equiv [f'(r)]^{-1} \;(\text{mod}\;p^m) \end{align} $$

then

(17)

$$ \begin{align} f(x) \equiv 0 \;(\text{mod}\;p^{k+m}) \;\;\;\textrm{and}\;\;\; r \equiv s \;(\text{mod}\;p^k) \end{align} $$

what if f'(r) is zero

general case when n is composite

quadratic residuosity problem

Discrete Logarithm

The discrete log of g base b, where both g and b are residues modulo n, is an integer k such at b^k = g. If n is prime, then the multiplicative group is cyclic and a solution exists if b is not 0 or 1, and g is not 0. A brute force search has run time which is linear in the size of the multiplicative group, or exponential in the number of digits in the size of the multiplicative group. Better algorithms exist, but none are polynomial in the number of digits in the size of the multiplicative group.

Multiple Equations

If we have multiple equations with the same modulus, we can use substitution to find a solution.

If the moduli on the equations are different, the Chinese Remainder Theorem tells us there is a solution under certain conditions. In particular there is a solution a to the following system of equations, provided that the n_i are all pairwise relatively prime:

(18)

$$ \begin{align} a \equiv a_i \mod n_i \;\;\; (i = 1,\ldots,k) \end{align} $$

Moreover, if a and a' are two solutions, then:

(19)

$$ \begin{align} a \equiv a' \mod \prod_{i=1}^k n_i \end{align} $$

The way to find a solution is by repeated application of the extended Euclidean algorithm. Find m₁ and m₂ such that

(20)

$$ \begin{align} m_1 n_1 + m_2 m_2 = 1 \end{align} $$

Then

(21)

$$ \begin{align} x = a_1 m_2 n_2 + a_2 m_1 n_1 \end{align} $$

will be a solution to the first two equations. These can be replaced by

(22)

$$ \begin{align} x \equiv a_{1,2} \;(\text{mod}\;n_1 n_2) \end{align} $$